Материал из MachineLearning.
(Различия между версиями)
Версия 13:07, 26 декабря 2008
Метод штрафных функций
Основная задача метода штрафных функций состоит в преобразовании задачи минимизации функции
)
с соответствующими ограничениями, наложенными на х, в задачу поиска минимума без ограничений функции
+P(x))
Функция )
является штрафной. Необходимо, чтобы при нарушении ограничений она «штрафовала» функцию Z будет находиться внутри области ограничений. Функция , удовлетворяющая этому условию, может быть не единственной.
Задачу минимизации можно сформулировать следующим образом:
минимизировать функцию
при ограничениях >0,j=1,2,\dots,m)
.
Функцию удобно записать следующим образом:
=r\sum_{j=1}^m\frac{1}{c_j(x)})
где r – положительная величина.
Тогда функция )
принимает вид
=f(x)+ r\sum_{j=1}^m\frac{1}{c_j(x)})
.
Если х принимает допустимые значения, т.е. значения, для которых 
, то Z принимает значения, которые больше соответствующих значений )
(истинной целевой функции данной задачи), и разность можно уменьшить за счет того, что r может быть очень малой величиной. Но если х принимает значения, которые хотя и являются допустимыми, но близки к границе области ограничений, и по крайней мере одна из функций )
близка к нулю, тогда значения функции , и следовательно значения функции Z станут очень велики. Таким образом, влияние функции состоит в создании «гребня с крутыми краями» вдоль каждой границы области ограничений. Следовательно, если поиск начнется из допустимой точки и осуществляется поиск минимума функции )
без ограничений, то минимум, конечно, будет достигаться внутри допустимой области для задачи с ограничениями. Полагая r достаточно малой величиной, для того чтобы влияние было малым в точке минимума, мы можем сделать точку минимума функции без ограничений совпадающей с точкой минимума задачи с ограничениями.
Алгоритм метода штрафных функций
Пусть имеется следующая задача:
Минимизировать при ограничениях >=0)
,
.
Начальный этап Выбрать 
в качестве константы остановки, начальную допустимую точку 
, для которой >0)
, , скаляр 
и 
. Положить k=1 и перейти к основному этапу.
Основной этап. k-я итерация.
Первый шаг. При исходной точке 
решить следующую задачу безусловной оптимизации:
=f(x)+\sum_{i=1}^mR_i(g_i(x))\omega_i)
минимизировать, где
- параметр, значения которого убывают с каждой итерации  \to \infty)
при 
; 
- положительные весовые коэффициенты.
Примерами штрафных функций являются:
1) обратная функция )=\frac{1}{g_i(x)})
2) логарифмическая функция )=-ln(g_i(x)))
Положить 
равным оптимальному решению задачи минимизации и перейти ко второму шагу.
Минимизация штрафной функцию может быть выполнена любым методом безусловной оптимизации, например, градиентным.
Второй шаг
Если )\omega_i<\epsilon)
, то остановиться. Решение является искомым. В противном случае положить 
. Изменить 
и перейти к первому шагу (k+1)-й итерации.
Метод штрафных функций относится к группе методов внутренней точки, т.е. он начинает работать с допустимой точки 
и генерирует последовательность допустимых точек 
. Метод барьерных функций, наоборот, относится к группе методов внешней точки, он начинает поиск с недопустимой точки и генерирует последовательность недопустимых решений, которая приближается к оптимальному решению извне допустимой области.
Пусть имеется задача минимизировать
при ограничениях
::,
::=0)
,
В частности, для искомых функций – ограничений целесообразно использовать барьерную функцию следующего вида:
=\sum_{i=1}^{m}R_1(g_i(x))+ \sum_{i=1}^{m}R_2(h_i(x)))
- непрерывные функции, которые удовлетворяют условиям:
=0)
, если 
и >0)
, если 
,
=0)
, если 
и >0)
, если 
.
Типичными являются следующие выражения для функций :
=(max{0,-y})^p)
, =|y|^p)
, где р – целое положительное число.
Далее от исходной задачи переходим к задачи безусловной оптимизации вспомогательной функции:
минимизировать +r\alpha(x))
,
где - штрафной коэффициент.
Пусть – непрерывная функция. Обозначим
=inf{f(x)+r\alpha(x)})
.
Подход, связанный с барьерной ф
