4.3. Теорема Куна-Таккера. Двоїста задача

Перейдемо до розгляду задач випуклого програмування. Під випуклим програмуванням розуміється розділ теорії екстремальних задач, в якому вивчаються задачі мінімізації (максимізації) випуклих функцій на випуклих множинах. Тобто під задачею випуклого програмування розуміється задача:

/(м)^тіп,   иєі/, (4.24) мєї70:^-(м)<0, і = 1,т;

и =

gi{u) = 0, і = т + \,я

(4.25)

де 1/0 - задана випукла множина з Еп,

функції J(u),gl(u\...,gm(u) визначені і випуклі на £/(,, а

gi(u) = {ai,u)-b',  і = т + \,8 - лінійні функції,

Ь' - задані числа,

а, - задані вектори з Еп .

Не   виключається   можливість,   коли   відсутні обмеження

^,(м)<0 (т = 0), або обмеження  gi(u) = 0 (я = т), або

обидва види обмежень (т=я=о), и = и0.   В   цих випадках

множина (4.25) є випуклою.

В теорії випуклого програмування важливе місце займає теорема про сідлову точку функції Лагранжа, яка відома в літературі як теорема Куна-Таккера, названа так в честь американських математиків Кута і Таккера, які вперше сформулювали та довели деякі варіанти цієї теореми. Ця теорема дає необхідні і достатні умови оптимальності в задачі (4.24) - (4.25), тобто умови належності точки до множини

£/» = \ и єІ/: Ли) = тіп ./(у) = У, |,

та встановлює правило множників Лагранжа для регулярної задачі. Для цього введемо функцію

Ь(и,Л)=4и)+^ЯіВі(и), (4.26)

ЯЕса називається регулярною функцією Лагранжа задачі (4.24), (4.25), де и є (/(,, а змінні Я = (Я^,..., Я5) належать множині

А0 = {Х = (Х1,...,Х$)єЕ$:Х1>О...Х3>0] (4.27)

Визначення 1. Точка (н„Я*)є £/0 хЛ0 називається сідповою точкою функції Лагранжа (4.26), якщо

і(и*Л) < £ і(и,Х*), VI* Є1/0 ,Х Є Л0. (4.28)

Існує рівнозначне формулювання для сідлової точки.

Лема 1. Для того, щоб точка ((/„Я") є 1/0 хЛ0 була сідловою

точкою функції Лагранжа, необхідно і достатньо, щоб виконувались наступні умови:

Ци*Х) ^ і(иХ) ,   V» Є Щ, (4.29)

К£і (м*)= 0, г = 1,5,  и* є {/. (4.30)

(без доведення).

Якщо ввести додаткові припущення про випуклість і гладкість задачі (4.24), (4.25), то лему 1 можна переформулювати в диференційній формі.

Лема 2. Нехай (4.24), (4.25) задача випуклого програмуванняі ЛиШи\...,8т(и)єС1{и0).

Тоді для того, щоб точка  (и„,Л*)є 1/0 хЛ0була сідловою точкою функції Лагранжа, необхідно і достатньо, щоб

(і„(н„Д* ),«-«,) =

= ^'("Л+ І^;(М,),М-М^>0, УИЄ£А0, (4.29')

= 0, І = 1,5,     И„ Є £/. (4.30') Доведення.

Так як функція Лагранжа (4.26), в силу припущень, випукла і диференційована по змінній иєі/^ для кожного ХєА^. Тому

умова (4.29) відповідно до теореми 1.7 рівносильна умові (4.29').

Як бачимо, співвідношення (4.29'), (4.30') нагадують умови (4.15) - (4.17) для Я,, = 1, співвідношення (4.29) - (4.30) відповідають

аналогічним (4.23) з Л,, = 1. Ці аналоги підкреслюють тісний зв'язок

між правилом множників Лагранжа з попереднього пункту і наступними теоремами.

З'ясуємо, як пов'язані між собою сідлова точка функції Лангранжа і розв'язок задачі (4.24), (4.25).

Теорема 1. Нехай (и„Л*) е[/0хЛ0- сідлова точка функції

Лагранжа. Тоді ./„ =-£^и„,Л*^ = ./(и,!), тобто и, - є

розв'язком задачі (4.24), (4.25).

Доведення. З умови (4.30) маємо и, є£/ і ь(и^,\*^ = ^{и*}-Тоді нерівність (4.29) перепишемо в вигляді

J(um) <і(иХ) = Д") + І      («), н Є Щ. (4.31) 4     ' 1=1

Зокрема,   (4.31)   виконується   і   для   всіх    и е 17. Але Л*£,.(н)<0, для нє£/, оскільки тоді gi(u)<0 і Я*>0 при

г = 1,т, так що %gi(u)<Q, для і =1,т, і &(«)=0 для і = т + 1,$, так що  Л*£((и) = 0,   і = т + 1,5. Тому з (4.31) випливає, що

J{um ) < ь{и, X* ^ < ./(м) для всіх иєіі, тобто и,єІІг.

Відзначимо, що теорема 1 доведена без будь-яких обмежень на

функції  J{u),gi{u),І = 1,5,   і на множину и9; зокрема ніякі

припущення про випуклість поки не використовувались.

Очевидно, що не для будь-якої задачі (4.24), (4.25) функція Латранжа буде мати сідлову точку. Так наприклад, якщо в задачі

(4.24) , (4.25) £/, =0, то як випливає з теореми 1, функція Латранжа такої задачі не може мати сідлову точку. Крім того, навіть в задачах випуклого програмування (4.24), (4.25) з £/, =0 в загальному випадку не можна чекати, що функція Латранжа буде мати сідлову точку.

Приклад . Розглянемо задачу J(u) = -Ы -> тіп

негУ = {ие*У0:#(и) = н2<0}, де £/0 = {м єЕ1 :0<и <а},0<а<оо.

Тут множина 1/0 випукла, функції Ллч), ^(м) випуклі на 1/0. Множина    І/   містить    лише    одну    точку    и=0,    так що = >/(0) = 0,11* = {О}. Але функція Латранжа

Ци,Х) = -и + Хи2,0<и<а,Х>0,

у цієї задачі не має сідлової точки.

Таким чином, для існування сідлової точки на задачу (4.24),

(4.25) , крім умов випуклості, повинні бути накладені якісь додатковіумови. Почнемо з розгляду випадку, коли в (4.25) відсутні обмеження типу рівностей (т = в), тобто множина [/має вигляд

II = {м є 1/0 : gi(u) < 0,і = 1,/и} (4.32)

Визначення 2. Множина (4.32) називається регулярною, якщо існує точка иєі/ така, що

gfi)<0,...,ga^)<0. (4.33)

Якщо и (, - випукла множина, функції gi («) випуклі на £/0, то в заміну (4.33) достатньо вимоги, щоб для кожного і існувала точка «;ЄЇ/, така щоб gj(ui) < 0, і = 1, т.

Тоді      в     якості      и      з     (4.33)      можна взяти

_ т _ т _

и = ^а(.и(, а,. >0, =1, оскільки иєї/ і в силу нерівності Йенсена

gj$<,£aigJfy<gjfc\  ] = \,т. і=і

Умову (4.33) називають умовою регулярності Слейтера. Будемо користуватися більш загальним визначенням регулярної множини.

Множина (4.32) називається регулярною, якщо для будь-якого вектора  Я" = ($,...,Я"т)*0 {я\ £0,...,Л*, >о)  існує така точка

и = и(я"), що

й^и,    {Х^) = ^В$)<0. (4.34)

і=1

Теорема 2. Нехай и 0 - випукла множина, функції J(u),gj(u\ і = \,т, випуклі на ЇД, а множина (4.32) регулярна; множина II, точок мінімуму функції J{u) на множині (4.32) непуста.

Тоді для кожної точки и, е II, необхідно, існують множники Лагранжа

Ґ=(ґи...Хт)єА0 = {%єЕт:Х1>0,...,Хт>0}

такі, що пара (и,,Х) складає сідлову точку функції Лагранжа на множині ио х Л0.

(без доведення)

Наведемо тепер найбільш відомий загальний варіант теореми Куна - Таккера.

Теорема 3 (Куна-Таккера). Нехай (у0 - випукла множина з Еп, функції ./(и), %і (м), І = 1, ТП, випуклі на 11^, 8і (") = (в,-, и) — 6', і = йі +1, і - лінійні функції. Нехай множина и, точок мінімуму функції ./(«) на множині

и = {и<=и0:§і(и)<0,  і = йіг; ^І-(м) = {аІ-,м)-Ь'<0,  і = т + 1,р; %і (и) = {аі,и)-Ь1 =0,  і = р +

непуста. Крім того, нехай виконується хоча б одна з наступних умов:

a) ио - багатогранна множина, функції Ллч), Яі'*"»£т(м) випуклі на випуклій відкритій множині Ш, £/0 с: \¥ і існує

точка и^І/така, що £і(и)<0,  і = \,т;

b) існуєточка иєи0Г\и така,що&(«)<0, і = \,т.

Тоді для кожної точки и, е и, необхідно існують множники

Лагранжа      X ={ХІ.....Я,) є Л0 = {X Є Еп : Хх > 0,... ,\р > О}такі, що пара (и,Д*)  є сідловою точкою функції Лагранжа на множини [/0хЛ0 . (без доведення).

За допомогою функції Лагранжа L(u,X^, UgUq, ХєА§,

задачу (4.24), (4.25) можна переформулювати наступним чином. Введемо функцію

Х(и) = sup L(u,X),    U є Щ. (4.35)

Я.єЛ0

Очевидно, що %(и) =

J(u\  Vm є U оо, Vu<=U0\U.

Зрозуміло, що іпї хім) = іпґ 3(и) = «Л і задачу (4.24), (4.25) можна переписати в рівносильному вигляді

%(и)^іпі,  иеи9. (4.36)

Будемо вважати, що 3. > -оо,   V, * 0.

Тоді задача (4.36) буде мати ту ж саму множину розв'язків £/, з тим же мінімальним значенням 3,, тобто

іпГ х(и) = Л,  1/«={и:иє = Л} (4.37)

Поряд з функцією (4.35) введемо функцію

= ІПҐ Ь(и,Х),   ХєЛ0, (4.38) иєС/0

і розглянемо задачу

¥(Х) ->■ вир,   X є Л0. (4.39)

Задача (19) називається двоїстою задачею до задачі (4.35) (або початкової, основної задачі (4.24), (4.25)), а змінні Л = (Л1,...,Л1)називаються  двоїстими  змінними,   на  відміну  від початкових, основних змінних и = (и1,...,«"). Позначимо

sup= ¥*,  Л* = {л. є Л0 := ¥*} (4.40)

Виявляється, задачі (4.35) і (4.39) тісно пов'язані між собою. Насамперед завжди виконується нерівності

<Л<х(«)>   иєи0і   ХєА0. (4.41)

Насправді, 4х      = inf і(и,Х) < і(и,Х) для всіх ЯеЛ0 і

иеС/д. Тому

= supT(X) < sup L(u,X) = х(и)

для будь-якого иєІІ0. Переходячи до нижньої грані по иєU0 в цій

нерівності, одержуємо W" <, J,, звідки і слідують нерівності (4.41).

Цікаво з'ясувати, коли ¥" = J, і обидві задачі (4.35) та (4.39) мають розв'язок, тобто

U,*0,   Л**0,   J, = W". (4.42)

Виявляється, співвідношення (4.42) тісно пов'язані з сідловою точкою функції Лагранжа.

Теорема 4. Для того, щоб мали місце співвідношення (4.42), необхідно і достатньо, щоб функція Ь{и,Х^ {и є Uq, X є Aq) мала

сідлову точку на      хЛ0 в сенсі визначення 1. Множина сідлових

точок функції Ь{и,Х) на U0 х Л0 співпадає з множиною t/.хЛ', (без доведення)

Наслідок 1. Наступні твердження рівносильні:

a) (н„Л*)є£/0хЛ0 - сідлова точка функції Ь(и,Л) на хЛ0;

b) виконуються співвідношення (4.42);

c) існують точки u,eUfy, Я" є Л0, такі що %{и,) = *?{Х);

d) справедлива рівність

max inf і(м,Х) = тіп sup L(u,X)

\<-AQu<=U0 "єЩХєА0

(нагадаємо, якщо пишуть mas або min, то передбачається досягнення верхньої або нижньої грані), (без доведення).

Звідси та теореми 1 випливає, що в теоремах 2, 3 можна вибрати одні й ті ж самі множники Лагранжа. Відзначимо, що рівність *Р* = Jt

може виконуватись і в тому випадку, коли одна з множин U, або Л* пуста.

Наслідок 2. Якщо (ы„Я*) і (а„й*) є £/0 хЛ0- сідпові точки функції і(и,Я) на U0 хЛ№, то (и,,&*)і(а„Я*)на     хЛ0, причому

L(u#,b*) = L{am,\*) = Д"*Л*) = Ь(ащ,Ъ*) = J* = X¥*.

(без доведення).

Розглянемо задачу мінімізації функції j{u) на множині

U = {ueU0:gi(u)<0,  і = йі;

gi(u) = (ahu)-bi <0, і = т + \,р; (4.43) Si (") = (щ,и)-Ь* = 0,  і = р +,

де

и0 = {и^Еп:{^,и}</1,  і = 1,р;

 (і/,-,и) =        / = /» + 1,^|- багатогранна

множина,

Ьг,/'- задані числа,

а^сії є £■„ - задані вектори з і?я.

Зокрема, тут може бути 11$ = Е*.

Теорема   5.   Нехай   функція випукла   на (у0,

Ли) £ С1 (£/о), множина  С/   визначена відповідно до (4.43),

II* = Іиєї/: 7(м) = іпґ У(у) = Л >-оо[ * 0. Тоді для кожної

точки ш^и* необхідно існують множника Лагранжа Я*=(Я1*,...,Ді*)єЛ0 = {Я = (Л1.....Л3)єЕ3 :Хх £0,...,^ >0} такі, що

пара (ш,Я)  є сідловою точкою функції Лагранжа на множині

иохА0.

(без доведення)

З цієї теореми, зокрема, випливає, що в будь-якій задачі лінійного програмування, яка має розв'язок, функція Лагранжа завжди має сідлову точку.