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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И РАДИОЭЛЕКТРОНИКИ Факультет информационных технологий и управления Кафедра вычислительных методов и программирования Дисциплина: Основы алгоритмизации и программирования ПОЯСНИТЕЛЬНАЯ ЗАПИСКА к курсовой работе на тему

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

Студент: гр.120 603 Нарчук А. С.

Руководитель: д. ф-м.н., профессор Синицын А.К.

Минск, 2012

Содержание Введение.

Описание алгоритма и решения задачи Описание тестовой задачи и результатов работы программы Заключение Литература Текст программы Приложение

Введение

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

Минимумодин из видов экстремума, наименьшее значение функции на заданном интервале.

Пусть в пространстве задана функция Говорят, что имеет локальный минимум в точке, если существует некотораяокрестность точки, в которой выполняется:

Будем полагать, что непрерывная дважды дифференцируемая функция.

Локальный минимум:

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

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

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

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

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

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

2) В противном случае имеют дело с задачей нелинейного программирования и применяют соответствующие методы. В свою очередь из них выделяют две частные задачи:

1. если и — выпуклые функции, то такую задачу называют задачей выпуклого программирования;

2. если, то имеют дело с задачей целочисленного (дискретного) программирования.

Практически все методы минимизации функции n переменных основаны на многократном повторении следующих двух действий:

1. выбор в области параметров некоторого направления спуска;

2.

спуск к минимуму вдоль выбранного направления.

Если — единичный вектор выбранного направления в точке, то уравнение прямой, проходящей через эту точку в направлении, записывается в виде:

где параметр z, соответствующий точкам на прямой (модуль z есть расстояние от текущей точки до).

Значения функции вдоль этой прямой можно описать функцией одной переменной :

Изменяя z двигаемся вдоль этой прямой, находим точку, в которой функция имеет меньшее значение, чем в точке Обычно находим минимум функции одной переменной:

Все многообразие методов минимизации функции n переменных определяется множеством способов выбора направлений и методов спуска в выбранном направлении.

Классификация методов многомерной оптимизации

1. МЕТОДЫ НУЛЕВОГО ПОРЯДКА — при выборе направления спуска требуют вычисления только значений функции (методы:Гаусса-Зейделя, Пауэлла, ДСК, Розенброка, Хука-Дживса, Нелдера-Мида).

2. МЕТОДЫ ПЕРВОГО ПОРЯДКА — требуют вычисления (точного или приближенного) градиента функции (методы: градиентный, сопряженных градиентов, Давидона-Флетчера-Пауэлла (ДФП), Флетчера-Ривса идр.).

3. МЕТОДЫ ВТОРОГО ПОРЯДКА — требуют вычисления как градиента, так и матрицы вторых производных (методы: Ньютона, Ньютона-Рафсона).

4. МЕТОДЫ С ПЕРЕМЕННОЙ МЕТРИКОЙ — занимают промежуточное место между методами 1-го и 2-го порядка.

Описание алгоритма и решение задачи Методами с переменной метрикой называется широкий класс эффективных градиентных методов, в которых направление очередного спуска вычисляется по формуле:

Н — положительно определенная симметричная матрица.

— корректирующая матрица, рассчитываемая по результатам предыдущих спусков таким образом, чтобы обеспечить сходимость:

Последовательность вычислений

1. На 1-м шаге следует положить Н0=Е

2. Делаем очередной одномерный спуск в направлении

3. Делается пересчет корректирующей матрицы

4. Если, то производится вычисление нового направления спуска Нk+1=Нk+Аk+1;

Общая схема алгоритма В 1979 г. Гринсдадт Дж. предложил общее выражение, задающее в зависимости от выбираемой произвольной симметричной матрицы М семейство методов с переменной метрикой В последствии исходя из него были предложены различные методы с переменной метрикой, наиболее эффективным зарекомендовал себя метод Гольдфарба Метод Гольдфарба:

Описание тестовой задачи и результатов работы программы Данная программа выполняет оптимизацию функции n переменных методом Гольдфарба. Тестовая задача включает в себя поиск минимума следующих функций:

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

2. func2:=10*sqr (x[0])+sqr (x[1]);

3. func3:=2*sqr (x[0])+4*sqr (x[1])+8*sqr (x[2])+2*x[0]*x[1]-x[2]*x[2]+2*x[2]+6*x[0]-7*x[2];

В программу вводятся следующие начальные условия:

1. начальные координаты точки (x).

2. эпселент.

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

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

2. func2:=10*sqr (x[0])+sqr (x[1]);

3. func3:=2*sqr (x[0])+4*sqr (x[1])+8*sqr (x[2])+2*x[0]*x[1]-x[2]*x[2]+2*x[2]+6*x[0]-7*x[2];

оптимизация минимум функция переменный

Заключение

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

· Конспект лекций д. ф-м.н., профессор Синицын А.К.

