Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике 2.6. ФУНКЦИЯ ЛАГРАНЖА И ТЕОРИЯ ДВОЙСТВЕННОСТИПрямое отношение к задаче НЛП имеет функция Лагранжа
где
В самом деле, всякий раз, когда функция Лагранжа имеет седловую точку, задача НЛП решается. Доказательство этого результата, его применения в теории двойственности и вывод новых достаточных условий являются предметами этого параграфа. (Принципиально отличный подход к двойственности изложен в гл. 12, где двойственность выведена на основании метода штрафов.) Седловые точки. Наше рассмотрение начнется с общего определения седловой точки. Для произвольной функции Теперь определим две важные функции, которые тесно связаны с седловыми точками. Первая функция зависит от у и получается максимизацией
Эти функции имеют много интересных свойств. Прежде всего следует обратить внимание на то, что
так что
Теперь будет показано, что определение седловой точки может быть перефразировано при помощи функций К и К. Лемма 2.16. Следующие три утверждения эквивалентны:
Доказательство. Утверждение (а) может быть переписано в виде
Пусть Если учесть соотношение (2.18), то из (б) следует (2.19), значит, и (а). Из уравнения (2.17) следует, что (б) эквивалентно
и, используя введенные определения, из (2.20) получаем
что является утверждением (в). Таким образом, (в) является перефразировкой (б), т. е. они эквивалентны. Лемма 2.16 дает несколько эквивалентных путей для идентификации седловой точки
Седловая точка функции Лагранжа. Рассмотрим функцию Лагранжа для
Функция Лагранжа имеет седловую точку, если
По аналогии с
и двойственную функцию как
Из этих функций возникают две задачи. Прямой задачей является задача нахождения оптимального
Соответственно двойственная задача заключается в вычислении оптимального
Прямая и двойственная задачи. Прямая и двойственная задачи являются основой исследований в НЛП, и остальная часть этого параграфа посвящена их анализу. Начнем изучение прямой задачи оценкой прямой функции
Поскольку Прямая задача требует максимизации прямой функции рассмотрения и прямая задача может быть сформулирована как нахождение
В более явной форме прямая задача сводится к нахождению
Обратите внимание на то, что точка х является допустимой для задачи (2.23), если Теперь обратимся к двойственной задаче и ее связи с прямой задачей. Пара Следующая лемма выражает важное свойство прямой и двойственной задач. Лемма 2.17. Предположим, что
Доказательство. Если
где Достаточность. Следующая теорема содержит основной результат для вывода достаточных условий оптимальности. Теорема 2.18. Пусть
Тогда Доказательство. Из леммы 2.16 видно, что точка Теорема утверждает, что если Ниже через
Теорема 2.19. Точка (см. скан) г) 2. если предположить, что д) функции Доказательство. Во всех частях доказательства искомое заключение следует из теоремы 2.18 после установления наличия у функции Лагранжа седловой точки: а) согласно лемме 2.16 это условие эквивалентно наличию седловой точки; б) используя лемму 2.17, имеем в) из (в) 2 и(в) 3
Тогда г) так как имеют место условия Куна—Таккера, то точка Кроме того, условие 3 Куна — Таккера приводит к равенству д) из вогнутости функций, леммы 2.3 и того факта что
является вогнутой функцией х. Тогда из
так как Из пяти условий теоремы 2.19 наиболее полезными являются алгоритмы решения задачи НЛП определяют точку
то Для простоты мы часто заявляем, что при наличии седловой точки имеет место двойственное равенство, так как в этом случае оптимальные значения целевых функций прямой и двойственной задач равны. Теорема 2.19 дает несколько условий, из которых следует наличие двойственного равенства.
|
1 |
Оглавление
|