Лабораторная работа №7. Решение задачи           безусловной оптимизации функций многих переменных

Требуется найти минимум заданной функции многих переменных методами циклического покоординатного спуска и наискорейшего спуска.

Пример.

Пусть задана функция двух переменных , которую необходимо минимизировать с заданной точностью ε=0.001.

6.7.1 Метод циклического покоординатного спуска

Метод реализован в модуле Pokoord_Spusk.pas в функции Function Spusk (E: Real): Real.

Описание типов.

- FType = Function (x: Real): Extended - хранит функцию;

- Point = Array of Real – хранит значения всех переменных;

- MainFunction = Function (P: Point): Extended – целевая функция;

- TGran = Array of Array [1..2] of Real – для хранения границ минимизации каждой переменной.

Используемые глобальные переменные:

- CurrentVar: Integer – содержит номер текущей переменной, по которой производится минимизация;

- P: Point – хранит текущее значение всех переменных;

- Gran: TGran – хранит границы всех переменных;

- FMain: MainFunction – хранит основную функцию;

- IterCount: Integer – хранит количество итераций.

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

unit Pokoord_Spusk;

{***************************************************************

До запуска функции поиска нужно в массив функций f занести все функции по каждой переменной,

в переменную P внести значение начальной точки, а также задать границы

для каждой переменной.

Главная функция определяется в вызывающем модуле и записывается

в виде "sqr(p[0])+sqr(p[1])", что соответствует функции (x1)^2 + (x2)^2 (предполагается что в массиве P хранятся переменные x1 и x2)

***************************************************************}

interface

uses Ravnomer_Search;

Type FType = Function(x : Real) : Extended; //Объявляется

                                                                    //функциональный тип

Point = Array of Real; //Тип массив значений всех переменных

MainFunction = Function(P : Point) : Extended; //Главная функция

TGran = Array of Array [1..2] of Real;

Var CurrentVar : Integer;

P : Point; //Текущая точка

Gran : TGran;

FMain : MainFunction;

IterCount : Integer;

Function Spusk(E : Real) : Real;

         //E - заданная точность

         //FMain - передается главная функция как параметр

    implementation

    Function NormaV(P1,P2 : Point) : Real; //Нахождение нормы ветора,

                                               //заданного разницей векторов P1 и P2

Var I : Integer;

Begin

Result:=abs(P1[0]-P2[0]);

For I:=1 to High(P1) do If abs(P1[I]-P2[I])>Result Then Result:=abs(P1[I]-P2[I]);

End;

     Function Current(x : Real) : Extended;//Функция от конкретной

                                                                   // переменной

Var PTemp : Point;

Begin

SetLength(PTemp,High(P)+1);

PTemp:=Copy(P);

PTemp[CurrentVar]:=P[CurrentVar]+x;

Result:=FMain(PTemp);

End;

    Function Spusk;//Поиск минимума главной функции

var I,J : Integer;

Neisv : Point; //Массив поправок

FSub : FType; //Подфункция. Хранит функцию от конкретной

                       // переменной

Res : Byte; //Результат поиска минимум функции от конкретной

                    // переменной

Begin

SetLength(Neisv,High(P)+1);

For I:=0 to High(P) do //Перебор всех переменных

Begin

CurrentVar:=I;//Установка текущей переменной

FSub:=Current;//Установка текущей функции

Neisv[I]:=Search(Gran[i][1],Gran[i][2],100,FSub,Res,E);//Вычисление

                               // минимума функции конкретной переменной

Neisv[I]:=P[I]+Neisv[I];//Установка новой текущей точки

End;

IterCount:=1;

While NormaV(P,Neisv)>E do//Пока не достигнута нужная точность

Begin

For I:=0 to High(P) do//Перебор по всем переменным

Begin

For J:=0 to High(P) do P[J]:=Neisv[J];//Переход к новой точке

CurrentVar:=I;

FSub:=Current;

Neisv[I]:=Search(gran[i][1],gran[i][2],100,FSub,Res,E);

Neisv[I]:=P[I]+Neisv[I];

End;

Inc(IterCount); 

End;

    Result:=FMain(Neisv);//Вычисление значения главной функции

                                         // в точке минимума

End;

    end.

Результат работы программы.

      Наименьшее значение функция достигает в точке  , .

6.7.2 Метод наискорейшего спуска

Метод реализован в модуле Naiskor_Spusk.pas в функции Function Spusk (E: Real): Real.

Описание типов.

