Материал из MachineLearning.
(Различия между версиями)
|
|
| Строка 111: |
Строка 111: |
| | необходимо минимизировать функцию | | необходимо минимизировать функцию |
| | ::<tex>f(x) = x_1^2 + x_2^2 + 2x_3^2 + x_4^2 - 5x_1 - 5x_2 - 21x_3 + 7x_4</tex> | | ::<tex>f(x) = x_1^2 + x_2^2 + 2x_3^2 + x_4^2 - 5x_1 - 5x_2 - 21x_3 + 7x_4</tex> |
| - | | + | со следующими ограничениями |
| | ::<tex>8-x_1^2 - x_2^2 - x_3^2 - x_4^2 - x_1 + x_2 - x_3 + x_4>0</tex> | | ::<tex>8-x_1^2 - x_2^2 - x_3^2 - x_4^2 - x_1 + x_2 - x_3 + x_4>0</tex> |
| | ::<tex> 10 -x_1^2-2x_2^2-x_3^2-2x_4^2+x_1-x_4>0</tex> | | ::<tex> 10 -x_1^2-2x_2^2-x_3^2-2x_4^2+x_1-x_4>0</tex> |
Версия 14:28, 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 и перейти к первому шагу.
Пример реализации
Рассмотрим задачу Розена-Сузуки и реализуем её решение с помощью метода штрафных функций.
Задача Розена-Сузуки заключается в следующем:
необходимо минимизировать функцию
 = x_1^2 + x_2^2 + 2x_3^2 + x_4^2 - 5x_1 - 5x_2 - 21x_3 + 7x_4)
со следующими ограничениями
Рекомендация программисту
Использование штрафных функций для решения задач связано с определенной вычислительной трудностью. Прежде всего поиск может начинаться с допустимой точки х, для которой , .Для некоторых задач находить такую точку довольно сложно. Кроме того, вследствие использования в алгоритме оптимизации дискретных шагов около границы \ge 0\})
возможен шаг, который выводит за границы допустимой области. Он приводит к уменьшению значений функции )
, т.е. к фиктивному успеху. Таким образом, нужна явная проверка допустимости каждой последующей точки, для чего на каждой итерации необходимо вычислять значения функции )
,
.
На эффективность метода барьерных функций существенно влияют выбор начального значения и метод сокращения значений в процессе минимизации, а также выбор весовых коэффициентов . Если в функции значение )
, выбирают слишком малым, то уже на начальной стадии процесса приходят к минимуму функции , который вряд ли окажется вблизи действительного условного минимума в точке 
,. С другой стороны, если значение , выбирается слишком большим, то на первых итерациях вычислительного процесса текущая точка неизбежно окажется слишком далеко за пределами допустимой области, и поиск из-за необходимости возврата в пределы допустимой области окажется весьма затяжным.
Список литературы
См. также
