Решение задач методом Давидона-Флетчера-Пауэлла. Градиентные методы

Курсовая работа

Решение задач методом Давидона-Флетчера-Пауэлла. Градиентные методы

Содержание

Введение

1. Минимизация функции нескольких переменных

2. Градиентные методы

2.1 Метод покоординатного спуска

2.2 Метод градиентного спуска и его модификации

3. Метод Давидона-Флетчера-Пауэлла

3.1 Идея метода

3.2 Алгоритм Метода

4. Блок-схемы

4.1 Блок-схема основной программы

4.2 Блок-схемы процедур

5. Программы

6. Пример решения задач

Заключение

Список использованной литературы

Введение

Первые задачи геометрического содержания, связанные с отысканием наибольших и наименьших величин, появились еще в древние времена. Развитие промышленности в 17-18 веках привело к необходимости исследования более сложных задач на экстремум и к появлению вариационного исчисления.

Потребности развития самой вычислительной математики в более позднее время привели к необходимости исследования таких задач на максимум и минимум, как, например, задачи наилучшего приближения функции, оптимального выбора параметров интерполяционного процесса или узлов интерполирования, минимизации функции нескольких переменных и т.д.

Потребности практики способствовали бурному развитию методов приближенного решения экстремальных задач. Внедрение компьютеров во все сферы человеческой деятельности потребовало от специалистов разного профиля навыков использования вычислительной техники. Но, вместе с тем, появление быстродействующих электронных вычислительных машин сделало возможным эффективное решение многих важных прикладных экстремальных задач, которые ранее из-за своей сложности представлялись недоступными.

Применение ЭВМ в настоящее время приобрело поистине массовый характер. Компьютеры используются не только в области науки и инженерии, но и для обработки, хранения и передачи информации, а также при решении ряда других задач и даже в быту. Тем не менее, использование электронных вычислительных машин для проведения математических вычислений не потеряло своей актуальности.

Целью моей работы являлось решение одной из задач численных методов, а в частности минимизации функции конечного числа переменных. К настоящему времени разработано и исследовано большое число методов минимизации функций многих переменных, но в данной работе подробно рассматривается метод Давидона-Флетчера-Пауэлла.

1. Минимизация функции нескольких переменных

При таких определениях и очевидных предположениях относительно дифференцируемости можно рассмотреть разложение функции в ряд Тейлора в окрестности точки x₀:

Следовательно, необходимым условием минимума в точке x₀ является уравнение:



Если матрица G(x₀) положительно определена, то этот член положителен для всех h. Следовательно, необходимым и достаточным условиями минимума являются:

Необходимыми и достаточными условиями максимума являются:

Рассмотрим пример:

2. Градиентные методы

В моей курсовой работе речь идет об алгоритме нахождения минимума функции конечного числа переменных методом Давидона-Флетчера-Пауэлла.

Данный метод является одним из так называемых градиентных методов. Само название данного класса методов говорит о том, что поиск наименьшего значения функций в них осуществляется с помощью использования градиента.

2.1 Метод покоординатного спуска

Данный метод не является градиентным, но его рассмотрение необходимо для понимания идеи градиентных методов. На разработку методов прямого поиска для определения минимума функции n переменных было затрачено много усилий. Методы прямого поиска являются методами, в которых используются только значения функции. Рассмотрим подробно метод покоординатного спуска.



Рассмотрим функцию двух переменных. Ее линии постоянного уровня¹ представлены на рисунке выше, а минимум лежит в точке (x*, x*). Простейшим методом поиска является метод покоординатного спуска. Из точки А мы про- таким образом, мы приходим к оптимальной точке.

Теоретически данный метод эффективен в случае единственного минимума. Но на практике он оказывается слишком медленным. Поэтому были разработаны более сложные методы, использующие больше информации на основе полученных значений функции.

2.2 Метод градиентного спуска и его модификации

С помощью упомянутого в предыдущем параграфе 2.1 метода покоординатного спуска, поиск осуществляется из заданной точки в направлении, параллельном одной из осей, до точки минимума в данном направлении. Затем поиск производится в направлении, параллельном другой оси, и т.д. Направления, конечно, фиксированы. Кажется разумным, попытаться модифицировать этот метод таким образом, чтобы на каждом этапе поиск точки минимума производился вдоль «наилучшего» направления. Не ясно, какое направление является «наилучшим», но известно, что направления градиента является направлением наискорейшего возрастания функции. Следовательно, противоположное направление, является направлением наискорейшего убывания функции.

Рассмотрим функцию двух переменных u= f(х, у). Ее градиент равен:



где е1, е2 -- единичные векторы (орты) в направлении координатных осей.
Следовательно, направление, противоположное градиентному, укажет на-
правление наибольшего убывания функции.

