Найти минимум функции n переменных методом Гольдфарба

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к курсовой работе на тему

«Найти минимум функции n переменных методом Гольдфарба»

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

1) Методы оптимизации классифицируют в соответствии с задачами оптимизации:

Локальные методы: сходятся к какому-нибудь локальному экстремуму целевой функции. В случае унимодальной целевой функции, этот экстремум единственен, и будет глобальным максимумом / минимумом.

2) Глобальные методы: имеют дело с многоэкстремальными целевыми функциями. При глобальном поиске основной задачей является выявление тенденций глобального поведения целевой функции.

По критерию размерности допустимого множества, методы оптимизации делят на методы одномерной и многомерной оптимизации.

3) Задачи оптимизации, в которых целевая функция F () и ограничение, i = 1, …, m является линейными функциями, разрешаются так называемыми методами линейного программирования.

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

Описание алгоритмов решения поставленной задачи

В рассмотренном ниже классе методов с переменной метрикой реализована идея адаптивного управления.

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

Метод Гольдфарба Он более устойчив к ошибкам вычислений, чем ДФП

Описание тестовой задачи и результатов работы программы

Рассмотрим решение задачи при помощи данной программы.

Чтобы выполнить нашу программу мы должны поступить следующим образом:

1. Мы должны ввести значения функции, например (x[0]+2x[1])²в Unit1. Это будет выглядеть так, как представлено на рисунке 1.

Рис. 1.

2. И для того чтобы получить ответ, мы должны нажать на кнопку «Ввести». В результате появится график, это и будет наш ответ (Рис. 2.)

Рис. 2.

Ответ: Минимум x=(0,0057 -0,0029)

f (x)=0,0000

Градиент (0,0000 0,0000)

Заключение

Ш Среди методов нулевого порядка наибольшей эффективностью обладают метод Розенброка и метод НелдераМида

Ш Если же функция гладкая, т. е. имеет непрерывные производные, то наиболее эффективным себя зарекомендовали метод Гольдфарба и метод ДФП (они в 2−6 раз эффективнее по быстродействию чем метод Розенброка).

Ш На самом деле многое зависит от вида конкретной оптимизируемой функции. Особенно если количество оптимизируемых переменных больше 4−5 нужно иметь в запасе несколько разнообразных методов, а процесс оптимизации строить на основе интерактивных программ.

1. Колосов С. В. Программирование в средеDelphi: Учеб.пособие. — Мн.: БГУИР

2. Калиткин Н. Н. Численные Методы. — М.:Наука, 1978. 512 с.

3. Фленов М. Е. Библия Delphi. — 2-eизд., перераб. и доп. — СПб.:БХВ-Петербург, 2008.-800 с.

4. Мощные приборы СВЧ с дискретным взаимодействием (теория и оптимизация)

Текст программы

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ExtCtrls, TeeProcs, TeEngine, Chart, Series, ArrowCha, Math,

ComCtrls, Unit2, Grids;

type

TForm1 = class (TForm)

Memo1: TMemo;

Button1: TButton;

Chart1: TChart;

Series1: TLineSeries;

procedure Button1Click (Sender: TObject);

private

{Private declarations}

public

{Public declarations}

end;

var

Form1:TForm;

leftmin, leftmax, bottommin, bottommax: integer;

funcno:integer;

implementation

{$R *.dfm}

functionfunc (x:TMas1):real;

begin

func:=sqr (x[0]+2*x[1]);

end;

procedure TForm1. Button1Click (Sender: TObject);

vari, j: integer;

x, g: TMas1;

myHmat:TMas2;

eps:single;

ss:TUnit2;

begin

memo1. Lines. Clear;

with Chart1 do begin

LeftAxis. Automatic:=false;

LeftAxis. Minimum:=-5;

LeftAxis. Maximum:=5;

BottomAxis. Automatic:=false;

BottomAxis. Minimum:=-5;

BottomAxis. Maximum:=5;

AnimatedZoom:=True;

SeriesList[0]. Clear;

end;

eps:=0.1;

SetLength (x, 2);

SetLength (g, 2);

SetLength (myHmat, 2,2);

// НАЧАЛЬНЫЕ ПЕРЕМЕННЫЕ

