Методы условной минимизации

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

min f =? X- допустимое множество

X=íxÎRⁿ, g_i(x)0, i =1...mý f и все g_i выпуклы

Утверждение:

Допустимое множество в задаче выпуклого программирования (ЗВП) выпукло

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

пусть x₁,x₂ÎX, lÎ[0,1]

lx₁+(1-l)x₂ÎX

воспользуемся свойством выпуклости g_i:

g_i(lx₁+(1-l)x₂)l g_i (x₁) + (1-) g_i(x₂)0

тогда x₁+(1-)x₂X (см. опр. X),но рассматривается только отдельная g_i.

Все допустимое множество X рассматривается как пересечение выпуклых

множеств X выпукло.

Определение:

Функцией Лагранжа в ЗВП называется функция

f(x)+f(x) + (,g(x)), где _i0

справедлива теорема Каруша-Джона:

Ñf(x*)+=0, _i g_i(x*) = 0, i=1..m

В случае выпуклости множества X условие линейной независимости векторов

g_i(x), соответствующее активным ограничениям, можно заменить более просто

проверяемыми, а именно, так называемыми условиями регулярности.

Существуют различные условия регулярности ограничений:

А) если для любого i (1i m)

существует x_iX: g_i (x_i) <0, то говорят, что множество X удовлетворяет

условию регулярности.

Б) условие регулярности Слейтера:

Существует точка xX такая, что для любого i=1...m g_i(x)<0.

Легко доказать эквивалентность условий А и Б. Очевидно, что из Б

следует А. Пусть теперь выпукла А. Выберем x =, =1,

0, i=1...mэто возможно, так как X выпукло.

Тогда Б следует из неравенства Иенсена.

Замечание:

Условие регулярности означает, что допустимое множество имеет внутреннюю

точку (то есть оно не вырождено в точку(общий случай))

Определение:

Пусть существует функция (x,y), точка (x,y) называется седловой точкой функции, если выполняется следующее неравенство: (x,y)(x,y)(x,y)

Теорема (о седловой точке):

Пусть функция Лагранжа ЗВП имеет седловую точку, то есть

f(x)+f(x)+ f (x)+

для любого xÎRⁿ, l_i ³0, i =1...m

тогда x*- оптимальная точка (решение) ЗВП.

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

Из левого неравенства следует:

,l_i* ³0, g_i(x*)0(см. опред. X)

Так как -любое, то при =0 получится:

0£(l*, g(x*))=0.

Из правого неравенства имеем:

f(x*)+0 f(x)+ f(x) xX

Тогда по определению оптимальной точки x*оптимальна.

Теорема Куна-Таккера:

Пусть в ЗВП выполнено условие регулярности Слейгера. Тогда для того, чтобы

x* была оптимальной точкой ЗВП, необходимо и достаточно, чтобы для

некоторого вектора l* с неотрицательными компонентами точка (x*,l*)

была седловой точкой функции Лагранжа.

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

Достаточность следует из теоремы о седловой точке.

Необходимость -без доказательства.