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

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

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИНФОРМАТИКИ И

РАДИОЭЛЕКТРОНИКИ

Факультет информационных технологий и управления

Кафедра вычислительных методов и программирования

Дисциплина: Основы алгоритмизации и программирования

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

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

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

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

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

Минск,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)<e then

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

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

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

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.

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



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