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

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

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

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

Версия 13:52, 26 декабря 2008

Содержание

1 Метод штрафных функций
- 1.1 Изложение метода
- 1.2 Алгоритм метода штрафных функций
2 Метод барьерных функций
- 2.1 Изложение метода
- 2.2 Алгоритм метода барьерных функций

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

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

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

$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 и перейти к первому шагу.

Источник — «http://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»

@@ Строка 1: / Строка 1: @@
 ==Метод штрафных функций==
+===Изложение метода===
 Основная задача метода штрафных функций состоит в преобразовании задачи минимизации функции
 ::<tex>z=f(x)</tex>
@@ Строка 53: / Строка 54: @@
 ==Метод барьерных функций==
+===Изложение метода===
 Метод штрафных функций относится к группе методов внутренней точки, т.е. он начинает работать с допустимой точки <tex>x_0</tex> и генерирует последовательность допустимых точек  <tex>x_1,x_2,\dots,x_n</tex>. Метод барьерных функций, наоборот, относится к группе методов внешней точки, он начинает поиск с недопустимой точки и генерирует последовательность недопустимых решений, которая приближается к оптимальному решению извне допустимой области.
@@ Строка 84: / Строка 86: @@
 Минимизировать <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>, параметр штрафа <tex>r_1</tex> и число  <tex>\beta>1</tex>. Положить k=1 и перейти к основному этапу.
+'''Начальный этап''' Выбрать <tex>\epsilon>0</tex> Выбрать начальную точку <tex>x^1</tex>, параметр штрафа <tex>r_1</tex> и число  <tex>\beta>1</tex>. Положить k=1 и перейти к основному этапу.
 '''Основной этап'''. ''k-я итерация''.
@@ Строка 91: / Строка 93: @@
 минимизировать
-::<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</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>r>0</tex> - параметр, значения которого убывают с каждой итерации <tex>R_i(t) \to \infty</tex> при <tex>t \to 0</tex>; <tex>\omega_i</tex> - положительные весовые коэффициенты.
+<tex>p>0</tex>,p - целое.
-Примерами штрафных функций являются:
+Положить <tex>x_{k+1}</tex> равным оптимальному решению задачи и перейти ко второму шагу.
-) обратная функция <tex>R_i(g_i(x))=\frac{1}{g_i(x)}</tex>
-) логарифмическая функция <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\alpha(x_{k+1})<\epsilon</tex>, то остановиться.
-В противном случае положить <tex>r_{k+1}=\beta r_k</tex>. Изменить <tex>k=k+1</tex> и перейти к первому шагу (k+1)-й итерации.
+В противном случае положить <tex>r_{k+1}=\beta r_k</tex>. Заменить k на k+1 и перейти к первому шагу.

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

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

Версия 13:52, 26 декабря 2008

Содержание

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

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

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

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

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

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

Просмотры

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

Навигация

Поиск

Инструменты