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

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

(Различия между версиями)
Перейти к: навигация, поиск
 
(1 промежуточная версия не показана)
Строка 1: Строка 1:
-
==Метод штрафных функций==
+
Джумабекова Айнагуль, [[МГУ]], факультет [[ВМК]], кафедра [[ММП]], группа 517
-
===Изложение метода===
+
-
Основная задача метода штрафных функций состоит в преобразовании задачи минимизации функции
+
-
::<tex>z=f(x)</tex>
+
-
с соответствующими ограничениями, наложенными на х, в задачу поиска минимума без ограничений функции
+
-
::<tex>Z=f(x)+P(x)</tex>
+
-
 
+
-
Функция <tex>P(x)</tex> является штрафной. Необходимо, чтобы при нарушении ограничений она «штрафовала» функцию Z, т.е. увеличивала её значение.В этом случае минимум функции Z будет находиться внутри области ограничений. Функция <tex>P(x)</tex>, удовлетворяющая этому условию, может быть не единственной.
+
-
Задачу минимизации можно сформулировать следующим образом:
+
-
::минимизировать функцию <tex>z=f(x)</tex>
+
-
при ограничениях <tex>c_j(x)>0,j=1,2,\dots,m</tex>.
+
-
 
+
-
Функцию <tex>P(x)</tex> удобно записать следующим образом:
+
-
 
+
-
::<tex>P(x)=r\sum_{j=1}^m\frac{1}{c_j(x)}</tex>
+
-
где r – положительная величина.
+
-
 
+
-
Тогда функция <tex>Z=\varphi(x,r)</tex> принимает вид
+
-
 
+
-
::<tex>Z=\varphi(x,r)=f(x)+ r\sum_{j=1}^m\frac{1}{c_j(x)}</tex>.
+
-
 
+
-
Если х принимает допустимые значения, т.е. значения, для которых <tex>c_j\ge0</tex>, то Z принимает значения, которые больше соответствующих значений <tex>f(x)</tex> (истинной целевой функции данной задачи), и разность можно уменьшить за счет того, что r может быть очень малой величиной. Но если х принимает значения, которые хотя и являются допустимыми, но близки к границе области ограничений, и по крайней мере одна из функций <tex>c_j(x)</tex> близка к нулю, тогда значения функции <tex>P(x)</tex>, и следовательно значения функции Z станут очень велики. Таким образом, влияние функции <tex>P(x)</tex> состоит в создании «гребня с крутыми краями» вдоль каждой границы области ограничений. Следовательно, если поиск начнется из допустимой точки и осуществляется поиск минимума функции <tex>\varphi(x,r)</tex> без ограничений, то минимум, конечно, будет достигаться внутри допустимой области для задачи с ограничениями. Полагая r достаточно малой величиной, для того чтобы влияние <tex>P(x)</tex> было малым в точке минимума, мы можем сделать точку минимума функции <tex>\varphi(x,r)</tex>без ограничений совпадающей с точкой минимума задачи с ограничениями.
+
-
 
+
-
===Алгоритм метода штрафных функций===
+
-
 
+
-
Пусть имеется следующая задача:
+
-
Минимизировать <tex>f(x)</tex> при ограничениях <tex>g_i(x)\ge0</tex>,<tex>i=\bar{1,m}</tex>.
+
-
 
+
-
'''Начальный этап''' Выбрать <tex>\epsilon>0</tex> в качестве константы остановки, начальную допустимую точку <tex>x^0</tex>∈<tex>R^n</tex>, для которой <tex>g_i(x^0)>0</tex>, <tex>i=\bar{1,m}</tex>, скаляр <tex>r_0</tex> и <tex>0<\beta<1</tex>. Положить k=1 и перейти к основному этапу.
+
-
 
+
-
'''Основной этап'''. ''k-я итерация''.
+
-
 
+
-
'''Первый шаг'''. При исходной точке <tex>x_k</tex> решить следующую задачу безусловной оптимизации:
+
-
 
+
-
<tex>P(x,r)=f(x)+\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> - положительные весовые коэффициенты.
+
-
 
+
-
Примерами штрафных функций являются:
+
-
 
+
-
1) обратная функция <tex>R_i(g_i(x))=\frac{1}{g_i(x)}</tex>
+
-
 
+
-
2) логарифмическая функция <tex>R_i(g_i(x))=-ln(g_i(x))</tex>
+
-
+
-
Положить <tex>x_{k+1}</tex> равным оптимальному решению задачи минимизации и перейти ко второму шагу.
+
-
 
+
-
Минимизация штрафной функцию может быть выполнена любым методом безусловной оптимизации, например, градиентным.
+
-
 
+
-
'''Второй шаг'''
+
-
 
+
-
Если <tex>r_k\sum R(g_i(x_{k+1}))\omega_i<\epsilon</tex>, то остановиться. Решение является искомым.
+
-
 
+
-
В противном случае положить <tex>r_{k+1}=\beta r_k</tex>. Изменить <tex>k=k+1</tex> и перейти к первому шагу (k+1)-й итерации.
+
-
 