Выбираем некоторую начальную точку

и вычисляем в ней градиент рассматриваемой функции. Делаем шаг в направлении, обратном градиентному:

В результате приходим в точку M1 (x(1)), значение функции в которой обычно меньше первоначального (б(1) > 0). Если это условие не выполнено, т. е. значение функции не изменилось либо даже возросло, то нужно уменьшить шаг б(1) . В новой точке процедуру повторяем: вычисляем градиент и снова делаем шаг в обратном к нему направлении:

Процесс продолжается до получения наименьшего значения целевой функции. Строго говоря, момент окончания поиска наступит тогда, когда движение из полученной точки с любым шагом приводит к возрастанию значения целевой функции. Если минимум функции достигается внутри рассматриваемой области, то в этой точке градиент равен нулю, что также может служить сигналом об окончании процесса оптимизации. Приближенно момент окончания поиска можно определить аналогично тому, как это делается в других итерационных, методах. Например, можно проверить близость значений целевой функции на двух последовательных итерациях:

При использовании градиентного спуска в задачах оптимизации основной объем вычислений приходится обычно на вычисление градиента целевой функции в каждой точке траектории спуска. Поэтому целесообразно уменьшить количество таких точек без ущерба для самого решения. Это достигается в некоторых методах, являющихся модификациями градиентного спуска. Одним из них является метод наискорейшего спуска. Согласно этому методу, после определения в начальной точке направления, противоположного градиенту целевой функции, решают одномерную задачу оптимизации, минимизируя функцию вдоль этого направления. А именно, минимизируется функция

Для минимизации g(б) можно использовать один из методов одномер-ной оптимизации. Можно и просто двигаться в направлении, противопо-ложном градиенту, делая при этом не один шаг, а несколько шагов до тех пор, пока целевая функция не перестанет убывать. В найденной новой точке снова определяют направление спуска (с помощью градиента) и ищут новую точку минимума целевой функции и т. д. В этом методе спуск происходит гораздо более крупными шагами, и градиент функции вычисляется в меньшем числе точек.

Проиллюстрирую метод наискорейшего спуска на рисунке для случая функции двух переменных z = f(x,y) и отмстим некоторые его геометрические особенности.

Во-первых, легко показать, что градиент функции перпендикулярен касательной к линии уровня в данной точке. Следовательно, в градиентных методах спуск происходит по нормали к линии уровня.

Во-вторых, в точке, в которой достигается минимум целевой функции вдоль направления, производная функции по этому направлению обраща-ется в нуль. Но производная функции равна нулю по направлению каса-тельной к линии уровня. Отсюда следует, что градиент целевой функции в новой точке перпендикулярен направлению одномерной оптимизации на предыдущем шаге, т. е. спуск на двух последовательных шагах про-изводится во взаимно перпендикулярных направлениях.

3. Метод Давидона-Флетчера-Пауэлла

3.1 Идея метода

Первоначально метод был предложен Дэвидоном (Davidon [1959] ), а затем развит Флетчером и Пауэллом (Fletcher, Powell [1963] ). Метод Дэвидона-Флетчера-Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в виде -D_jf(y). Направление градиента является, таким образом, отклоненным в результате умножения на -D_j , где D_j - положительно определенная симметрическая матрица порядка n n, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица D_j+1 представляется в виде суммы D_j и двух симметрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два.

Среди алгоритмов многомерной минимизации следует выделить группу алгоритмов, которые объединяют достоинства метода наискорейшего спуска и метода Ньютона. Такие алгоритмы принято относить к так называемым квазиньютоновским методам. Особенность этих алгоритмов состоит в том, что при их применении нет необходимости вычислять и обращать матрицу Гессе целевой функции f(x) и в то же время удается сохранить высокую скорость сходимости алгоритмов, присущую методу Ньютона и его модификациям.

3.2 Алгоритм метода

2. Рассмотрим функцию нескольких переменных,g(x), где x - некоторый вектор. H_i - положительно определенная симметрическая матрица, которая обновляется на каждом шаге, как это будет описано ниже. В пределе матрица H становится равной обратному гессиану, т.е. G^-1.

В качестве направления взять направление

(1)

4. Положить

(2)

5. Положить

Замечание.

(4)

7. Положить

(5)

8. Обновить матрицу H следующим образом:

(6)

9. Увеличить i на единицу и вернуться на шаг 2.

Поясним процедуру, следуя аргументации Флетчера и Пауэлла.

(9)

ложительно

Определению. Процесс обновления в соответствии с соотношениями (6)-(8) сохраняет симметричность гессиана. Докажем, что после обновления матрица H_i остается положительно определенной. Если это условие справедливо, то

