2.6. ФУНКЦИЯ ЛАГРАНЖА И ТЕОРИЯ ДВОЙСТВЕННОСТИ

Прямое отношение к задаче НЛП имеет функция Лагранжа

где

В самом деле, всякий раз, когда функция Лагранжа имеет седловую точку, задача НЛП решается. Доказательство этого результата, его применения в теории двойственности и вывод новых достаточных условий являются предметами этого параграфа. (Принципиально отличный подход к двойственности изложен в гл. 12, где двойственность выведена на основании метода штрафов.)

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

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

Эти функции имеют много интересных свойств. Прежде всего следует обратить внимание на то, что

так что

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

Лемма 2.16. Следующие три утверждения эквивалентны:

Доказательство. Утверждение (а) может быть переписано в виде

Пусть минимизирует максимизирует тогда справедливо утверждение (б).

Если учесть соотношение (2.18), то из (б) следует (2.19), значит, и (а).

Из уравнения (2.17) следует, что (б) эквивалентно

и, используя введенные определения, из (2.20) получаем

что является утверждением (в). Таким образом, (в) является перефразировкой (б), т. е. они эквивалентны.

Лемма 2.16 дает несколько эквивалентных путей для идентификации седловой точки сожалению, функция может не иметь седловой точки (упр. 20), так как может оказаться, что

Седловая точка функции Лагранжа. Рассмотрим функцию Лагранжа для и

Функция Лагранжа имеет седловую точку, если

По аналогии с мы определим прямую функцию как

и двойственную функцию как

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

Соответственно двойственная задача заключается в вычислении оптимального такого, что

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

Поскольку для выбор минимизирует функцию Лагранжа. Но если при некоторых х и то функцию Лагранжа минимизирует при

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

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

В более явной форме прямая задача сводится к нахождению

Обратите внимание на то, что точка х является допустимой для задачи (2.23), если Следовательно, задача (2.23) становится задачей НЛП, если Из-за тесной связи между задачей НЛП и прямой задачей к. задаче НЛП часто относятся как к прямой. При этом, конечно, подразумевается предположение, что

Теперь обратимся к двойственной задаче и ее связи с прямой задачей. Пара называется допустимой для двойственной задачи, если Если — оптимальная точка для двойственной задачи и допустима, то пара также называется оптимальной.

Следующая лемма выражает важное свойство прямой и двойственной задач.

Лемма 2.17. Предположим, что допустима для задачи (2.23). Тогда Кроме того, если допустима для двойственной задачи, то

Доказательство. Если допустима для задачи (2.23), то из Уравнение (2.18), переписанное с помощью и дает Лемма 2.17 утверждает, что двойственная задача всегда дает верхнюю границу для прямой задачи. Это происходит, если даже функция Лагранжа не имеет седловой точки. В этом случае

где оптимальная точка для прямой задачи, а двойственной (упр. 2.21).

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

Теорема 2.18. Пусть является седловой точкой функции Лагранжа, т. е.

Тогда решает прямую задачу. Далее, если то решает задачу НЛП.

Доказательство. Из леммы 2.16 видно, что точка решает прямую задачу. Если то прямая задача сводится к задаче НЛП.

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

Ниже через обозначено

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

(см. скан)

г) удовлетворяет условиям Куна — Таккера для задачи НЛП и

2. если предположить, что — соответствующие множители из условий Куна—Таккера, то из следует, что

д) функции и вогнуты, удовлетворяет условиям Куна — Таккера.

Доказательство. Во всех частях доказательства искомое заключение следует из теоремы 2.18 после установления наличия у функции Лагранжа седловой точки:

а) согласно лемме 2.16 это условие эквивалентно наличию седловой точки;

б) используя лемму 2.17, имеем но это эквивалентно случаю (а);

в) из (в) 2 и(в) 3

Тогда допустима для двойственной задачи и получаем случай (б);

г) так как имеют место условия Куна—Таккера, то точка допустима и

Кроме того, условие 3 Куна — Таккера приводит к равенству Приходим к условиям случая (в);

д) из вогнутости функций, леммы 2.3 и того факта что для фиксированного функция

является вогнутой функцией х. Тогда из следует

так как т. е. имеет место случай

Из пяти условий теоремы 2.19 наиболее полезными являются Это связано с тем, что многие

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

то действительно является оптимальной точкой для задачи НЛП (см. упр. 28).

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