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

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

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

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

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

z=f(x)

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

Z=f(x)+P(x)

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

минимизировать функцию z=f(x)

при ограничениях c_j(x)>0,j=1,2,\dots,m.

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

P(x)=r\sum_{j=1}^m\frac{1}{c_j(x)}

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

Тогда функция Z=\varphi(x,r) принимает вид

Z=\varphi(x,r)=f(x)+ r\sum_{j=1}^m\frac{1}{c_j(x)}.

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

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

Пусть имеется следующая задача: Минимизировать f(x) при ограничениях g_i(x)\ge0,i=\bar{1,m}.

Начальный этап Выбрать \epsilon>0 в качестве константы остановки, начальную допустимую точку x^0R^n, для которой g_i(x^0)>0, i=\bar{1,m}, скаляр r_0 и 0<\beta<1. Положить k=1 и перейти к основному этапу.

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

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

P(x,r)=f(x)+r\sum_{i=1}^mR_i(g_i(x))\omega_i минимизировать, где

r>0 - параметр, значения которого убывают с каждой итерации R_i(t) \to \infty при t \to 0; \omega_i - положительные весовые коэффициенты.

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

1) обратная функция R_i(g_i(x))=\frac{1}{g_i(x)}

2) логарифмическая функция R_i(g_i(x))=-ln(g_i(x))

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

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

Второй шаг

Если r_k\sum R(g_i(x_{k+1}))\omega_i<\epsilon, то остановиться. Решение является искомым.

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

Метод барьерных функций

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

Метод штрафных функций относится к группе методов внутренней точки, т.е. он начинает работать с допустимой точки x_0 и генерирует последовательность допустимых точек x_1,x_2,\dots,x_n. Метод барьерных функций, наоборот, относится к группе методов внешней точки, он начинает поиск с недопустимой точки и генерирует последовательность недопустимых решений, которая приближается к оптимальному решению извне допустимой области.

Пусть имеется задача минимизировать f(x) при ограничениях

g_i(x)\ge0, i=\bar{1,m}
h_i(x)=0 ,i=\bar{m+1,l}

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

\alpha(x)=\sum_{i=1}^{m}R_1(g_i(x))+ \sum_{i=m+1}^{l}R_2(h_i(x))
R_1,R_2 - непрерывные функции, которые удовлетворяют условиям:
R_1(y)=0 , если y>=0 и R_1(y)>0 , если y<0,
R_2(y)=0 , если y=0 и R_2(y)>0 , если y\not=0.

Типичными являются следующие выражения для функций R_1,R_2:

R_1(y)=(max\{0,-y\})^p,
R_2(y)=|y|^p, где р – целое положительное число.

Далее от исходной задачи переходим к задачи безусловной оптимизации вспомогательной функции: минимизировать  f(x)+r\alpha(x), где r>0 - штрафной коэффициент.

Пусть α– непрерывная функция. Обозначим \theta(r)=inf\{f(x)+r\alpha(x)\}.

Подход, связанный с барьерной функцией состоит в решении задачи вида:

максимизировать \theta(r) при ограничении r\ge0

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

Пусть имеется следующая задача:

Минимизировать f(x) при ограничениях g_i(x)\ge0,h_i(x)=0, где функции f,g_i,h_i.

Начальный этап Выбрать \epsilon>0 Выбрать начальную точку x^1, параметр штрафа r_1 и число \beta>1. Положить k=1 и перейти к основному этапу.

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

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

минимизировать

f(x)+r_k\alpha(x)=f(x)+r_k\left[\sum_{i=1}^{m}(max\{0,-g_i(x)\})^p+ \sum_{i=m+1}^{l}|h_i(x)|^p\right] , где

p>0,p - целое.

Положить x_{k+1} равным оптимальному решению задачи и перейти ко второму шагу.

Второй шаг

Если r_k\alpha(x_{k+1})<\epsilon, то остановиться.

В противном случае положить r_{k+1}=\beta r_k. Заменить k на k+1 и перейти к первому шагу.

Пример реализации

Рассмотрим задачу Розена-Сузуки и реализуем её решение с помощью метода штрафных функций. Задача Розена-Сузуки заключается в следующем: необходимо минимизировать функцию

f(x) = x_1^2 + x_2^2 + 2x_3^2 + x_4^2 - 5x_1 - 5x_2 - 21x_3 + 7x_4

со следующими ограничениями

8-x_1^2 - x_2^2 - x_3^2 - x_4^2 - x_1 + x_2 - x_3 + x_4>0
 10 -x_1^2-2x_2^2-x_3^2-2x_4^2+x_1-x_4>0
5 - 2x_1^2 - x_2^2 - x_3^2 - 2x_1 + x_2 + x_4>0

Ниже приведена таблица промежуточных результатов алгоритма.

Число итераций Значение миимизируемой функции f(x) Координаты первой точки x_1 Координаты второй точки x_2 Координаты третьей точки x_3 Координаты четвертой точки x_3
0 nfmin=-43.739500 x1=-0.010000 x2=0.990000 x3=1.990000 x4=-0.990000
10 nfmin=-43.762449 x1=-0.009498 x2=0.990302 x3=1.991304 x4=-0.990502
20 nfmin=-43.785381 x1=-0.008996 x2=0.990604 x3=1.992607 x4=-0.991004
30 nfmin=-43.808298 x1=-0.008494 x2=0.990906 x3=1.993910 x4=-0.991506
40 nfmin=-43.831199 x1=-0.007993 x2=0.991208 x3=1.995212 x4=-0.992007
50 nfmin=-43.854084 x1=-0.007491 x2=0.991509 x3=1.996514 x4=-0.992509

Оптимальную точку x^*=(0,1,2,-1) мы получаем на 114й итерации с оптимальным значением функции f(x^*)=-44

Рекомендация программисту

Использование штрафных функций для решения задач связано с определенной вычислительной трудностью. Прежде всего поиск может начинаться с допустимой точки х, для которой g_i(x)\ge0,i=\bar{1,m} .Для некоторых задач находить такую точку довольно сложно. Кроме того, вследствие использования в алгоритме оптимизации дискретных шагов около границы \{x:g_i(x)\ge 0\} возможен шаг, который выводит за границы допустимой области. Он приводит к уменьшению значений функции P(x,r_k), т.е. к фиктивному успеху. Таким образом, нужна явная проверка допустимости каждой последующей точки, для чего на каждой итерации необходимо вычислять значения функции g_i(x_k),k=1,2,\dots.

На эффективность метода барьерных функций существенно влияют выбор начального значения r_0 и метод сокращения значений в процессе минимизации, а также выбор весовых коэффициентов \omega_i. Если в функции значение P(x,r), выбирают слишком малым, то уже на начальной стадии процесса приходят к минимуму функции f(x), который вряд ли окажется вблизи действительного условного минимума в точке x^*,. С другой стороны, если значение r_0, выбирается слишком большим, то на первых итерациях вычислительного процесса текущая точка неизбежно окажется слишком далеко за пределами допустимой области, и поиск из-за необходимости возврата в пределы допустимой области окажется весьма затяжным.

Список литературы

См. также