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

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

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

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

Текущая версия

Содержание

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)+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$

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

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

См. также

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

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%88%D1%82%D1%80%D0%B0%D1%84%D0%BD%D1%8B%D1%85_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B9»

Категория: Численные методы условной оптимизации

@@ Строка 33: / Строка 33: @@
 '''Первый шаг'''. При исходной точке <tex>x_k</tex> решить следующую задачу безусловной оптимизации:
-<tex>P(x,r)=f(x)+\sum_{i=1}^mR_i(g_i(x))\omega_i</tex> минимизировать, где
+<tex>P(x,r)=f(x)+r\sum_{i=1}^mR_i(g_i(x))\omega_i</tex> минимизировать, где
 <tex>r>0</tex> - параметр, значения которого убывают с каждой итерации <tex>R_i(t) \to \infty</tex> при <tex>t \to 0</tex>; <tex>\omega_i</tex> - положительные весовые коэффициенты.

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

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

Текущая версия

Содержание

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

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

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

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

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

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

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

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

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

См. также

Просмотры

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

Навигация

Поиск

Инструменты