3. МНОГОМЕРНЫЙ ПОИСК

НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

МЕТОДЫ УСЛОВНОЙ МИНИМИЗАЦИИ

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

Основная идея метода штрафных функций состоит в преобразовании задачи минимизации функции с соответствующими ограничениями, наложенными на аргументы , в задачу поиска минимума функции без ограничений.

Преимущество, которое получаем в результате такого перехода к новой функции, достигается за счет применения более простых алгоритмов.

Методы штрафных функций можно разделить на два класса: параметрические и непараметрические. Параметрические методы характеризуются наличием одного или нескольких параметров, входящих в структуру штрафной функции в качестве весовых коэффициентов.

Например, требуется найти минимум функции при ограничениях:

i=1, 2,…, m.

Введем функцию:

Здесь выступает в роли штрафа. Штраф можно выбрать в виде:

(30)

или в виде:

(31)

где - некоторый положительный параметр.

Примеры выбора вида штрафной функции:

Пусть дана функция при ограничениях . Выберем штраф как:

В результате минимизируем функцию

Другой пример. Требуется минимизировать функцию , при ограничении . Прибавим к целевой функции значение , тогда получим функцию без ограничений

Таким образом, методы штрафных функций определяются как выбором вида штрафа, так и выбором параметра r.

Рассмотрим на конкретном примере один из параметрических методов, а именно метод внутренней точки.

Пусть требуется минимизировать функцию при ограничениях .

Исходная точка поиска .

1. Строим функцию без ограничений, используя штраф

2. Пусть . Найдем минимум функции любым методом безусловной оптимизации, например, градиентным:

И так далее.

3. Уменьшаем r:

.

Пусть С=10.

Минимизируем тем же градиентным методом, теперь за исходную точку принимаем .

и т.д.

.

4. Вновь уменьшаем r

и т.д.

Чем ближе к минимуму при , тем меньше градиент функции .

Поиск заканчивается, если , где ε – малая положительная величина.

Графическая иллюстрация примера показана на рис. 15.

Рис.15

Линии уровня функции есть концентрические окружности с центром в точке с координатами:

	если,
	если,

и так далее.

Блок-схема метода штрафных функций представлена на рис. 16.

Рис.16