+
-
==Метод барьерных функций==
+
-
===Изложение метода===
+
-
Метод штрафных функций относится к группе методов внутренней точки, т.е. он начинает работать с допустимой точки <tex>x_0</tex> и генерирует последовательность допустимых точек <tex>x_1,x_2,\dots,x_n</tex>. Метод барьерных функций, наоборот, относится к группе методов внешней точки, он начинает поиск с недопустимой точки и генерирует последовательность недопустимых решений, которая приближается к оптимальному решению извне допустимой области.
+
-
 
+
-
Пусть имеется задача минимизировать <tex>f(x)</tex>
+
-
при ограничениях
+
-
::<tex>g_i(x)\ge0</tex>, <tex>i=\bar{1,m}</tex>
+
-
::<tex>h_i(x)=0</tex> ,<tex>i=\bar{m+1,l}</tex>
+
-
 
+
-
В частности, для искомых функций – ограничений целесообразно использовать барьерную функцию следующего вида:
+
-
::<tex>\alpha(x)=\sum_{i=1}^{m}R_1(g_i(x))+ \sum_{i=m+1}^{l}R_2(h_i(x))</tex>
+
-
::<tex>R_1,R_2</tex> - непрерывные функции, которые удовлетворяют условиям:
+
-
::<tex>R_1(y)=0</tex> , если <tex>y>=0</tex> и <tex>R_1(y)>0</tex> , если <tex>y<0</tex>,
+
-
::<tex>R_2(y)=0</tex> , если <tex>y=0</tex> и <tex>R_2(y)>0</tex> , если <tex>y\not=0</tex>.
+
-
 
+
-
Типичными являются следующие выражения для функций <tex>R_1,R_2</tex>:
+
-
::<tex>R_1(y)=(max\{0,-y\})^p</tex>,
+
-
::<tex>R_2(y)=|y|^p</tex>, где р – целое положительное число.
+
-
Далее от исходной задачи переходим к задачи безусловной оптимизации вспомогательной функции:
+
-
минимизировать <tex> f(x)+r\alpha(x)</tex>,
+
-
где <tex>r>0</tex> - штрафной коэффициент.
+
-
 
+
-
Пусть α– непрерывная функция. Обозначим
+
-
<tex>\theta(r)=inf\{f(x)+r\alpha(x)\}</tex>.
+
-
 
+
-
Подход, связанный с барьерной функцией состоит в решении задачи вида:
+
-
::максимизировать <tex>\theta(r)</tex> при ограничении <tex>r\ge0</tex>
+
-
 
+
-
===Алгоритм метода барьерных функций===
+
-
 
+
-
Пусть имеется следующая задача:
+
-
 
+
-
Минимизировать <tex>f(x)</tex> при ограничениях <tex>g_i(x)\ge0</tex>,<tex>h_i(x)=0</tex>, где функции <tex>f,g_i,h_i</tex>.
+
-
 
+
-
'''Начальный этап''' Выбрать <tex>\epsilon>0</tex> Выбрать начальную точку <tex>x^1</tex>, параметр штрафа <tex>r_1</tex> и число <tex>\beta>1</tex>. Положить k=1 и перейти к основному этапу.
+
-
 
+
-
'''Основной этап'''. ''k-я итерация''.
+
-
 
+
-
'''Первый шаг'''. При начальной точке <tex>x_k</tex> и параметре штрафа <tex>r_k</tex>решить следующую задачу:
+
-
 
+
-
минимизировать
+
-
::<tex>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]</tex> , где
+
-
+
-
<tex>p>0</tex>,p - целое.
+
-
 
+
-
Положить <tex>x_{k+1}</tex> равным оптимальному решению задачи и перейти ко второму шагу.
+
-
 
+
-
'''Второй шаг'''
+
-
 
+
-
Если <tex>r_k\alpha(x_{k+1})<\epsilon</tex>, то остановиться.
+
-
 
+
-
В противном случае положить <tex>r_{k+1}=\beta r_k</tex>. Заменить k на k+1 и перейти к первому шагу.
+
-
 
+
-
==Пример реализации==
+
-
Рассмотрим задачу Розена-Сузуки и реализуем её решение с помощью метода штрафных функций.
+
-
Задача Розена-Сузуки заключается в следующем:
+
-
необходимо минимизировать функцию
+
-
::<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> 10 -x_1^2-2x_2^2-x_3^2-2x_4^2+x_1-x_4>0</tex>
+
-
::<tex>5 - 2x_1^2 - x_2^2 - x_3^2 - 2x_1 + x_2 + x_4>0</tex>
+
-
 
+
-
Ниже приведена таблица промежуточных результатов алгоритма.
+
-
{| class="wikitable"
+
-
|-
+
-
! Число итераций
+
-
! Значение миимизируемой функции <tex>f(x)</tex>
+
-
! Координаты первой точки <tex>x_1</tex>
+
-
! Координаты второй точки <tex>x_2</tex>
+
-
! Координаты третьей точки <tex>x_3</tex>
+
-
! Координаты четвертой точки <tex>x_3</tex>
+
-
|-
+
-
| 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
+
-
|}
+
-
Оптимальную точку <tex>x^*=(0,1,2,-1)</tex> мы получаем на 114й итерации с оптимальным значением функции <tex>f(x^*)=-44</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]]
+

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

Джумабекова Айнагуль, МГУ, факультет ВМК, кафедра ММП, группа 517

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