x[0]: =3;

x[1]:=6;

ss:=TUnit2. Create (x, 2, eps, func, Chart1); // (массив с перменными, количество переменных, точность, функция, TChart график)

ss.minimizationGoldfarb; // минимизация

x:=ss.x1;

g:=ss.g1;

myHmat:=ss. Hmat;

memo1. Lines. Add ('минимумпри x=('+floattostrf (x[0], fffixed, 4,4)+' '+floattostrf (x[1], fffixed, 4,4)+')');

memo1. Lines. Add ('f (x)='+floattostrf (func (x), fffixed, 4,4));

memo1. Lines. Add ('градиент ('+floattostrf (g[0], fffixed, 4,4)+' '+floattostrf (g[1], fffixed, 4,4)+')');

end;

end.

unit Unit2;

interface

usesDialogs, Chart;

type

TMas2 = array of array of real;

TMas1 = array of real;

fun=function (x:TMas1):real;

TUnit2 = class (TObject)

dk, v, u, g1, g0, Hu, x0, x1: TMas1;

n, num, i: integer;

Amat, Hmat, vuTH, HuvT, vvT: TMas2;

zm, eps, uTHu, uTv, uuT, h: real;

func:fun;

chart:TChart;

constructor Create (x:TMas1; enum: integer; meps: single; mfunc: fun; mchart: TChart);

function F1 (x:real):real;

function Grad (x:TMas1):TMas1;

functionMakeOneMatrix (hm: TMas2): TMas2;

functionNullMatrix (hm:TMas2):TMas2;

function mp2 (x0: real; h, e: real): real;

procedureminimizationGoldfarb;

end;

implementation

function TUnit2. F1 (x:real):real;

var

tmp:TMas1;

i:integer;

begin

SetLength (tmp, num);

for i:=0 to num-1 do

tmp[i]: =x0 [i]+x*dk[i];

F1:=func (tmp);

end;

function TUnit2. MakeOneMatrix (hm: TMas2): TMas2;

var

i, j: integer;

begin

for i:=0 to num-1 do

for j:=0 to num-1 do

if i=j then

hm[i] [j]: =1

else

hm[i] [j]: =0;

result:=hm;

end;

function TUnit2. Grad (x:TMas1):TMas1;

var i: integer;

tmp, grad: TMas1;

begin

SetLength (tmp, num);

SetLength (grad, num);

for i:=0 to num-1 do

tmp[i]: =x[i];

for i:=0 to num-1 do begin

tmp[i]: =tmp[i]+h;

grad[i]:=func (tmp);

tmp[i]:=tmp[i] - 2*h;

grad[i]: =(grad[i] - func (tmp))/(2*h);

end;

result:=grad;

end;

function TUnit2. mp2 (x0: real; h, e: real): real;

var

comput: boolean;

x1, x2, x3, y1, y2, y3, z1, z2, p, q, zm: real;

begin

x1:=x0-h;

x2:=x0;

x3:=x0+h;

y1:=F1 (x1);

y2:=F1 (x2);

y3:=F1 (x3);

comput:=False;

if (y1 — (2*y2)+y3)>0 then

begin

whilecomput=False do begin

z1:=x1-x3;

z2:=x2-x3;

p:=((((y1-y3)*z2) — ((y2-y3)*z1)))/((z1*z2*(z1-z2)));

q:=(((y1-y3)*sqr (z2)) — ((y2-y3)*sqr (z1)))/(z1*z2*(z2-z1));

zm:=-q/(2*p);

x1:=x2;

x2:=x3;

y1:=y2;

y2:=y3;

x3:=x3+zm;

y3:=F1 (x3);

if abs (zm)

begin

result:=x3+zm;

comput:=True;

end;

end;

end;

end;

constructor TUnit2. Create;

var i: integer;

begin

eps:=meps;

func:=mfunc;

num:=enum;

chart:=mchart;

SetLength (g1, num);

SetLength (g0, num);

SetLength (dk, num);

SetLength (v, num);

SetLength (u, num);

SetLength (x1, num);

SetLength (x0, num);

SetLength (Hu, num);

SetLength (Amat, num, num);

