Найти минимум функции n переменных методом Гольдфарба
ПОЯСНИТЕЛЬНАЯ
ЗАПИСКА
к
курсовой работе
на
тему
«Найти
минимум функции n переменных методом Гольдфарба»
Введение
С точки зрения математики задачей
оптимизации называется задача нахождения экстремума вещественной функции в
некоторой области. Чем больше информации мы знаем, тем более эффективно и
быстро можно достичь минимума, если правильно воспользоваться информацией.
Методы оптимизации классифицируют в соответствии с задачами оптимизации:
) Методы оптимизации
классифицируют в соответствии с задачами оптимизации:
Локальные методы: сходятся к
какому-нибудь локальному экстремуму целевой функции. В случае унимодальной
целевой функции, этот экстремум единственен, и будет глобальным максимумом /
минимумом.
) Глобальные методы: имеют дело с
многоэкстремальными целевыми функциями. При глобальном поиске основной задачей
является выявление тенденций глобального поведения целевой функции.
По критерию размерности допустимого
множества, методы оптимизации делят на методы одномерной и многомерной
оптимизации.
3) Задачи
оптимизации, в которых целевая функция F(
) и ограничение 
, i = 1, …, m
является линейными функциями, разрешаются так называемыми методами линейного
программирования.
Метод Гольдфарба был разработан в
1970 году, но до сих пор является весьма эффективным и оригинальным. Поиск
состоит из последовательности шагов исследующего поиска вокруг базисной точки,
за которой в случае успеха следует поиск по образцу. Он применяется для решения
задачи минимизирования функции без учёта ограничений.
Описание алгоритмов
решения поставленной задачи
В рассмотренном ниже классе методов
с переменной метрикой реализована идея адаптивного управления.
Информация о предыдущих итерациях
накапливается в специальной матрице Н, которая по мере накопления информации
постепенно превращается в обратную матрицу Гессе
При этом матрица вторых производных
на каждом шаге не пересчитывается.
Метод Гольдфарба
Он более устойчив к ошибкам
вычислений, чем ДФП
Рассмотрим решение задачи при помощи
данной программы.
Чтобы выполнить нашу программу мы
должны поступить следующим образом:
. Мы должны ввести значения
функции, например (x[0]+2x[1])2в Unit1. Это будет выглядеть так, как представлено на рисунке 1.
Рис. 1.
. И для того чтобы получить
ответ, мы должны нажать на кнопку «Ввести». В результате появится график, это и
будет наш ответ (Рис. 2.)
Рис. 2.
Ответ: Минимум x=(0,0057
-0,0029)(x)=0,0000
Градиент (0,0000 0,0000)
Заключение
Ø Среди
методов нулевого порядка наибольшей эффективностью обладают метод Розенброка
и метод НелдераМида
Ø Если же
функция гладкая, т.е. имеет непрерывные производные, то наиболее эффективным
себя зарекомендовали метод Гольдфарба и метод ДФП (они в 2-6 раз
эффективнее по быстродействию чем метод Розенброка).
Ø На
самом деле многое зависит от вида конкретной оптимизируемой функции. Особенно
если количество оптимизируемых переменных больше 4-5 нужно иметь в запасе
несколько разнообразных методов, а процесс оптимизации строить на основе
интерактивных программ.
Литература
1. Колосов С.В. Программирование в средеDelphi: Учеб.пособие. - Мн.:
БГУИР
. Калиткин Н.Н. Численные Методы. - М.:Наука, 1978. 512 с.
. Фленов М.Е. Библия Delphi. - 2-eизд., перераб. и доп. -
СПб.:БХВ-Петербург, 2008.-800 с.
. Мощные приборы СВЧ с дискретным взаимодействием (теория и
оптимизация)
Текст программы
{Private declarations}
{Public
declarations};:TForm;, leftmax, bottommin, bottommax:integer;:integer;
{$R
*.dfm}(x:TMas1):real;:=sqr (x[0]+2*x[1]);;TForm1. Button1Click (Sender:
TObject);, j:integer;, g:TMas1;:TMas2;:single;:TUnit2;. Lines. Clear;Chart1 do
begin. Automatic:=false;. Minimum:=-5;. Maximum:=5;. Automatic:=false;.
Minimum:=-5;
BottomAxis.
Maximum:=5;:=True;[0].Clear;;:=0.00001;(x, 2);
(g,
2);(myHmat, 2,2);
// НАЧАЛЬНЫЕ
ПЕРЕМЕННЫЕ[0]:=3;[1]:=6;:=TUnit2. Create (x, 2, eps, func, Chart1); // (массив
с перменными, количество переменных, точность, функция, TChart
график).minimizationGoldfarb; // минимизация:=ss.x1;
g:=ss.g1;:=ss. Hmat;.
Lines. Add ('минимумпри x=('+floattostrf (x[0], fffixed, 4,4)+' '+floattostrf (x[1],
fffixed, 4,4)+')');. Lines. Add ('f(x)='+floattostrf (func(x), fffixed, 4,4));.
Lines. Add ('градиент ('+floattostrf (g[0], fffixed, 4,4)+' '+floattostrf (g[1],
fffixed, 4,4)+')');
end;.
unit Unit2;, Chart;=
array of array of real;= array of real;=function (x:TMas1):real;=
class(TObject), v, u, g1, g0, Hu, x0, x1: TMas1;, num, i:integer;, Hmat, vuTH,
HuvT, vvT:TMas2;, eps, uTHu, uTv, uuT, h:real;:fun;:TChart;Create (x:TMas1;
enum:integer; meps:single; mfunc:fun; mchart:TChart);F1 (x:real):real;Grad
(x:TMas1):TMas1;(hm: TMas2): TMas2;(hm:TMas2):TMas2;mp2 (x0: real; h, e: real):
real;;;TUnit2.F1 (x:real):real;:TMas1;:integer;(tmp, num);i:=0 to num-1
do[i]:=x0 [i]+x*dk[i];:=func(tmp);;TUnit2. MakeOneMatrix (hm: TMas2): TMas2;,
j:integer;i:=0 to num-1 doj:=0 to num-1 doi=j then[i] [j]:=1[i] [j]:=0;:=hm;;TUnit2.
Grad (x:TMas1):TMas1;i:integer;, grad:TMas1;(tmp, num);(grad, num);i:=0 to
num-1 do[i]:=x[i];i:=0 to num-1 do
begin[i]:=tmp[i]+h;[i]:=func(tmp);[i]:=tmp[i] - 2*h;[i]:=(grad[i] -
func(tmp))/(2*h);;:=grad;;TUnit2.mp2 (x0: real; h, e: real): real;: boolean;,
x2, x3, y1, y2, y3, z1, z2, p, q, zm: real;
:=x0-h;:=x0;:=x0+h;:=F1
(x1);:=F1 (x2);:=F1 (x3);:=False;(y1 - (2*y2)+y3)>0 then=False do
begin:=x1-x3;:=x2-x3;:=((((y1-y3)*z2) -
((y2-y3)*z1)))/((z1*z2*(z1-z2)));:=(((y1-y3)*sqr(z2)) - ((y2-y3)*sqr(z1)))/(z1*z2*(z2-z1));:=-q/(2*p);:=x2;:=x3;:=y2;:=y3;:=x3+zm;:=F1
(x3);abs(zm)<e then:=x3+zm;:=True;;;;;TUnit2.
Create;i:integer;:=meps;:=mfunc;:=enum;:=mchart;
(g1, num);(g0, num);(dk,
num);(v, num);(u, num);(x1, num);(x0, num);(Hu, num);(Amat, num, num);(Hmat,
num, num);(vuTH, num, num);(HuvT, num, num);(vvT, num,
num);:=0.0000000000001;i:=0 to num-1 do[i]:=x[i];;TUnit2.minimizationGoldfarb;,
j:integer;, cond2:real;:=Grad(x0);i:=0 to num-1 do[i]:=-g0
[i];:=MakeOneMatrix(Hmat);:=NullMatrix(Amat);. SeriesList[0].AddXY (x0 [0], x0
[1]);:=0;:=0;(n);:=mp2 (1,0. 5,0.0000001);i:=0 to num-1 do[i]:=x0
[i]+zm*dk[i];. SeriesList[0].AddXY (x1 [0], x1 [1]);i:=0 to num-1
do[i]:=zm*dk[i];i:=0 to num-1 do[i]:=x1 [i];:=Grad(x1);i:=0 to num-1 do[i]:=g1
[i] - g0 [i];i:=0 to num-1 do[i]:=g1 [i];
//uTv=vTu:=0;i:=0 to
num-1 do:=uTv+v[i]*u[i];[0] [0]:=v[0]*u[0]*Hmat[0] [0]+v[0]*u[1]*Hmat[1]
[0];[0] [1]:=v[0]*u[0]*Hmat[0] [1]+v[0]*u[1]*Hmat[1] [1];[1]
[0]:=v[1]*u[0]*Hmat[0] [0]+v[1]*u[1]*Hmat[1] [0];[1] [1]:=v[1]*u[0]*Hmat[0] [1]+v[1]*u[1]*Hmat[1]
[1];i:=0 to num-1 doj:=0 to num-1 do[i] [j]:=0;i:=0 to num-1 doj:=0 to num-1
do[i] [j]:=-vuTH[i] [j];
// vvTi:=0 to num-1
doj:=0 to num-1 do[i] [j]:=v[i]*v[j];
i:=0 to num-1 doj:=0 to
num-1 do[i]:=Hu[i]+Hmat[i] [j]*u[j];
//HuvTi:=0 to num-1
doj:=0 to num-1 do[i] [j]:=Hu[i]*v[j]; uTHu:=(Hmat[0] [0]*u[0]+Hmat[0]
[1]*u[1])*u[0]+(Hmat[1] [0]*u[0]+Hmat[1] [1]*u[1])*u[1];:=1+uTHu/uTv;i:=0 to
num-1 doj:=0 to num-1 do[i] [j]:=vvT[i] [j]*uTHu;i:=0 to num-1 doj:=0 to num-1
do[i] [j]:=vuTH[i] [j]+HuvT[i] [j]+vvT[i] [j];i:=0 to num-1 doj:=0 to num-1
do[i] [j]:=Amat[i] [j]/uTv;
i:=0 to num-1 doj:=0 to
num-1 do[i] [j]:=Hmat[i] [j]+Amat[i] [j];i:=0 to num-1 do[i]:=0;i:=0 to num-1
doj:=0 to num-1 do[i]:=dk[i]+Hmat[i] [j]*g1 [j];i:=0 to num-1 do[i]:=-dk[i];:=0;:=0;i:=0
to num-1 do:=cond1+sqr (v[i]);i:=0 to num-1 do:=cond2+sqr (g1 [i]);:=abs
(sqrt(cond1));:=abs (sqrt(cond2));(cond1+cond2)<eps;;TUnit2. NullMatrix (hm:
TMas2): TMas2;, j:integer;i:=0 to num-1 doj:=0 to num-1 do[i] [j]:=0;:=hm;;.
Блок-схема алгоритма
оптимизация экстремум
программа алгоритм
ДА
ЦИКЛ
i=0 to num-1
НЕТ
Нет перехода