Двойственность в нелинейном программировании

2.2.1. Понятие седловой точки. В настоящем параграфе мы кратко остановимся на некоторых фундаментальных моментах теории нелинейного программирования. Отправной точкой для них является распространение метода Лагранжа для решения ЗНП с ограничениями в форме неравенств:

 

 

где X — некоторая область в пространстве Rⁿ.

По аналогии с п. 2.1.2 определим для задачи (2.28) функцию Лагранжа:

 

 

F Пара векторов (х, u) называется седловой точкой фун­кции Ф (х, и) в некоторой области X x U, если

для любых x ∈ X и u ∈ U

 

Неравенства (2.30) также называют неравенствами седловой точки.

 

 

В качестве примера седловой точки может быть приведена точка (0, 0) для функции Ф(х,и) = - х ² + и ², определенной на множестве R х R. В самом деле, Ф(0,0)=0, Ф(х,0)=- х ², Ф(0, и) = и ², а для любых x ∊ R и u ∊ R выполняются неравенства – х ²≤0 и 0 ≤ и ².

На рис. 2.7 изображен график функции Ф(х,и) (гиперболи­ческий параболоид), и, как видно, в окрестности точки (0,0) он действительно по форме напоминает седло, чем и объясняется происхождение соответствующего термина.

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

 

Теорема 2.3. (Достаточное условие экстремума). Если (х, и) — седловая точка функции Лагранжа, в области x ∊ X⊇D, и≥ 0, то х является оптимальным планом задачи (2.28), причем справедливо так называ­емое правило дополняющей нежесткости:

 

Доказательство.

По определению седловой точки

 

 

при всех x ∊ X, и≥ 0. Из второго неравенства в (2.32) следует, что

 

 

Однако (2.33) может иметь место только тогда, когда g_i (x)≤0 при всех i ∊1: m. Действительно, если существует та­кое k, что g_k (x)>0, то, положив и_i =0 для всех i ≠ k и выбрав достаточно большое и_k > 0, можно добиться того, что значение

 

окажется больше постоянного выражения

 

 

Из того, что для всех i ∊1: m выполняются неравенства g_i (x)≤0, следует, что х является допустимым планом задачи (2.28).

Если в левую часть неравенства (2.33) подставить значения u_i = 0, i ∊1: m, то получим, что

 

 

Вместе с тем из того что, g_i (x)≤0 и u_i ≥0, следует оценка

 

 

Совместное рассмотрение последних двух неравенств приводит к правилу дополняющей нежесткости в точке х:

 

 

Тогда на основании левой части неравенства седловой точки (2.32) имеем, что для всех х ∊ Х (в том числе и для х ∊ D)

 

 

Но условию ЗНП для любых х ∊ D верны неравенства g_i (x)≤0, что, в сочетании с условием u_i ≥0, позволяет записать

 

 

Значит,

 

 

Окончательно получаем, что для любых х ∊ D справедливо со­отношение f(x) ≥ f(x), т. е. х — оптимальный план задачи (2.28). A

Утверждение, обратное теореме (2.3), т. е. необходимое условие экстремума в ЗНП, оказывается верным только при вы­полнении дополнительных условий, которым должна удовлет­ворять задача (2.28). Важнейшим из них является так называе­мое условие регулярности Слейтера:

F F Говорят, что функция g_i (х), задающая ограничение в за­даче (2.28), удовлетворяет условию регулярности Слей­тера, если существует такая точка , принадлежащая области допустимых планов D, что

 

т. е. является внутренней точкой относительно ограничения g_i(x). Поэтому данное условие также называют условием теле­сности.

Вообще говоря, существуют разные варианты необходимо­го условия Куна—Таккера. Приведем один из них.

 

Теорема 2.4. (Необходимое условие наличия экст­ремума). Если (D, f) является задачей выпуклого программиро­вания с решением х, ее целевая функция f(x) и функ­ции ограничений gi(x) — дифференцируемы, нелиней­ные ограничения в форме неравенств удовлетворяют условию регулярности Слейтера, то существует та­кой вектор и ≥ 0, что (х,и) — седловая точка функции Лагранжа Ф (х,и).

 

Мы не будем здесь приводить доказательство теоремы (2.4), которое является довольно сложным. Заинтересованный чита­тель может найти его в таких источниках, как [1, 13].

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

