Участник:Айнагуль Джумабекова
Материал из MachineLearning.
Айнагуль Джумабекова (Обсуждение | вклад)
(Новая: =Метод штрафных функций= Основная задача метода штрафных функций состоит в преобразовании задачи мин...)
К следующему изменению →
Версия 13:07, 26 декабря 2008
Метод штрафных функций
Основная задача метода штрафных функций состоит в преобразовании задачи минимизации функции
с соответствующими ограничениями, наложенными на х, в задачу поиска минимума без ограничений функции
Функция является штрафной. Необходимо, чтобы при нарушении ограничений она «штрафовала» функцию Z будет находиться внутри области ограничений. Функция
, удовлетворяющая этому условию, может быть не единственной.
Задачу минимизации можно сформулировать следующим образом:
минимизировать функцию
при ограничениях
.
Функцию удобно записать следующим образом:
где r – положительная величина.
Тогда функция принимает вид
.
Если х принимает допустимые значения, т.е. значения, для которых , то Z принимает значения, которые больше соответствующих значений
(истинной целевой функции данной задачи), и разность можно уменьшить за счет того, что r может быть очень малой величиной. Но если х принимает значения, которые хотя и являются допустимыми, но близки к границе области ограничений, и по крайней мере одна из функций
близка к нулю, тогда значения функции
, и следовательно значения функции Z станут очень велики. Таким образом, влияние функции
состоит в создании «гребня с крутыми краями» вдоль каждой границы области ограничений. Следовательно, если поиск начнется из допустимой точки и осуществляется поиск минимума функции
без ограничений, то минимум, конечно, будет достигаться внутри допустимой области для задачи с ограничениями. Полагая r достаточно малой величиной, для того чтобы влияние
было малым в точке минимума, мы можем сделать точку минимума функции
без ограничений совпадающей с точкой минимума задачи с ограничениями.
Алгоритм метода штрафных функций
Пусть имеется следующая задача:
Минимизировать при ограничениях
,
.
Начальный этап Выбрать в качестве константы остановки, начальную допустимую точку
, для которой
,
, скаляр
и
. Положить k=1 и перейти к основному этапу.
Основной этап. k-я итерация.
Первый шаг. При исходной точке решить следующую задачу безусловной оптимизации:
минимизировать, где
- параметр, значения которого убывают с каждой итерации
при
;
- положительные весовые коэффициенты.
Примерами штрафных функций являются:
1) обратная функция
2) логарифмическая функция
Положить равным оптимальному решению задачи минимизации и перейти ко второму шагу.
Минимизация штрафной функцию может быть выполнена любым методом безусловной оптимизации, например, градиентным.
Второй шаг
Если , то остановиться. Решение является искомым. В противном случае положить
. Изменить
и перейти к первому шагу (k+1)-й итерации.
Метод штрафных функций относится к группе методов внутренней точки, т.е. он начинает работать с допустимой точки и генерирует последовательность допустимых точек
. Метод барьерных функций, наоборот, относится к группе методов внешней точки, он начинает поиск с недопустимой точки и генерирует последовательность недопустимых решений, которая приближается к оптимальному решению извне допустимой области.
Пусть имеется задача минимизировать
при ограничениях
::,
::
,
![]()
В частности, для искомых функций – ограничений целесообразно использовать барьерную функцию следующего вида:
- непрерывные функции, которые удовлетворяют условиям:
, если
и
, если
,
, если
и
, если
.
Типичными являются следующие выражения для функций :
,
, где р – целое положительное число.
Далее от исходной задачи переходим к задачи безусловной оптимизации вспомогательной функции:
минимизировать
,
где
- штрафной коэффициент.
Пусть – непрерывная функция. Обозначим
.
Подход, связанный с барьерной ф