SetLength (Hmat, num, num);

SetLength (vuTH, num, num);

SetLength (HuvT, num, num);

SetLength (vvT, num, num);

h:=0.1;

for i:=0 to num-1 do

x0 [i]: =x[i];

end;

procedure TUnit2. minimizationGoldfarb;

vari, j: integer;

cond1, cond2: real;

begin

g0:=Grad (x0);

for i:=0 to num-1 do

dk[i]: =-g0 [i];

Hmat:=MakeOneMatrix (Hmat);

Amat:=NullMatrix (Amat);

chart. SeriesList[0]. AddXY (x0 [0], x0 [1]);

zm:=0;

n:=0;

repeat

inc (n);

zm:=mp2 (1,0. 5,0.1);

for i:=0 to num-1 do

x1 [i]: =x0 [i]+zm*dk[i];

chart. SeriesList[0]. AddXY (x1 [0], x1 [1]);

for i:=0 to num-1 do

v[i]: =zm*dk[i];

for i:=0 to num-1 do

x0 [i]: =x1 [i];

g1:=Grad (x1);

for i:=0 to num-1 do

u[i]: =g1 [i] - g0 [i];

for i:=0 to num-1 do

g0 [i]: =g1 [i];

//uTv=vTu

uTv:=0;

for i:=0 to num-1 do

uTv:=uTv+v[i]*u[i];

vuTH[0] [0]: =v[0]*u[0]*Hmat[0] [0]+v[0]*u[1]*Hmat[1] [0];

vuTH[0] [1]: =v[0]*u[0]*Hmat[0] [1]+v[0]*u[1]*Hmat[1] [1];

vuTH[1] [0]: =v[1]*u[0]*Hmat[0] [0]+v[1]*u[1]*Hmat[1] [0];

vuTH[1] [1]: =v[1]*u[0]*Hmat[0] [1]+v[1]*u[1]*Hmat[1] [1];

for i:=0 to num-1 do

for j:=0 to num-1 do

Amat[i] [j]: =0;

for i:=0 to num-1 do

for j:=0 to num-1 do

vuTH[i] [j]: =-vuTH[i] [j];

// vvT

for i:=0 to num-1 do

for j:=0 to num-1 do

vvT[i] [j]: =v[i]*v[j];

for i:=0 to num-1 do

for j:=0 to num-1 do

Hu[i]: =Hu[i]+Hmat[i] [j]*u[j];

//HuvT

for i:=0 to num-1 do

for j:=0 to num-1 do

HuvT[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];

uTHu:=1+uTHu/uTv;

for i:=0 to num-1 do

for j:=0 to num-1 do

vvT[i] [j]: =vvT[i] [j]*uTHu;

for i:=0 to num-1 do

for j:=0 to num-1 do

Amat[i] [j]: =vuTH[i] [j]+HuvT[i] [j]+vvT[i] [j];

for i:=0 to num-1 do

for j:=0 to num-1 do

Amat[i] [j]: =Amat[i] [j]/uTv;

for i:=0 to num-1 do

for j:=0 to num-1 do

Hmat[i] [j]: =Hmat[i] [j]+Amat[i] [j];

for i:=0 to num-1 do

dk[i]: =0;

for i:=0 to num-1 do

for j:=0 to num-1 do

dk[i]: =dk[i]+Hmat[i] [j]*g1 [j];

for i:=0 to num-1 do

dk[i]: =-dk[i];

cond1:=0;

cond2:=0;

for i:=0 to num-1 do

cond1:=cond1+sqr (v[i]);

for i:=0 to num-1 do

cond2:=cond2+sqr (g1 [i]);

cond1:=abs (sqrt (cond1));

cond2:=abs (sqrt (cond2));

until (cond1+cond2)

end;

function TUnit2. NullMatrix (hm: TMas2): TMas2;

vari, j: integer;

begin

for i:=0 to num-1 do

for j:=0 to num-1 do

hm[i] [j]: =0;

result:=hm;

end;

end.

Блок-схема алгоритма

оптимизация экстремум программа алгоритм

ДАЦИКЛ

i=0 tonum-1

НЕТ

Возврат цикла

Нет перехода