Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 12.2. МЕТОД ШТРАФНЫХ ФУНКЦИЙПусть
Определим непрерывную функцию
Типичным для Р является вид
где
Алгоритм. Процедура штрафных функций заключается в следующем: для каждого
Если Сходимость. Для доказательства сходимости алгоритма мы предполагаем, что функции Сходимость легко вытекает из следующей леммы. Лемма 12.1.
Доказательство. Из (12.13)
Кроме того, так как
что доказывает (12.17). Благодаря тому, что
Аналогично,
Складывая и преобразуя последние два неравенства» получаем
Но учитывая, что
Наконец, из выражений (12.20) и (12.21) имеем
Лемма доказана. Сходимость будет установлена при помощи теоремы сходимости С. Пусть как алгоритм. Допустим, что метод штрафных функций вырабатывает последовательность Условие 1. Точка х будет называться подходящей если х является решением задачи (12.1). Очевидно, условие Условие 2. Определим
Поэтому, если положить Чтобы доказать выполнение условия 26, предположим, что
Из леммы 12.1 и соотношения (12.23) вытекает, что
Воспользовавшись непрерывностью
и, используя (12.24) и (12.25), получаем
Но
Благодаря непрерывности
Отсюда приходим к важному заключению, что Требуется еще один результат. Используя опять (12.23) и учитывая, что
Далее непрерывность
Таким образом, мы доказали, что Необходимо отметить, что теорема сходимости С дает несколько больше, чем необходимо для доказательства сходимости. Фактически доказательство оптимальности точки х уже устанавливает сходимость. Обратите внимание также на то, что (упр. 2)
Пример. Рассмотрим следующий пример:
Очевидно, что оптимальной точкой является Чтобы решить эту задачу алгоритмом штрафных функций, используем следующую квадратичную функцию потерь:
Тогда найден дифференцированием. Соответствующий х, который максимизирует
или
Если Если Оценивая минимум при значениях 12.2.1. ДвойственностьС общей задачей НЛП связаны различные двойственные задачи. В этом параграфе строится новая форма двойственной задачи, несколько отличная от той, которая была введена в гл. 2, и показывается, что точки Здесь можно поставить следующие две задачи: прямая задача: двойственная задача: Прямая задача. Учитывая, что
Таким образом, прямая задача представляет собой задачу НЛП. Как предполагалось ранее, операция Двойственная задача. Теперь докажем, что двойственная задача решается алгоритмом штрафных функций. Предполагалось, что
Из леммы (12.1)
Значит,
Но как было показано в (12.30),
при Резюмируя рассмотрение двойственной задачи, мы приходим к формулировке
при Седловая точка. Итак, оптимальные значения целевых функций для прямой и двойственной задач совпадают,
Интересно отметить, что до сих пор построение прямой и двойственной задач было сделано для общей задачи НЛП, причем никаких требований типа условий вогнутости или выпуклости на задачу не накладывалось. Таким образом, двойственное равенство справедливо для задач НЛП весьма общего вида. Однако для получения дальнейших результатов мы должны сделать предположение о вогнутости функций, порождающих задачу. Вогнутость. Рассмотрим теперь задачу НЛП с вогнутыми и непрерывно дифференцируемыми функциями
тогда и только тогда, когда
Двойственная задача при этом может быть переписана в следующем виде:
при
или в эквивалентном виде
при
В зависимости от используемой функции потерь мы можем построить большое количество двойственных задач. Например, рассмотрим функцию
Если
Определим
Тогда для фиксированного
при
Отметим связь этой двойственной задачи с вогнутой двойственной задачей, построенной в гл. 2:
при
где
|
1 |
Оглавление
|