III Часть : условная оптимизация функции

Постановка задачи

    Рассматривается задача условной оптимизации (нелинейного программирования) с ограничивающими неравенствами:

  

     

Моему варианту соответствует:

f(x1, x2)	gi (x1, x2) ≤ 0, i = 1, m
(х1 – 5)2 + 2(х2 – 3)2	2х1 + х2 - 6
	-2х1 + х2 - 4
	-х2 - 3

 

Данную задачу я буду решать двумя способами:

1) Сведением задачи условной оптимизации к задаче безусловной оптимизации;

2) Применяя метод прямой условной оптимизации, который непосредственно учитывает ограничения;

Метод штрафной функции

Методы «штрафных» функций характеризуются простотой реализации алгоритмов и широкими возможностями применения большинства методов безусловной оптимизации. Это достигается с помощью специальной процедуры сведения задач условной оптимизации к безусловной.

Введем в рассмотрение функцию s ( x, a ), именуемую в дальнейшем функцией «штрафа» («штрафной» функцией), со следующими свойствами.

                                                (6.3)

В идеальном случае, при a ® ¥ «штрафная» функция будет иметь вид, представленный на рис. 6.1

 

 

Гипотеза:

Предполагается, что задача ,  эквивалентна задаче безусловной оптимизации следующего вида:

 ,               (6.4)

 

X

f(x)

s(x, a), a®¥

f(x)

x

s(x, a)

¥

Рис.6.1

При наличии нескольких ограничений  , каждой из них будет соответствовать своя штрафная функция s_j ( x, a ) .

Если ввести новую функцию , то решение задачи условной минимизации (6.1), (6.2) может быть приближенно получено с помощью итеративной процедуры безусловной оптимизации:

              (6.5)

где последовательность коэффициентов a _i строится по правилу:

               (6.6)

При этом, с ростом a _i, соответствующая последовательность решений задач безусловной оптимизации будет приближаться к решению задачи условной оптимизации (6.1), (6.2):

Þ                    (6.7)

Широко используются два основных подхода к построению функций «штрафа». Для решения своей задачи я буду использовать метод внешней точки, т.к. начальная точка может не удовлетворять всех ограничениям и при этом метод внутренней точки будет неприменим.

Метод внешней точки (Метод «штрафных» функций)

Идея метода

В качестве «штрафных» функций используются зависимости, которые внутри области Х близки или равны нулю, а при удалении (во вне) от границы допустимой области вариаций параметров (аргументов) – неограниченно возрастают.

На рис. 6.3 представлены тенденции изменений итеративных решений с ростом коэффициентов a _i.

s(x, a1)

s(x, a2)

F(x, a1)

F(x, a2)

f(x)

exp

xmin x*(ai)

x

f(x)

a2> a1

X

Рис.6.3

 Штрафная функция будет иметь вид:

s_j⁽²⁾(x, a) = a [max(0, g_j(x))]²

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

 

Блок-схема метода штрафной функции (внешней точки)

 

Блоксхема метода штрафных функций

НАЧАЛО

_X1[1]: = X[1, 1]; _X1[2]: = X[1, 2]; _X2[1]: = _X1[1] + 2 * Eps; _X2[2]: = _X1[2] + 2 * Eps; alpha: = 1; Sol: = false;

        

 

 

A (((Abs(_X1[1] - _X2[1]) > Eps)or(Abs(_X1[2] - _X2[2])> Eps)) and (Sol = false))

_X2[1]: = _X1[1]; _X2[2]: = _X1[2];

(G1(_X1[1], _X1[2]) < = 0) and (G2(_X1[1]) < = 0) and (G3(_X1[2]) < = 0)

2

then

else

switcher = false

2

switcher = false

Sol: = MyProstSluchOpt.GetSolution (_X1, Eps, 0);

Sol: = MyOptGradMeth.GetSolution (_X1, Eps, alfa)

Sol: = MyProstSluchOpt.GetSolution (_X1, Eps, alfa);

Sol: = MyOptGradMeth.GetSolution (_X1, Eps, 0)

else

then

then

else

n: = n + 1;

n: = n + 1;

КОНЕЦ

switcher = false

then

else

alfa: = alfa * 2

alfa: = alfa * 5;

3

Executing: = Sol;

3

 

 

 

 

 

 

Пример работы программы при начальной точке внутри ограничений:

 

В данном примере выбрана начальная точка (0; 0), которая удовлетворяет всем ограничениям. Программа находит условный минимум целевой функции за 7 шагов методом простой градиентной оптимизации за 17 шагов модифицированным методом наилучшей пробы и сходится к значению (1.9; 2.3).

 

Пример работы программы при начальной точке вне ограничений:

 

   

В данном примере начальная точка не удовлетворяет всем ограничениям, поэтому вначале программа приходит к точке (5; 6), что является безусловным минимумом целевой функции, но после этого текущая точка перестает удовлетворять всем ограничениям и на целевую функцию налагается штраф, что приводит к “сваливанию” точки к границе одного из ограничений. Программа приходит к условному минимуму функции (1.9; 2.3) за 5 шагов методом простой градиентной оптимизации и за 16 шагов модифицированным методом наилучшей пробы.

 

Выводы:

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

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

 

Листинг основной подпрограммы:

function MSF.Executing(var X: TArg; Eps: real; var n: integer; switcher: boolean): boolean;

Var

alfa: real;

Sol: boolean;

_X1, _X2: TVector;

MyProsGrOpt: TProsGrOpt;

MyMetNaiProb: TMetNaiProb;

Begin

n: = 0;

MyProsGrOpt: = TProsGrOpt.Create;

MyMetNaiProb: = TMetNaiProb.Create;

_X1[1]: = X[1, 1]; _X1[2]: = X[1, 2]; _X2[1]: = _X1[1] + 2 * Eps; _X2[2]: = _X1[2] + 2 * Eps;

alfa: = 1;

Sol: = false;

while (((Abs(_X1[1] - _X2[1]) > Eps)or(Abs(_X1[2] - _X2[2])> Eps)) and (Sol = false)) do

begin

_X2[1]: = _X1[1]; _X2[2]: = _X1[2];

if ((G1(_X1[1], _X1[2]) < = 0) and (G2(_X1[1], _X1[2]) < = 0) and (G3(_X1[2]) < = 0)) then

begin

if (switcher = false) then Sol: = MyProsGrOpt.GetSolution(_X1, Eps, 0)

else Sol: = MyMetNaiProb.GetSolution(_X1, Eps, 0);

n: = n + 1;

end

else

begin

if (switcher = false) then Sol: = MyProsGrOpt.GetSolution(_X1, Eps, alfa)

else Sol: = MyMetNaiProb.GetSolution(_X1, Eps, alfa);

n: = n + 1;

if (switcher = false) then alfa: = alfa * 7

else alfa: = alfa * 1.6;

end;

X[n, 1]: = _X1[1]; X[n, 2]: = _X1[2];

end;

Executing: = Sol;

end;

function MSF.G1(X1, X2: real): real;

Begin

G1: = 2 * X1 + X2 - 6;

end;

function MSF.G2(X1, X2: real): real;

Begin

G2: = - 2 * X1 + X2 - 4;

end;

function MSF.G3(X2: real): real;

Begin

G3: = - X2 - 3;

end;

End.

⇐ Предыдущая123

Поделиться: