3.5 Необходимые и достаточные условия экстремума

Рассмотрим задачу выпуклого программирования вида

к

 

 

г=1

 

(3.12)

57

(рі(х) < О, г = 1,то, х £ С С Вп, (3.13) (3.14)

где О - выпуклое замкнутое множество, имеющее внутренние точки, /, - выпуклые функции. Предположим, что Жо £ О и для каждой из функций /(ж) — /(жо)> щ(х), г = 1, ...,то, суще­ствуют непустые подмножества пространства на которых они принимают отрицательные значения. Конусы внутренних напра­влений из точки жо для множеств Со = {х £ Ка | /(х) < /(жо)}, С{ = {х £ Кп | (/зг(ж) < 0},г = 1,...,то, и О в данном случае выглядят следующим образом:

Г = {е | е = г/(ж — жо), V > 0, ж Є ггаіС}.

Конус предельных направлений при отсутствии ограничений -равенств есть все пространство Кп.

Определение 3.5 Вектор К £ Кп называется субградиентом функции / в точке жо, если для любого ж Є Ка справедливо не­равенство /(ж) — /(жо) > (/г, ж — жо).

Множество всех субградиентов функции / в точке жо будем обо­значать д/(хо) и называть субдифференциалом / в точке жо-

Лемма 3.11 Конусы Гц, Г*, г = 1,...,то, задаются равенства­ми

Гц = {с0 | с0 = -А0/г, /г Є <9/(ж0), А0 > 0},

Г* = {сг | сі = -Аг7г, /г Є дщ(х0), Аг > 0, Аг(^г(ж0) = 0}, г = 1,..., то.

Доказательство. Включение " Э " легко следует из опреде­ления сопряженного конуса и субградиента.  Покажем обратное

Г0 = {е | е = г/(ж - ж0), г/ > 0, /(ж) < /(ж0)}

 

Кп,   если </зг-(жо) < 0 {е | е = г/(ж — ж0), V > 0, </зг(ж) < 0},   если </2г'(ж0) = 0

включение. Пусть со G Гд. Тогда по определению сопряженного конуса для всех ж, удовлетворяющих неравенству /(ж) < /(жо), и всех v > 0 справедливо

г/(с0, ж — ж0) > 0.

Следовательно, для любого с0 G Гд из неравенства /(ж) < /(ж0) следует

(с0, ж - ж0) > 0. Рассмотрим в пространстве R2 множество

У = {(у1, у2) | Зх G Rn : у1 = <с0, ж - ж0), у2 > /(ж) - /(ж0)}.

Из выпуклости функции / следует выпуклость множества Y. Так как со G Гц, то множество Y не пересекается с отрицательным ортантом

R2_ = {а е R2 | а1 < 0, а2 < 0}.

По теореме 3.2 существует ненулевой вектор ц G R2 такой, что при всех a G R2_ и всех у G Y (рис. 7) справедливо

11,     22/     lli 22

ji а + ц а  < ц у + ц у .

 

Рис. 7. Множества У, i?2, и отделяющая гиперплоскость

Положим у1 = (со, ж — хо),у2 = /(ж) — /(жо). Тогда при любых ж € Кп, а1 < 0, а2 < 0 верно

д1»1 + [12а2 < д1(со, ж — жо) + д2(/(ж) — /(жо)).

Это возможно лишь в том случае, когда [I1 > 0, [I2 > 0 и для всех х еЯп

[/(со, ж - ж0) + Д2(/(ж) - /(ж0)) > 0.

Если со ф 0, то это неравенство может выполняться для всех ж 6 -йп только при [I2 > 0. Следовательно,

/(ж) - Дж0) > (-[//[/ с0, ж - ж0)

для всех ж 6 Д™. Это означает, что вектор Ь, = —[11/[12 со при­надлежит д/(хо). Так как существуют точки ж, в которых /(ж) < /(жо), то     > 0. Поэтому

с0 = -А0/г,

где А0 = [I2/[I1 > 0.

Аналогично устанавливается, что

Г* = {сг | сг = -Аг7г, /г е дсрг(х0),Хг > 0}

в том случае, если (рг(хо) = 0 при г < то. Учитывая, что из условия (рг(хо) < 0 вытекает равенство Г* = {0}, получаем

Г* = {сг | сг = -Аг7г, К е дсрг(х0),Хг > 0, Хгсрг(х0) = 0}

для любого г = 1,то. Лемма доказана.

Определение 3.6 Функции

та

Цх, А) = /(ж) + (А, ф)) = /(ж) + £ \м(х) (3.15)

г = 1

60и

т

Ь(х, А0, А) = А0Дж) + (А, ф)) = А0Дж) + ]Г К^(х) (3.16)

i=l

называются соответственно функцией Лагранжа и обобщенной функцией Лагранжа для задачи (3.12)-(3.14)-

Определение 3.7 Пару (жо, А0), где жо € О, А0 = (А°,..., А^) > О, назовем седловой точкой функции Лагранжа, если для любых х € О, А > 0 справедливо неравенство

Как следует из определения 3.7, седловая точка (жо, А0) доста­вляет минимум функции Лагранжа по переменным ж при фик­сированном значении А = Ао и максимум по переменным А при фиксированном значении ж = жо (рис. 8).

 

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

Условие Слейтера. Говорят, что для задачи (3.12)-(3.14) вы­полнено условие Слейтера, если существует х' £ О такое, что

Ь(х, А0) > Ь(х0, А0) > Ь(х0, А).

 

Если условие Слейтера выполняется, то множество допустимых решений содержит внутреннюю точку. Обратное, вообще говоря, не верно (рис. 9).

Теорема 3.9 (Куна-Таккера) Пусть выполнено условие Слей­тера и хо £ О. Тогда хо — решение задачи (3.12)-(3.14) в том и только в том случае, когда существуют неотрицательные множители А° > 0, г = 1,...,т, такие, что пара (хо, А0) есть седловая точка функции Лагранжа Ь.

 

Доказательство. Необходимость. Пусть х0 — оптимальное ре­шение задачи (3.12)-(3.14). Тогда П^_0Гг- П Г = 0 и по теореме Дубовицкого-Милютина существуют не все равные нулю векто­ры С{ £ Г*, г = 0,..., то, с £ Г* такие, что со + с\ + ... + ст + с = 0. Следовательно, с = —^,7=осг- Теперь, из представления конусов Го, Г*, г = 1,. . .,то„ найденного в лемме 3.11, следует, что суще­ствуют не все равные нулю множители А° > 0, г = 0,..., то, и не все равные нулю векторы К{, г = 0, ..., то, такие, что

А° > 0, г = 0,.. .,то,

А°(^г(ж0) =0, г = 1,то, /г0 £ д/(х0),]гг £ дщ(х0), г = 1,то,

т i=l

для любого ж из С Вектор Ад/го + А°/гг- является субгради-

ентом функции Ь(х, Ао, А0) в точке жо и с учетом предыдущих неравенств имеем:

т

Ь(х, А°, А0) - Ь(х0, А°, А0) > (\°0к0 + ]Г \%, ж - ж0) > О,

г = 1

при всех ж 6 С Из последнего неравенства следует, что для всех х £ О справедливо

Ь(ж,А°,А°) > Ь(ж0,А°,А°).

Так как жо — оптимальное решение задачи (3.12)-(3.14), то из равенств А°(,ог (жо) = 0, г = 1,..., то, следует Ад/(жо) > Ад/(жо) + ^,7=1 Аг'(/зг'(жо) для любого А > 0. Следовательно,

Ь(х, А°, А0) > Ь(х0, А°, А0) > Ь(х0, А°, А)

при любых ж £ О, А > 0. Если Ад ф 0, то, поделив эти неравенства на А|], получаем требуемое. Докажем, что Ад ф 0. В силу условия Слейтера найдется ж' £ О такое, что <-р{(х') < 0 для г = 1, ...,т. Подстановка ж = ж' в неравенство Ь(х, Ад, А0) > Ь(хо, Ад, А0) дает

т

А^Ы<А°/(ж') + ^А°^(ж'),

i=l

откуда при Ад = 0 в силу неравенств А° > 0,^pi(x/) < 0, г = 1,..., то следовало бы, что множители А°, г = 1,..., то тоже равны нулю. Это невозможно, так как среди чисел А°, г = 0,...,то должны быть положительные.

Достаточность. Покажем, что существование седловой точки (жо, А0) функции Лагранжа Ь(х, А) достаточно для оптимальности жо в задаче (3.12)-(3.14). По определению седловой точки имеем

т

Ь(х0, А) = Дж0) + ^2 Х^г{х0) <

i=l

< /ы + ЕА^-ы = цх0,\°)

i=l

для всех А > 0. Тогда

т т

Х>,-¥>,-Ы < ^А°^Ы- (3.17)

г = 1 г = 1

Заметим, что </?г'(жо) < 0 для всех г = 1,..., т. В противном слу­чае ^,7=1 АгУг(жо) неограничена сверху на множестве неотрица­тельных А, что противоречит неравенству (3.17). Следовательно,

т

ЕА°^'Ы<0, (3.18)

i=l

и жо — допустимое решение задачи. Положим в неравенстве (3.17) А = 0. Тогда ^7=1 ^¥г{хо) > 0. Учитывая (3.18), получаем

т

^А°^Ы = 0. (3.19)

i=l

Из неравенства Ь(х, А0) > Ь(хо, А0) и (3.19) следует, что

т

Ь(х0,Х°) = /(х0) </(ж) + ^А°^(ж)

г = 1

для всех х £ О. Если точка ж является допустимым решением задачи (3.12)-(3.14), то

т

/Ы</(ж) + ^А°^(ж)</(ж).

г = 1

Теорема доказана.