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

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовой работе

на тему

«Найти минимум функции 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.00001;

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)<e then

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.0000000000001;

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.0000001);

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)<eps;

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 to num-1

НЕТ

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

Нет перехода

Размещено на Allbest.ru