(10)

(12)

Знаменатель в соотношении (12) положителен, т.к.



Следовательно,

4. Блок схемы

4.1 Блок-схема основной программы

4.2 Блок-схемы процедур

Блок схема процедуры Isxfunc

Блок-схема процедуры funkcii



Блок-схема процедуры MDFP





Блок-схема процедуры Vect



Блок-схема процедуры Matvect

5. Программы

5.1 Основная программа

program pr1;

Uses DFP,CRT;

const

n=2;

fres='res_01.pas';

fdata='dat_1.pas';

Var fr,fd:text;

E,h:real;

i:integer;

b,f:vector;

{$F+}

procedure IsxFunc(n:integer;b:vector;Var fy:real);

begin

fy:=sqr(sqr(b[1]-2))+sqr(b[1]-2*b[2]);

end;

{$F-}

{$F+}

procedure funkcii(n:integer;b:vector;Var f:vector);

begin

f[1]:=4*sqr(b[1]-2)*(b[1]-2)+2*(b[1]-2*b[2]);

f[2]:=-4*(b[1]-2*b[2]);

end;

{$F-}

begin

clrscr;

Assign(fd,fdata);

reset(fd);

Assign(fr,fres);

rewrite(fr);

for i:=1 to n do

read(fd,b[i]);

writeln(fr,'b[n]');

for i:=1 to n do

writeln(fr,b[i]:0:6);

writeln(fr);

writeln('Введите точность E');

readln(E);

writeln('Введите шаг h');

readln(h);

MDFP(h,n,E,b,fr,IsxFunc,funkcii);

close(fd);

close(fr);

end.

Процедура MDFP

procedure MDFP(h:real;n:integer;E:real;Var b:vector;Var fr:text;IsxFunc:Proc1;

funkcii: proc);

Var lambd,G1,G,norma:real;

i,k,o,j,z:integer;

p,q,d,lf,u3,f2,f,r:vector;

u5,u2:real;

a:matrix;

begin

For i:=1 to n do

For j:=1 to n do

if i=j then a[i,j]:=1

else a[i,j]:=0;

o:=0;

Repeat

writeln(fr,' -------------------------------------------------');

funkcii(n,b,f);

norma:=sqrt(sqr(f[1])+sqr(f[2]));

writeln(fr,'norma= ',norma:2:6);

matvect(n,a,f,d);

lambd:=-1;

for z:=1 to n do

r[z]:=b[z]-lambd*d[z];

Repeat

Isxfunc(n,r,G);

lambd:=lambd+h;

for z:=1 to n do

r[z]:=b[z]-lambd*d[z];

Isxfunc(n,r,G1);

Until G<G1;

Lambd:=lambd-h;

writeln(fr,'lambda=',lambd:2:6);

for i:=1 to n do

b[i]:=b[i]-lambd*d[i];

writeln(fr,'b[n]');

for i:=1 to n do

writeln(fr,b[i]:2:6);

writeln(fr);

for i:=1 to n do

p[i]:=-lambd*d[i];

funkcii(n,b,f2);

for i:=1 to n do

q[i]:=f2[i]-f[i];

writeln(fr,'p[n]');

for i:=1 to n do

writeln(fr,p[i]:0:2);

writeln(fr);

writeln(fr,'q[n]');

for i:=1 to n do

writeln(fr,q[i]:0:2);

writeln(fr);

vect(n,p,q,u2);

matvect(n,a,q,u3);

vect(n,u3,q,u5);

for i:=1 to n do

for k:=1 to n do

a[i,k]:=a[i,k]+p[i]*p[k]/u2-u3[i]*u3[k]/u5;

writeln(fr,'a[n,n]');

for i:=1 to n do begin

for k:=1 to n do

write(fr,a[i,k]:2:6,' ');

writeln(fr);

end;

o:=o+1;

until norma<E;

writeln(fr,'точность достигается за ',o,'итераций');

end;

Процедура Vect

procedure vect(n:integer;a,b:vector;Var c:real);

Var i:integer;S:real;

begin

S:=0;

for i:=1 to n do

S:=S+a[i]*b[i];

c:=S;

end;

Процедура Matvect.

procedure matvect(n:integer; at:matrix;b:vector;Var atb:vector);

Var i,j:integer;S:real;

begin

for i:=1 to n do begin

s:=0;

for j:=1 to n do

S:=S+at[i,j]*b[j];

atb[i]:=S;

end;

end;

6. Пример решения задач

Дана функция f(x) = (x₁-2)⁴+(x₁-2x₂)². Используя точку (0,3) в качестве начальной, минимизировать данную функцию методом Давидона-Флетчера-Пауэлла.

Результат:

b[n]

0.000000

3.000000

