Участник:Айнагуль Джумабекова

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

(Различия между версиями)

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

Версия 14:27, 26 декабря 2008

Содержание

[убрать]

1 Метод штрафных функций
- 1.1 Изложение метода
- 1.2 Алгоритм метода штрафных функций
2 Метод барьерных функций
- 2.1 Изложение метода
- 2.2 Алгоритм метода барьерных функций
3 Пример реализации
4 Рекомендация программисту
5 Список литературы
6 См. также

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

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

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

$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^0$ ∈ $R^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)+\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$

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

Банди Б. Методы Оптимизации. Вводный курс. М.: Радио и связь, 1988.
http://iasa.org.ua/iso?lang=eng&ch=6&sub=8

См. также

Практикум ММП ВМК, 4й курс, осень 2008

Источник — «http://poligon.machinelearning.ru/wiki/index.php?title=%D0%A3%D1%87%D0%B0%D1%81%D1%82%D0%BD%D0%B8%D0%BA:%D0%90%D0%B9%D0%BD%D0%B0%D0%B3%D1%83%D0%BB%D1%8C_%D0%94%D0%B6%D1%83%D0%BC%D0%B0%D0%B1%D0%B5%D0%BA%D0%BE%D0%B2%D0%B0»

@@ Строка 116: / Строка 116: @@
 ::<tex>5 - 2x_1^2 - x_2^2 - x_3^2 - 2x_1 + x_2 + x_4>0</tex>
-==Памятка программисту==
+==Рекомендация программисту==
 Использование штрафных функций для решения задач связано с определенной вычислительной трудностью. Прежде всего поиск может начинаться с допустимой точки х, для которой <tex>g_i(x)\ge0</tex>,<tex>i=\bar{1,m}</tex> .Для некоторых задач находить такую точку довольно сложно. Кроме того, вследствие использования в алгоритме оптимизации  дискретных шагов около границы <tex>\{x:g_i(x)\ge 0\}</tex> возможен шаг, который выводит за границы допустимой области. Он приводит к уменьшению значений функции <tex>P(x,r_k)</tex>, т.е. к фиктивному успеху. Таким образом, нужна явная проверка допустимости каждой последующей точки, для чего на каждой итерации необходимо вычислять значения функции <tex>g_i(x_k)</tex>,<tex>k=1,2,\dots</tex>.
 На эффективность метода барьерных функций существенно влияют выбор начального значения <tex>r_0</tex> и метод сокращения значений в процессе минимизации, а также выбор весовых коэффициентов <tex>\omega_i</tex>. Если в функции значение <tex>P(x,r)</tex>, выбирают слишком малым, то уже на начальной стадии процесса приходят к минимуму функции <tex>f(x)</tex>, который вряд ли окажется вблизи действительного условного минимума в точке <tex>x^*</tex>,. С другой стороны, если значение <tex>r_0</tex>,  выбирается слишком большим, то на первых итерациях вычислительного процесса текущая точка неизбежно окажется слишком далеко за пределами допустимой области, и поиск из-за необходимости возврата в пределы допустимой области окажется весьма затяжным.
+== Список литературы ==
+* ''Банди Б.''&nbsp; Методы Оптимизации. Вводный курс. М.: Радио и связь, 1988.
+* http://iasa.org.ua/iso?lang=eng&ch=6&sub=8
+== См. также ==
+*[[Практикум ММП ВМК, 4й курс, осень 2008]]

Участник:Айнагуль Джумабекова

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

Версия 14:27, 26 декабря 2008

Содержание

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

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

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

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

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

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

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

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

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

См. также

Просмотры

Личные инструменты

Навигация

Поиск

Инструменты