 |
Двойственность в нелинейном программировании
|
|
|
|
Рассмотримнекоторые фундаментальные моменты теории нелинейного программирования. Исходной точкой для них является распространение метода Лагранжа для решения ЗИП с ограничениями в форме неравенств:
(28)
где X - некоторая область в пространстве 
.
Определим для задачи (28) функцию Лагранжа:
. (29)
Определение. Пара векторов 
называется седловой точкой функции 
некоторой области 
, если для любых 
. (30)
Неравенства (30) также называют неравенствами седловой точки.
Рис. 2.7
В качестве примера седловой точки может быть приведена точка 
для функции 
определенной на множестве 
Действительно, 
а для любых 
и 
выполняются неравенства 
и 
.
На Рис. 2.7изображен график функции (гиперболический параболоид), и, как видно, в окрестности точки он действительно по форме напоминает седло, чем и объясняется происхождение соответствующего термина.
Теорема Куна-Таккера. Центральное место в теории нелинейного программирования занимает теорема Куна - Таккера, которая связывает решение ЗНП с наличием седловой точки у соответствующей функции Лагранжа.
Теорема 2.3. (Достаточное условие экстремума). Если - седловая точка функции Лагранжа, в области 
, 
, mo 
является оптимальным планом задачи (28), причем справедливо так называемое правило дополняющей нежесткости
. (31)
По определению седловой точки имеем
(32)
при всех 
Из второго неравенства в (32) следует, что
, для (33)
Однако (33) может иметь место только тогда, когда 
при всех 
. Действительно, если существует такое k, что 
, то, положив 
для всех 
и выбрав достаточно большое 
, можно добиться того, что значение
,
окажется больше постоянного выражения
.
Из того, что для всех выполняются неравенства следует, что является допустимым планом задачи (28).
|
|
|
Если в левую часть неравенства (33) подставить значения .то получим, что
.
С другой стороны из того что, и 
, следует оценка
.
Совместное рассмотрение последних двух неравенств приводит к правилу дополняющей нежесткости в точке :
.
Тогда на основании левой части неравенства седловой точки (32) имеем, что для всех (в том числе и для 
)
По условию ЗИП для любых верны неравенства , что, в сочетании с условием , позволяет записать
.
Следовательно,
.
Окончательно получаем, что для любых справедливо соотношение 
, т.е. - оптимальный план задачи (28).
Утверждение, обратное теореме (3), т. е. необходимое условие экстремума в ЗНП, оказывается верным только при выполнении дополнительных условий, которым должна удовлетворять задача (28). Важнейшим из них является так называемое условие регулярности Слейтера:
Говорят, что функция 
, задающая ограничение в задаче (28), удовлетворяет условию регулярности Слейтера, если существует такая точка 
, принадлежащая области допустимых, планов D, что
,
т. е. является внутренней точкой относительно ограничения . Поэтому данное условие также называют условием телесности.
Вообще говоря, существуют разные варианты необходимого условия Куна-Таккера. Приведем один из них.
Теорема 2.4. (Необходимое условие наличия экстремума) Если 
является задачей выпуклого программирования с решением , ее целевая функция 
и функции ограничений - дифференцируемы, нелинейные ограничения в форме неравенств удовлетворяют условию регулярности Слейтера, то существует такой вектор 
, что - седловая точка функции Лагранжа
Значение теоремы Куна-Таккера состоит в том, что она позволяет связать процесс решения оптимизационной задачи с поиском седловых точек функции Лагранжа, т. е., грубо говоря, с максимизацией этой функции по х и минимизацией по и.
|
|
|
Определим 
какфункцию, ставящую в соответствие каждому значению х минимальное значение функции по и:
и по аналогии
.
Рассмотрим задачу отыскания максимума функции
(34)
и задачу минимизации 
. (35)
Очевидно, что
Отсюда следует, что максимум находится в допустимой области D и совпадает с максимумом целевой функции задачи (28):
.
Таким образом, задача (34), в определенном смысле, равносильна (28). Аналогичные выводы могут быть получены и для (35). Задачи (34) и (35) образуют двойственную пару. Очевидно, данное отношение является обобщением отношения двойственности для задач линейного программирования. Соответственно, при определенных условиях пара двойственных задач нелинейного программирования обладает свойствами, аналогичными свойствам двойственных линейных задач. В частности, при любых 
. (36)
Условие (36) находит широкое применение при построении оценок в итеративных методах решения оптимизационных задач. Например, если имеется возможность приблизительно решить прямую и двойственную задачи и получить последовательности приближений 
и 
, то с помощью неравенств вида
можно определить момент остановки вычислительной процедуры.
В заключение отметим, что возможен вариант вывода выражений для целевых функций и ограничений пары двойственных задач линейного программирования из общего определения отношения двойственности для нелинейных задач. Также отметим, что в процессе формирования нелинейных двойственных задач существует большая неоднозначность: их вид можно варьировать, включая в множество X часть ограничений 
.
|
|
|
