Участник:Айнагуль Джумабекова
Материал из MachineLearning.
(Новая: =Метод штрафных функций= Основная задача метода штрафных функций состоит в преобразовании задачи мин...) |
|||
Строка 5: | Строка 5: | ||
::<tex>Z=f(x)+P(x)</tex> | ::<tex>Z=f(x)+P(x)</tex> | ||
- | Функция <tex>P(x)</tex> является штрафной. Необходимо, чтобы при нарушении ограничений она «штрафовала» функцию Z будет находиться внутри области ограничений. Функция <tex>P(x)</tex>, удовлетворяющая этому условию, может быть не единственной. | + | Функция <tex>P(x)</tex> является штрафной. Необходимо, чтобы при нарушении ограничений она «штрафовала» функцию Z, т.е. увеличивала её значение.В этом случае минимум функции Z будет находиться внутри области ограничений. Функция <tex>P(x)</tex>, удовлетворяющая этому условию, может быть не единственной. |
Задачу минимизации можно сформулировать следующим образом: | Задачу минимизации можно сформулировать следующим образом: | ||
- | минимизировать функцию <tex>z=f(x)</tex> | + | ::минимизировать функцию <tex>z=f(x)</tex> |
при ограничениях <tex>c_j(x)>0,j=1,2,\dots,m</tex>. | при ограничениях <tex>c_j(x)>0,j=1,2,\dots,m</tex>. | ||
Строка 24: | Строка 24: | ||
Пусть имеется следующая задача: | Пусть имеется следующая задача: | ||
- | Минимизировать <tex>f(x)</tex> при ограничениях <tex>g_i(x) | + | Минимизировать <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 и перейти к основному этапу. | '''Начальный этап''' Выбрать <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 и перейти к основному этапу. | ||
Строка 61: | Строка 61: | ||
<tex>R_1,R_2</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_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 | + | <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,R_2</tex>: |
Версия 13:12, 26 декабря 2008
Метод штрафных функций
Основная задача метода штрафных функций состоит в преобразовании задачи минимизации функции
с соответствующими ограничениями, наложенными на х, в задачу поиска минимума без ограничений функции
Функция является штрафной. Необходимо, чтобы при нарушении ограничений она «штрафовала» функцию Z, т.е. увеличивала её значение.В этом случае минимум функции Z будет находиться внутри области ограничений. Функция , удовлетворяющая этому условию, может быть не единственной. Задачу минимизации можно сформулировать следующим образом:
- минимизировать функцию
при ограничениях .
Функцию удобно записать следующим образом:
где r – положительная величина.
Тогда функция принимает вид
- .
Если х принимает допустимые значения, т.е. значения, для которых , то Z принимает значения, которые больше соответствующих значений (истинной целевой функции данной задачи), и разность можно уменьшить за счет того, что r может быть очень малой величиной. Но если х принимает значения, которые хотя и являются допустимыми, но близки к границе области ограничений, и по крайней мере одна из функций близка к нулю, тогда значения функции , и следовательно значения функции Z станут очень велики. Таким образом, влияние функции состоит в создании «гребня с крутыми краями» вдоль каждой границы области ограничений. Следовательно, если поиск начнется из допустимой точки и осуществляется поиск минимума функции без ограничений, то минимум, конечно, будет достигаться внутри допустимой области для задачи с ограничениями. Полагая r достаточно малой величиной, для того чтобы влияние было малым в точке минимума, мы можем сделать точку минимума функции без ограничений совпадающей с точкой минимума задачи с ограничениями.
Алгоритм метода штрафных функций
Пусть имеется следующая задача: Минимизировать при ограничениях ,.
Начальный этап Выбрать в качестве константы остановки, начальную допустимую точку , для которой , , скаляр и . Положить k=1 и перейти к основному этапу.
Основной этап. k-я итерация.
Первый шаг. При исходной точке решить следующую задачу безусловной оптимизации:
минимизировать, где
- параметр, значения которого убывают с каждой итерации при ; - положительные весовые коэффициенты.
Примерами штрафных функций являются:
1) обратная функция
2) логарифмическая функция
Положить равным оптимальному решению задачи минимизации и перейти ко второму шагу.
Минимизация штрафной функцию может быть выполнена любым методом безусловной оптимизации, например, градиентным.
Второй шаг
Если , то остановиться. Решение является искомым. В противном случае положить . Изменить и перейти к первому шагу (k+1)-й итерации.
Метод штрафных функций относится к группе методов внутренней точки, т.е. он начинает работать с допустимой точки и генерирует последовательность допустимых точек . Метод барьерных функций, наоборот, относится к группе методов внешней точки, он начинает поиск с недопустимой точки и генерирует последовательность недопустимых решений, которая приближается к оптимальному решению извне допустимой области.
Пусть имеется задача минимизировать при ограничениях
::, :: ,
В частности, для искомых функций – ограничений целесообразно использовать барьерную функцию следующего вида:
- непрерывные функции, которые удовлетворяют условиям: , если и , если , , если и , если .
Типичными являются следующие выражения для функций : , , где р – целое положительное число. Далее от исходной задачи переходим к задачи безусловной оптимизации вспомогательной функции: минимизировать , где - штрафной коэффициент. Пусть – непрерывная функция. Обозначим .
Подход, связанный с барьерной ф