- FType = Function(x : Real) : Extended - хранит функцию;

- Point = Array of Real – хранит значения всех переменных;

- MainFunction = Function(P : Point) : Extended – целевая функция;

- TGran = Array of Array [1..2] of Real – для хранения границ минимизации каждой переменной;

- TFunction = Array of FType – содержит производные по всем переменным.

Используемые глобальные переменные:

- CurrentVar : Integer – содержит номер текущей переменной, по которой производится минимизация;

- FPr : TFunction – хранит все производные;

- P : Point – хранит текущее значение всех переменных;

- Gran : TGran – хранит границы всех переменных;

- Grad : Point – вектор-градент;

- FMain : MainFunction – хранит основную функцию;

- IterCount : Integer хранит количество итераций.

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

unit Naiskor_spusk;

{***************************************************************

До запуска функции поиска нужно в массив функций f занести все функции по каждой переменной,

в переменную FPr внести производные по каждой переменной,

в переменную P внести значение начальной точки,

а также задать границы для каждой переменной.

Главная функция определяется в вызывающем модуле и записывается в виде

 "sqr(p[0])+sqr(p[1])", что соответствует функции (x1)^2 + (x2)^2

***************************************************************}

interface

uses Ravnomer_Search;

Type

Point = Array of Extended; //Тип массив значений всех переменных

FType = Function(x : Real) : Extended; //Объявляется функциональный

                                                                 // тип

TFunction = Array of FType; //Тип массив функций.

                                               // Хранит функции от каждой переменной

MainFunction = Function(P : Point) : Extended; //Главная функция

TGran = Array of Array [1..2] of Real;

Var CurrentVar : Integer;

FPr : TFunction;//Содержит производные по каждой переменной

P : Point; //Текущая точка

Gran : TGran; //Границы

grad : Point; //Градиентный вектор

FMain : MainFunction;

IterCount : Integer;

Function Spusk(E : Real) : Real;

         //E - заданная точность

         //FMain - передается главная функция как параметр

implementation

Function NormaV(P1,P2 : Point) : Real; //Нахождение нормы ветора,

                                  //заданного разницей векторов P1 и P2

Var I : Integer;

Begin

Result:=abs(P1[0]-P2[0]);

For I:=1 to High(P1) do If abs(P1[I]-P2[I])>Result Then Result:=abs(P1[I]-P2[I]);

End;

Function Current(x : Real) : Extended;//Функция от конкретной переменной

Var PTemp : Point;

Begin

SetLength(PTemp,High(P)+1);

PTemp:=Copy(P);

PTemp[CurrentVar]:=P[CurrentVar]+x*Grad[CurrentVar];

Result:=FMain(PTemp);

End;

Function Spusk;//Поиск минимума главной функции

var I,J : Integer;

Neisv : Point; //Массив поправок

FSub : FType; //Подфункция. Хранит функцию от конкретной

                        //переменной

Res : Byte; //Результат поиска минимума функции от конкретной

                    // переменной

Begin

For I:=0 to High(P) do

Begin

Grad[I]:=-FPr[I](P[I]); //Нахождение вектора градиентов

End;

SetLength(Neisv,High(P)+1);

For I:=0 to High(P) do //Перебор всех переменных

Begin

CurrentVar:=I;//Установка текущей переменной

FSub:=Current;//Установка текущей функции

Neisv[I]:=Search(Gran[i][1],Gran[i][2],100,FSub,Res,E);//Вычисление минимум функции конкретной переменной

Neisv[I]:=P[I]+Grad[I]*Neisv[I];//Установка новой текущей точки

End;

IterCount:=1;

While NormaV(P,Neisv)>E do//Пока не достигнута нужная точность делать...

Begin

For I:=0 to High(P) do//Перебор по всем переменным

Begin

For J:=0 to High(P) do P[J]:=Neisv[J];//Переход к новой точке

CurrentVar:=I;

FSub:=Current;

Neisv[I]:=Search(Gran[i][1],gran[i][2],100,FSub,Res,E);

Neisv[I]:=P[I]+Grad[I]*Neisv[I];

End;

Inc(IterCount); 

End;

Result:=FMain(Neisv);//Вычисление значения главной функции

                                // в точке минимума

End;

end.

Результат работы программы.

Наименьшее значение функция достигает в точке , .

Варианты заданий

1.

2.

3.

4.

5.

6.  

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

21.

22.

23.

24.

25.

26.

27.

28.

29.

30.