Материал из MachineLearning.
(Различия между версиями)
|
|
| Строка 84: |
Строка 84: |
| | | | |
| | Пусть имеется следующая задача: | | Пусть имеется следующая задача: |
| | + | |
| | Минимизировать <tex>f(x)</tex> при ограничениях <tex>g_i(x)\ge0</tex>,<tex>h_i(x)=0</tex>, где функции <tex>f,g_i,h_i</tex>. | | Минимизировать <tex>f(x)</tex> при ограничениях <tex>g_i(x)\ge0</tex>,<tex>h_i(x)=0</tex>, где функции <tex>f,g_i,h_i</tex>. |
| | | | |
Версия 13:54, 26 декабря 2008
Метод штрафных функций
Изложение метода
Основная задача метода штрафных функций состоит в преобразовании задачи минимизации функции
)
с соответствующими ограничениями, наложенными на х, в задачу поиска минимума без ограничений функции
+P(x))
Функция )
является штрафной. Необходимо, чтобы при нарушении ограничений она «штрафовала» функцию Z, т.е. увеличивала её значение.В этом случае минимум функции 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 достаточно малой величиной, для того чтобы влияние было малым в точке минимума, мы можем сделать точку минимума функции без ограничений совпадающей с точкой минимума задачи с ограничениями.
Алгоритм метода штрафных функций
Пусть имеется следующая задача:
Минимизировать при ограничениях \ge0)
,
.
Начальный этап Выбрать 
в качестве константы остановки, начальную допустимую точку 
∈
, для которой >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=m+1}^{l}R_2(h_i(x)))
- непрерывные функции, которые удовлетворяют условиям:
=0)
, если 
и >0)
, если 
,
=0)
, если 
и >0)
, если 
.
Типичными являются следующие выражения для функций :
=(max\{0,-y\})^p)
,
=|y|^p)
, где р – целое положительное число.
Далее от исходной задачи переходим к задачи безусловной оптимизации вспомогательной функции:
минимизировать +r\alpha(x))
,
где - штрафной коэффициент.
Пусть α– непрерывная функция. Обозначим
=inf\{f(x)+r\alpha(x)\})
.
Подход, связанный с барьерной функцией состоит в решении задачи вида:
- максимизировать
)
при ограничении 
Алгоритм метода барьерных функций
Пусть имеется следующая задача:
Минимизировать при ограничениях ,, где функции 
.
Начальный этап Выбрать Выбрать начальную точку 
, параметр штрафа 
и число 
. Положить k=1 и перейти к основному этапу.
Основной этап. 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]](../mimetex/?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 - целое.
Положить равным оптимальному решению задачи и перейти ко второму шагу.
Второй шаг
Если <\epsilon)
, то остановиться.
В противном случае положить . Заменить k на k+1 и перейти к первому шагу.