Определим F(x) как функцию, ставящую в соответствие каждому значению х минимальное значение функции Ф(х,и) по и:

 

 

и по аналогии

 

 

Рассмотрим задачу отыскания максимума функции F(x)

 

 

и задачу минимизации G(u)

 

 

Очевидно, что

 

 

Отсюда следует, что максимум F(x) находится в допустимой области D и совпадает с максимумом целевой функции f(x) зада­чи (2.28):

 

 

Таким образом, задача (2.34), в определенном смысле, рав­носильна (2.28). Аналогичные выводы могут быть получены и для (2.35). Задачи (2.34) и (2.35) образуют двойственную пару. Как нетрудно догадаться, данное отношение является обобще­нием отношения двойственности для задач линейного програм­мирования. Соответственно, при определенных условиях пара двойственных задач нелинейного программирования обладает свойствами, аналогичными свойствам двойственных линейных задач. В частности, при любых х ∊ Х, и ≥0

 

Условие (2.36) находит широкое применение при построе­нии оценок в итеративных методах решения оптимизационных задач. Например, если имеется возможность приблизительно решить прямую и двойственную задачи и получить последова­тельности приближений { х ^{( q )}} и { и ^{( q )}}, то с помощью нера­венств вида

 

 

можно определить момент остановки вычислительной про­цедуры.

В заключение отметим, что возможен вариант вывода выра­жений для целевых функций и ограничений пары двойственных задач линейного программирования из общего определения от­ношения двойственности для нелинейных задач. Также отме­тим, что в процессе формирования нелинейных двойственных задач существует большая неоднозначность: их вид можно ва­рьировать, включая в множество Х часть ограничений g_i(x) ≤0.

 

КЛЮЧЕВЫЕ ПОНЯТИЯ

 

Ø Ø Общая задача нелинейного программирования.

Ø Ø Условная и безусловная оптимизация.

Ø Ø Прямые и непрямые методы решения оптимизационных задач.

Ø Ø Стационарная точка.

Ø Ø Градиентные методы.

Ø Ø Метод наискорейшего спуска и методы дробления шага.

Ø Ø Выпуклая и вогнутая функции.

Ø Ø Матрица Гессе.

Ø Ø Достаточное условие выпуклости (вогнутости).

Ø Ø Задача выпуклого программирования.

Ø Ø Допустимое направление.

Ø Ø Прогрессивное направление.

Ø Ø Седловая точка.

Ø Ø Теорема Куна—Таккера.

Ø Ø Условие регулярности Слейтера.

КОНТРОЛЬНЫЕ ВОПРОСЫ

 

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

2.2. Приведите пример экономической модели, сводящейся к задаче нелинейного программирования.

2.3. Перечислите основные трудности, возникающие в про­цессе решения задачи нелинейного

программирования.

2.4. Какой смысл вкладывается в понятие «условная оптими­зация»?

2.5. Для чего предназначен метод множителей Лагранжа и в чем он состоит?

2.6. Какая точка называется стационарной?

2.7. Какие принципиальные этапы входят в градиентные ме­тоды?

2.8. Для решения каких задач предназначены метод наиско­рейшего спуска и метод дробления шага?

2.9. Дайте определение выпуклой (вогнутой) функции.

2.10. Сформулируйте достаточное условие выпуклости (во­гнутости) функции.

2.11. В чем заключена специфика задач выпуклого программи­рования?

2.12. Перечислите основные этапы, входящие в метод допусти­мых направлений.

2.13. Сформулируйте задачу, которая должна быть решена при определении шага в методе

допустимых направлений.

2.14. Исходя из каких соображений определяется допустимое прогрессивное направление?

2.15. Какое условие используется для определения оптималь­ности текущей точки в методе

допустимых направлений?

2.16. Дайте определение седловой точки. Приведите пример функции, имеющей седловую точку.

2.17. Сформулируйте необходимое и достаточное условия тео­ремы Куна—Таккера. Какое значение

они имеют для ре­шения задач нелинейного программирования?

2.18. В чем состоит условие регулярности Слейтера? Поясните его содержание.

2.19. Какое условие получило название «правила дополняю­щей нежесткости»?

2.20. Приведите пример пары двойственных задач нелинейного программирования.

2.21. Какие свойства пары нелинейных двойственных задач мо­гут быть применены для их решения?