|
|
| (10 промежуточных версий не показаны.) |
| Строка 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>=0</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 R^n</tex>, для которой <tex>g_i(x^0)>0</tex>, <tex>i=\bar{1,m}</tex>, скаляр <tex>r_0</tex> и <tex>0<\betta<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\sumR(g_i(x_{k+1}))\omega_i<\epsilon</tex>, то остановиться. Решение является искомым. В противном случае положить <tex>r_{k+1}=\bettar_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)>=0</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=1}^{m}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>\tetta(r)=inf{f(x)+r\alpha(x)}</tex>.
| + | |
| - | | + | |
| - | Подход, связанный с барьерной ф
| + | |
