12.2. МЕТОД ШТРАФНЫХ ФУНКЦИЙ

Пусть будет последовательностью такой, что

Определим непрерывную функцию называемую штрафной функцией, следующим образом:

Типичным для Р является вид

где хотя возможны многие другие виды. Определим

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

Если окажется оптимальным для задачи (12.1), то необходим останов, в противном случае процедура продолжается с новым

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

Сходимость легко вытекает из следующей леммы. Лемма 12.1.

Доказательство. Из (12.13) для всех х. Поскольку имеем

Кроме того, так как максимизирует то

что доказывает (12.17).

Благодаря тому, что максимизирует

Аналогично,

Складывая и преобразуя последние два неравенства» получаем

Но учитывая, что получаем

Наконец, из выражений (12.20) и (12.21) имеем

Лемма доказана.

Сходимость будет установлена при помощи теоремы сходимости С.

Пусть Напомним, что в гл. 11 было показано, что любая последовательность может быть определена

как алгоритм. Допустим, что метод штрафных функций вырабатывает последовательность Мы определим последовательность как алгоритм и докажем его сходимость. В частности, мы установим, что любая предельная точка любой сходящейся подпоследовательности является решением задачи (12.1).

Условие 1. Точка х будет называться подходящей если х является решением задачи (12.1). Очевидно, условие теоремы сходимости С выполняется. По предположению все входят В компактное множество X, и решение существует, так что условие 16 также выполняется.

Условие 2. Определим Согласно лемме 12.1

Поэтому, если положить для всех то условие 2а выполняется.

Чтобы доказать выполнение условия 26, предположим, что Обратите внимание на то, что вследствие оптимальности точки из (12.13) и определения получаем

Из леммы 12.1 и соотношения (12.23) вытекает, что невозрастающая последовательность, ограниченная снизу величиной Поэтому она имеет предел (упр. 1)

Воспользовавшись непрерывностью придем к выводу, что

и, используя (12.24) и (12.25), получаем

Но так что (12.26) будет иметь место лишь в том случае, если

Благодаря непрерывности и соотношению

Отсюда приходим к важному заключению, что

Требуется еще один результат. Используя опять (12.23) и учитывая, что получаем

Далее непрерывность и неравенство (12.29) влекут за собой соотношения

Таким образом, мы доказали, что Это значит, что х должно быть решением задачи (12.1). Теперь условие 26 выполняется автоматически. Следовательно, установлено выполнение предположений теоремы сходимости С.

Необходимо отметить, что теорема сходимости С дает несколько больше, чем необходимо для доказательства сходимости. Фактически доказательство оптимальности точки х уже устанавливает сходимость.

Обратите внимание также на то, что (упр. 2)

Пример. Рассмотрим следующий пример:

Очевидно, что оптимальной точкой является

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

Тогда Так как вогнута и непрерывно дифференцируема, то ее максимум может быть

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

или

Если

Если

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

12.2.1. Двойственность

С общей задачей НЛП связаны различные двойственные задачи. В этом параграфе строится новая форма двойственной задачи, несколько отличная от той, которая была введена в гл. 2, и показывается, что точки где максимизирует являются допустимыми для этой новой двойственной задачи. Таким образом, алгоритм штрафных функций представляет собой двойственный метод.

Здесь можно поставить следующие две задачи:

прямая задача:

двойственная задача: , где

Прямая задача. Учитывая, что равна нулю, если х — допустимая точками отрицательна в противном случае, прямая программа может быть записана в виде

Таким образом, прямая задача представляет собой задачу НЛП. Как предполагалось ранее, операция может быть заменена операцией шах.

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

Из леммы (12.1)

Значит,

Но как было показано в (12.30),

при .

Резюмируя рассмотрение двойственной задачи, мы приходим к формулировке

при

Седловая точка. Итак, оптимальные значения целевых функций для прямой и двойственной задач совпадают,

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

Вогнутость. Рассмотрим теперь задачу НЛП с вогнутыми и непрерывно дифференцируемыми функциями и также может быть выбрана вогнутой и непрерывно дифференцируемой (упр. 3); в этом случае

тогда и только тогда, когда

Двойственная задача при этом может быть переписана в следующем виде:

при

или в эквивалентном виде

при

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

Если то непрерывна;

Определим

Тогда для фиксированного двойственная задача может быть записана в виде

при

Отметим связь этой двойственной задачи с вогнутой двойственной задачей, построенной в гл. 2:

при

где