-------------------------------------------------

norma= 50.119856

lambda=0.060000

b[n]

2.640000

1.560000

p[n]

2.64

-1.44

q[n]

44.09

-22.08

a[n,n]

0.247550 0.374735

0.374735 0.813474

-------------------------------------------------

norma= 1.922042

lambda=0.220000

b[n]

2.476888

1.209086

p[n]

-0.16

-0.35

q[n]

0.46

-2.15

a[n,n]

0.130882 0.103797

0.103797 0.185134

-------------------------------------------------

norma= 0.599200

lambda=5.370000

b[n]

2.220359

1.135319

p[n]

-0.26

-0.07

q[n]

-0.61

0.44

a[n,n]

0.619806 0.277395

0.277395 0.218288

-------------------------------------------------

norma= 0.209246

lambda=1.610000

b[n]

2.188175

1.090433

p[n]

-0.03

-0.04

q[n]

0.10

-0.23

a[n,n]

0.763359 0.467885

0.467885 0.396002

-------------------------------------------------

norma= 0.050578

lambda=6.170000

b[n]

2.078192

1.042724

p[n]

-0.11

-0.05

q[n]

-0.05

0.06

a[n,n]

4.300388 2.088602

2.088602 1.112349

-------------------------------------------------

norma= 0.031639

lambda=1.460000

b[n]

2.068796

1.034009

p[n]

-0.01

-0.01

q[n]

0.02

-0.03

a[n,n]

4.951443 2.674190

2.674190 1.557562

-------------------------------------------------

norma= 0.004221

lambda=7.230000

b[n]

2.026631

1.013782

p[n]

-0.04

-0.02

q[n]

-0.00

0.01

a[n,n]

33.555206 16.631863

16.631863 8.341934

Точность достигается за 7 итераций.

Данный результат получается при заданной точности Е = 0.01 и шаге изменения h=0.01

Можно произвести проверку правильности нахождения минимальной точки, подставив полученные значения b[n] в выражения частных производных данной функции.

f(x)/dx₁ = 4(x₁-2)³+2(x₁-2x₂) = 4(2.026 - 2)³+2(2.026 - 2*1.013)=0.000

f(x)/dx₂ = -4(x₁-2x₂) = -4(2.026 - 2*1.013)=0.000

Полученные выражения максимально близки к нулю в зависимости от заданной точности, что удовлетворяет необходимым и достаточным условиям минимума функции нескольких переменных. Следовательно, можно считать, что задача решена.

Заключение

В настоящее время теория экстремальных задач обогатилась фундаментальными результатами, появились ее новые разделы. В любой практической оптимизационной задаче существует много совпадающих этапов. Наиболее важным этапом является моделирование рассматриваемой физической ситуации с целью получения математической функции, которую необходимо минимизировать, а также определения ограничений, если таковые существуют. Затем следует выбрать подходящую процедуру для осуществления минимизации. Эта процедура должна быть реализована на практике, что во многих реальных случаях вынуждает использовать ЭВМ для выполнения большого объема вычислений. Не случайно, что многие важные методы оптимизации были разработаны в течение трех последних десятилетий, в период появления цифровых ЭВМ, и эти методы являются машинными. Трудно считать их сколько-нибудь практически значимыми без большой скорости и эффективности вычислительных машин, имеющихся в нашем распоряжении. На многих универсальных ЭВМ имеются пакеты программ оптимизации, реализующие эти методы. Они мо гут оказаться весьма эффективными и позволят решить широкий круг задач.

В данной курсовой работе был описан алгоритм минимизации функции нескольких переменных методом Давидона-Флетчера-Пауэлла. Было приведено несколько примеров, как ручного счета, так и подробного описания алгоритма минимизации с помощью ЭВМ нахождения минимума функции данным методом. Было показано, что метод Давидона-Флетчера-Пауэлла имеет высокую скорость сходимости. Делая вывод нужно отметить, что ДФП - метод является важным инструментом многомерной оптимизации.

Список использованной литературы

1). А.В. Аттетков, С.В. Галкин, В.С. Зарубин Методы оптимизации. под редакцией В.С. Зарубин и А.П. Крищенко,2001

2). Ф.П. Васильев. Методы решения экстремальных задач. М: Наука, 1981.

3). Ф.П. Васильев. Численные методы решения экстремальных задач М.: Наука, 1988

4). Б. Банди Методы оптимизации вводный курс. М.: Радио и связь,1988.

5). Б.Н. Пшеничный Ю.М. Данилин численные методы в экстремальных задачах. М.: Наука, 1975

6). Л.И. Турчак, П.В. Плотников. Основы численных методов. Учебное пособие-2е изд.,ФИЗМАТЛИТ,2003