3.
МНОГОМЕРНЫЙ
ПОИСК
НЕЛИНЕЙНОЕ
ПРОГРАММИРОВАНИЕ
МЕТОДЫ УСЛОВНОЙ МИНИМИЗАЦИИ
3.2. Метод
штрафных
функций
Основная идея метода штрафных функций состоит в преобразовании задачи минимизации функции с соответствующими ограничениями, наложенными на аргументы , в задачу поиска минимума функции без ограничений.
Преимущество, которое получаем в результате такого перехода к новой функции, достигается за счет применения более простых алгоритмов.
Методы штрафных функций можно разделить на два класса: параметрические и непараметрические. Параметрические методы характеризуются наличием одного или нескольких параметров, входящих в структуру штрафной функции в качестве весовых коэффициентов.
Например, требуется найти минимум функции при ограничениях:
|
i=1, 2,…, m. |
Введем функцию:
Здесь выступает в роли штрафа. Штраф можно выбрать в виде:
|
(30) |
или в виде:
|
(31) |
где - некоторый положительный параметр.
Примеры выбора вида штрафной функции:
Пусть дана функция при ограничениях . Выберем штраф как:
В результате минимизируем функцию
Другой пример. Требуется минимизировать функцию , при ограничении . Прибавим к целевой функции значение , тогда получим функцию без ограничений
Таким образом, методы штрафных функций определяются как выбором вида штрафа, так и выбором параметра r.
Рассмотрим на конкретном примере один из параметрических методов, а именно метод внутренней точки.
Пусть требуется минимизировать функцию при ограничениях .
Исходная точка поиска .
|
|
И так далее.
.
Пусть С=10.
Минимизируем тем же градиентным методом, теперь за исходную точку принимаем .
|
|
и т.д.
.
и т.д.
Чем ближе к минимуму при , тем меньше градиент функции .
Поиск заканчивается, если , где ε – малая положительная величина.
Графическая иллюстрация примера показана на рис. 15.
Рис.15
Линии уровня функции есть концентрические окружности с центром в точке с координатами:
|
|
|
если, |
|
|
если, |
|
и так далее.
Блок-схема метода штрафных функций представлена на рис. 16.
Рис.16