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

Изложение метода

Основная задача метода штрафных функций состоит в преобразовании задачи минимизации функции

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

Функция является штрафной. Необходимо, чтобы при нарушении ограничений она «штрафовала» функцию Z, т.е. увеличивала её значение.В этом случае минимум функции Z будет находиться внутри области ограничений. Функция , удовлетворяющая этому условию, может быть не единственной. Задачу минимизации можно сформулировать следующим образом:

минимизировать функцию

при ограничениях .

Функцию удобно записать следующим образом:

где r – положительная величина.

Тогда функция принимает вид

.

Если х принимает допустимые значения, т.е. значения, для которых , то Z принимает значения, которые больше соответствующих значений (истинной целевой функции данной задачи), и разность можно уменьшить за счет того, что r может быть очень малой величиной. Но если х принимает значения, которые хотя и являются допустимыми, но близки к границе области ограничений, и по крайней мере одна из функций близка к нулю, тогда значения функции , и следовательно значения функции Z станут очень велики. Таким образом, влияние функции состоит в создании «гребня с крутыми краями» вдоль каждой границы области ограничений. Следовательно, если поиск начнется из допустимой точки и осуществляется поиск минимума функции без ограничений, то минимум, конечно, будет достигаться внутри допустимой области для задачи с ограничениями. Полагая r достаточно малой величиной, для того чтобы влияние было малым в точке минимума, мы можем сделать точку минимума функции без ограничений совпадающей с точкой минимума задачи с ограничениями.

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

Пусть имеется следующая задача: Минимизировать при ограничениях , .

Начальный этап Выбрать в качестве константы остановки, начальную допустимую точку , для которой , , скаляр и . Положить k=1 и перейти к основному этапу.

Основной этап. k-я итерация.

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

минимизировать, где

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

Примерами штрафных функций являются:

1) обратная функция

2) логарифмическая функция

Положить равным оптимальному решению задачи минимизации и перейти ко второму шагу.

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

Второй шаг

Если , то остановиться. Решение является искомым.

В противном случае положить . Изменить и перейти к первому шагу (k+1)-й итерации.

 

При реализации метода мы использовали штрафную функцию 1) R=1/g(i);

Задачу безусловной оптимизации мы решали с помощью метода наискорейшего спуска, описание и анализ которого подробно рассматривается в лабораторной работе номер 2.

 

 

clc

clear

 

[x11 x22]=meshgrid([-15:0.1:15],[-15:0.1:15]);

syms x1 x2;

eps=10^(-5);

f=7*x1^2+2*x1*x2+5*x2^2-2*x1-10*x2;

z=7.*x11.^2+2.*x11.*x22+5.*x22.^2-2.*x11-10.*x22;

xx0=[5 10];

m=10000;

beta=0.5;

g1=x1+x2-6;

n=1;

k=0;

g=[g1];

plot(xx0(1),xx0(2),'o');

hold on

while(1)

plot(xx0(1),xx0(2),'.');

hold on

a=0;

for i=1:n

s=subs(g(i),[x1 x2],xx0);

if(abs(s)>=2*eps)

a=a+1/g(i);

end

end

if (a==0)

RES=xx0;

break;

end

F=f+m*a;

 

RES=method_NS(xx0,F,z,eps,g,n);

 

s=1/subs(g(i),[x1 x2],RES);

if (abs(m*s)<eps)

break;

end

 

m=m*beta;

k=k+1;

xx0=RES;

 

end

xx0

k

ff=subs(f,[x1 x2],xx0)

plot(RES(1),RES(2),'o');

 

Результаты:

Eps=10^(-5)

F=x1^2+x2^2

X0=[5 ; 10]

Xточное = [2 ; 2]

F(x)точное=8

m	x	F(x)	Time (seconds)	k
	2.000004060440634 2.000007075540867	8.000044543992551	3.575780
	2.000004717017259 2.000004719098306	8.000037744506781	5.27514
	2.000004752794619 2.000004752790486	8.000038022385597	6.380273
	2.000006127663761 2.000006127663761	8.000049021385184	9.462643
	2.000006433557238 2.000006433557238	8.000051468540686	13.098821