4.6. Квадратичне програмування

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

 

(4.53)

U =

иєЕя :{ai,u)<bi,i = l,...,m; (a,,«) = £>',   i = m+l,s (4.54)

де С - симетрична, невід'ємно визначена матриця розміром пхп, тобто  С>0;<і,аі єЕ",Ь' єй(і' = 1,...,ї)  (не виключається

можливість т = 0, або 5 = 0, або т = 5 = 0).

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

Розглянемо деякі специфічні особливості цієї задачі. Зокрема розглянемо двоїсту до (4.53), (4.54) задачу.

Введемо функцію Лагранжа задачі (4.53), (4.54):

Ь(и, Я) = ^{Си, и)+(а, и) + (Я, Аи-Ь) = Л{Си,и)+{а + АТЯ,и)-{Я,Ь),

иєио=Еп,ЯєА0 = {Я = (ЯІ,...,Л5)єЕ5:ЛІ>0,...,Ят>0},

де А - матриця розміром .їх я з рядками а1,...,а3,  Ь = (Ь1,...,Ь"). Якщо Л>-со,  І/, *0, то відповідно до

теореми 3. 5 функція Ь(и,Я) має сідлову точку (и,,Я )при чому в силу леми 3.2

dL{u„X) ди

= Cu,+d + ATX =0,

Я]{(аі,и.)-Ьі) = 0, і = 1.....si

и, є17„Х єЛ0.

Тоді двоїста до (4.53), (4.54) задача

W(Я) = inf Ь(и,Я) -> sup, Л<=Л0,

(4.55) (4.56)

(4.57)відповідно до теореми 3.4 також має розв'язок , причому Л=¥/* = 8ир¥/(я)=У(«,)) «,єС/„

X еЛ' = {ЛєА0:¥{Л)=¥'\

За додаткових припущень про додатну визначеність матриці С, тобто 00, функція Ї'(Я) може бути виписана явно. Насправді, тоді С невироджена і точка мінімуму и = и(Х) функції Ь(и, Я) для иєЕ„ однозначно  визначається  з  системи   Си + <1 + АТЛ = 0,   так що

и(Л)=-с-1(а+лтя).

Тому

¥{Л) = Ци(Я), Л) = --{(і + АтЛ, С"1 (а + атл)} - (Л, Ь) =

= --((АС-,Ат)А,А)-{аС-,(І+Ь,А)--(с-,(І,(і), ЯеЛ0,

де АС~1АТ >0. Таким чином, для 00 двоїста задача (4.57), записана у вигляді

-!Р(Л)-»ІПҐ, ЯєЛ0, (4.58)

також є задачею квадратичного програмування вигляду (4.53), (4.54), але множина Л0в порівнянні з (4.54) має більш просту структуру.

Знаючи деякий розв'язок X задачі (4.58), можна записати розв'язок початкової задачі (4.53), (4.54) в вигляді

и.=-С~1((і + Атх) (4.59)

Справді, для 00 функція •/(«) сильно випукла і відповідно до теореми 3.1. задача (4.53), (4.54) має єдиний розв'язок який обов'язково буде розв'язком системи (4.55), (4.56), де X - розв'язок задачі (4.58). І оскільки система (4.55) при фіксованому Яоднозначно визначає точку и., то необхідно приходимо до формули (4.59).

Особливо простою задача (4.58) є в тому випадку, коли в початковій задачі (4.53), (4.54) відсутні обмеження типу нерівностей (т = 0) і множина £/ має вигляд

и={ ые£п:{а(-,и) = &',/ = 1,...,4 (4.60)

Тоді Л0 = Еа і задача (4.58) запишеться в формі

-!Р(Л)-Мпт;  ЛєЕ5. (4.61)

Множина А* розв'язків задачі (4.61) в силу теореми 2.1 співпадає з множиною розв'язків системи

- У(А*) = АС~1АТХ + АС~1<І + Ь = 0. (4.62)

В загальному випадку система (4.62) може мати більш ніж однин розв'язок. Якщо матриця А не вироджена.  Тобто вектори

а1,...,а1 в (4.60) лінійно незалежні, то з С >0 випливає АС~1АТ > 0 і

тоді задача (4.61), і як наслідок, система (4.62) будуть мати єдиний розв'язок. Таким чином, для С >0, щоб розв'язати задачу (4.53), (4.60) достатньо розв'язати дві системи лінійних алгебраїчних рівнянь (4.62), (4.55). Для цього можна застосувати відомі методи лінійної алгебри.