· http://www.wikipedia.org/

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

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

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

toSend = function (x:TMas1):real;

TForm1 = class (TForm)

Memo1: TMemo;

Button1: TButton;

Chart1: TChart;

Series1: TLineSeries;

StringGrid1: TStringGrid;

Edit1: TEdit;

Label1: TLabel;

RadioButton1: TRadioButton;

RadioButton2: TRadioButton;

RadioButton3: TRadioButton;

procedure Button1Click (Sender: TObject);

procedureFormCreate (Sender: TObject);

procedure RadioButton1Click (Sender: TObject);

procedure RadioButton2Click (Sender: TObject);

procedurerefreshUpperGrid ();

procedure RadioButton3Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1:TForm;

leftmin, leftmax, bottommin, bottommax: integer;

NumOfParameters: integer;

x, toset: TMas1;

fToSend:toSend;

funcno:integer;

implementation

{$R *.dfm}

function func1(x:TMas1):real;

begin

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

end;

function func2(x:TMas1):real;

begin

func2:=10*sqr (x[0])+sqr (x[1]);

end;

function func3(x:TMas1):real;

begin

func3:=2*sqr (x[0])+4*sqr (x[1])+8*sqr (x[2])+2*x[0]*x[1]-x[2]*x[2]+2*x[2]+6*x[0]-7*x[2];

end;

procedure TForm1. Button1Click (Sender: TObject);

vari, j: integer;

g:TMas1;

eps:single;

minimize:TMinimization;

begin

memo1.Lines.Clear;

withChart1 dobegin

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:=StrToFloat (Edit1.Text);

SetLength (g, 2);

memo1.Lines.Add ('Начальные переменные:');

SetLength (toset, NumOfParameters);

for i:=0 to NumOfParameters-1 do

toset[i]: =StrToFloat (StringGrid1.Cells[i, 1]);

for i:=0 to NumOfParameters-1 do

memo1.Lines.Add ('x'+IntToStr (i)+'='+FloatToStr (toset[i]));

minimize:=TMinimization.Create (toset, 2, eps, fToSend, Chart1);

minimize.minimizationGoldfarb;

x:=minimize.GetFinalPoint;

g:=minimize.GetFinalGradient;

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

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

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

minimize.Free;

end;

procedure TForm1. FormCreate (Sender: TObject);

var

i:integer;

begin

StringGrid1.RowCount:=2;

RadioButton1.Checked:=True;

RadioButton1Click (Sender);

end;

procedure TForm1. RadioButton1Click (Sender: TObject);

var

i:integer;

begin

fToSend:=func1;

NumOfParameters:=2;

SetLength (x, 2);

x[0]: =3;

x[1]:=6;

refreshUpperGrid;

end;

procedure TForm1. RadioButton2Click (Sender: TObject);

var

i:integer;

begin

fToSend:= func2;

NumOfParameters:=2;

SetLength (x, 2);

x[0]: =5;

x[1]:=7;

refreshUpperGrid;

end;

procedure TForm1. RadioButton3Click (Sender: TObject);

begin

fToSend:= func3;

NumOfParameters:=3;

SetLength (x, 3);

x[0]: =0.2;

x[1]:=0.2;

x[2]:=0.5;

refreshUpperGrid;

end;

procedure TForm1. refreshUpperGrid;

var

i:integer;

begin

StringGrid1.ColCount:=NumOfParameters;

Chart1.SeriesList[0]. Clear;

memo1.Clear;

for i:=0 to NumOfParameters-1 do

StringGrid1.Cells[i, 0]: ='x'+IntToStr (i);

for i:=0 to NumOfParameters-1 do

StringGrid1.Cells[i, 1]: =FloatToStr (x[i]);

end;

end.

unit Unit2;

interface

usesDialogs, Chart;

type

TMas2 = array of array of real;

TMas1 = array of real;

fun=function (x:TMas1):real;

TMinimization = 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;

functionGrad (x:TMas1):TMas1;

functionMakeOneMatrix (hm: TMas2): TMas2;

functionNullMatrix (hm:TMas2):TMas2;

functionmp2(x0: real;h, e: real): real;// функциявыполняетпоискминимума

functionGetFinalPoint (): TMas1;

functionGetFinalGradient (): TMas1;

procedureminimizationGoldfarb;

end;

implementation

function TMinimization. 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;

functionTMinimization.GetFinalPoint (): TMas1;

begin

GetFinalPoint:=x1;

end;

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

functionTMinimization.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 TMinimization. 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;

constructorTMinimization.Create;

var i: integer;

begin

eps:=meps;

func:=mfunc;

num:=enum;

chart:=mchart;

// функция SetLength устанавливает размер динамического массива

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;

procedureTMinimization.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];

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

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

//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;

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

functionTMinimization.GetFinalGradient: TMas1;

begin

GetFinalGradient:=g1;

end;

end.

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