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

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

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

 

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

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

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

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

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

i=1, 2,…, m.

 

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

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

(30)

или в виде:

(31)

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

 

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

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

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

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

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

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

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

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

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

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

 

И так далее.

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

  .

Пусть С=10.

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

и т.д.

 .

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

и т.д.

 

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

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

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

Рис.15

 

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

 

если,

если,

и так далее.

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

 

Рис.16