Semi-definitní programování

Semidefinite programming (neboli SDP z angl. Semidefinite programming ) je podsekce konvexního programování , která se zabývá optimalizací lineární účelové funkce (cílová funkce je uživatelem specifikovaná funkce, jejíž hodnotu chce uživatel minimalizovat nebo maximalizovat) na průsečík kuželů pozitivně semidefinitních matic s afinním prostorem .

Semi-definite programování je relativně nová oblast optimalizace, o kterou roste zájem z několika důvodů. Mnoho praktických problémů v oblasti operačního výzkumu a kombinatorické optimalizace lze modelovat nebo aproximovat jako semidefinité programovací problémy. V teorii automatického řízení se problémy SDP používají v kontextu lineárních maticových nerovností . Problémy SDP jsou ve skutečnosti speciálním případem kónického programování a lze je efektivně vyřešit metodou vnitřních bodů . Všechny problémy lineárního programování lze vyjádřit jako problémy SDP a pomocí hierarchií problémů SDP lze aproximovat řešení problémů polynomiální optimalizace. Semi-definitní programování se používá při optimalizaci složitých systémů . V posledních letech byly některé problémy kvantové složitosti dotazů formulovány z hlediska semidefinitního programování.

Motivace a definice

Počáteční motivace

Problém lineárního programování je problém, ve kterém potřebujete maximalizovat nebo minimalizovat lineární účelovou funkci reálných proměnných na mnohostěnu . V semi-definitním programování místo toho používáme skutečné vektory a můžeme používat bodový součin vektorů. Podmínka nezápornosti reálných proměnných úlohy LP je nahrazena semidefinitními omezeními na matici proměnných úlohy SDP. Zejména obecný semidefinitní programovací problém může být definován jako jakýkoli matematický programovací problém formuláře

{\min _{x^{1},\ldots ,x^{n}\in \mathbb {R} ^{n))}{\součet _{i,j\in [n]}c_ {i,j}(x^{i}\cdot x^{j})}

za podmínek

{\sum _{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}\qquad \forall k }.

Ekvivalentní formulace

O matici se říká, že je kladně semidefinitní , pokud jde o Gramovu matici některých vektorů (tj. pokud existují vektory takové, že pro všechny ). Pokud je to pravda, označíme to jako . Všimněte si, že existují některé další ekvivalentní definice pozitivní semidefinitečnosti, například pozitivní semidefinitní matice mají pouze nezáporná vlastní čísla a mají kladnou semidefinitní druhou odmocninu. $n\krát n$ $M$ ${\displaystyle x^{1},\ldots ,x^{n))$ ${\displaystyle m_{i,j}=x^{i}\cdot x^{j))$ $i,j$ $M \succeq 0$

Označme prostorem všech reálných symetrických matic. V tomto prostoru je vnitřní produkt (kde znamená stopa ) ${\mathbb {S}}^{n}$ $n\krát n$ $\langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\sum _{i=1,j=1 }^{n}A_{ij}B_{ij}.$ ${\rm {tr))$

Úlohu matematického programování z předchozí části můžeme přepsat do ekvivalentní podoby

{\min _{X\in \mathbb {S} ^{n))}\langle C,X\rangle _{\mathbb {S} ^{n))

za podmínek

{\begin{array}{ll}{\displaystyle \langle A_{k},X\rangle _{\mathbb {S} ^{n))\leq b_{k},\quad k=1, \ldots ,m}\\X\succeq 0\end{array}}

kde prvek matice je roven z předchozí části a je to matice, která má hodnotu z předchozí části jako prvek matice. $i,j$ $C$ ${\displaystyle c_{i,j))$ $A_k$ $n\krát n$ $i,j$ ${\displaystyle a_{i,j,k))$

Všimněte si, že pokud správně přidáme další proměnné , lze tuto úlohu SDP převést na

{\displaystyle \min _{X\in \mathbb {S} ^{n))}\langle C,X\rangle _{\mathbb {S} ^{n))

za podmínek

{\begin{array}{ll}\langle A_{k},X\rangle _{\mathbb {S} ^{n))=b_{k},\quad k=1,\ldots ,m \\X\succeq 0\end{array}}

Pro usnadnění může být problém SDP definován v mírně odlišné, ale ekvivalentní formě. Například lineární výrazy využívající nezáporné skalární proměnné lze přidat do specifikace úlohy. Úkolem zůstává SDP, protože každá proměnná může být zahrnuta do matice jako diagonální prvek ( pro některé ). Chcete-li zajistit , můžete přidat omezení pro všechny . Jako další příklad si všimněte, že pro jakoukoli kladnou semidefinitní matici existuje sada vektorů , takže prvek matice je roven , skalárnímu součinu vektorů a . Problémy SDP jsou tedy často formulovány jako lineární vyjádření skalárních součinů vektorů. Při řešení problému SDP ve standardním tvaru lze vektory rekonstruovat v čase (např. pomocí neúplného rozkladu Choleského matice X). $X$ ${\displaystyle X_{ii))$ $i$ $X_{ii}\geq 0$ $X_{ij}=0$ $j\neq i$ $X$ $\{v_{i}\}$ $i$ $j$ $X$ $X_{ij}=(v_{i},v_{j})$ $v_{i}$ $v_{j}$ $\{v_{i}\}$ $O(n^{3})$

Teorie duality

Definice

Podobně jako u lineárního programování, pokud je ve formuláři uveden obecný problém SDP

\min _{X\in \mathbb {S} ^{n}}\langle C,X\rangle _{\mathbb {S} ^{n}}

za podmínek

{\begin{array}{ll}\langle A_{i},X\rangle _{\mathbb {S} ^{n))=b_{i},\quad i=1,\ldots ,m \\X\succeq 0\end{array}}

(přímý problém, nebo P-SDP), definujeme duální semidefinitní problém (D-SDP) jako

\max _{y\in \mathbb {R} ^{m}}\langle b,y\rangle _{\mathbb {R} ^{m}}

za podmínek

{\begin{array}{ll}{\displaystyle \sum _{i=1}^{m}}y_{i}A_{i}\preceq C\end{array}}

Kde pro libovolné dvě matice a , znamená . $P$ $Q$ $P\succeq Q$ $PQ\succeq 0$

Slabá dualita

Slabý teorém duality říká , že primární SDP má hodnotu ne menší než hodnotu duálního SDP. Jakékoli přípustné řešení problému duálního SDP tedy omezuje hodnotu přímého SDP zdola a naopak jakákoli přípustná hodnota problému přímého SDP omezuje hodnotu duálního SDP shora. To se děje, protože

\langle C,X\rangle -\langle b,y\rangle =\langle C,X\rangle -\sum _{i=1}^{m}y_{i}b_{i}=\langle C,X\rangle -\součet _{i=1}^{m}y_{i}\langle A_{i},X\rangle =\langle C-\součet _{i=1}^{m}y_ {i}A_{i},X\rangle \geq 0,

kde poslední nerovnost odráží skutečnost, že obě matice jsou kladně semidefinitní. Hodnota této funkce se někdy nazývá dvojitá vůle.

Silná dualita

Za podmínky známé jako Slaterova podmínka jsou hodnoty primárního a duálního problému SDP stejné. Tomu se říká silná dualita . Na rozdíl od problémů lineárního programování nemá každý problém SDP přísnou dualitu. V obecném případě může být hodnota SDP duálního problému přísně nižší než hodnota přímého problému.

(i) Předpokládejme, že přímý problém (P-SDP) je ohraničen zdola a přísně přípustný (tj. existuje , takový, že , ). Pak existuje optimální řešení pro duální problém (D-SDP) a $X_{0}\in \mathbb {S} ^{n},X_{0}\succ 0$ ${\displaystyle \langle A_{i},X_{0}\rangle _{\mathbb {S} ^{n))=b_{i))$ $i=1,\ldots ,m$ $y^{*}$

\langle C,X^{*}\rangle _{\mathbb {S} ^{n))=\langle b,y^{*}\rangle _{\mathbb {R} ^{m)) .

(ii) Předpokládejme, že duální problém (D-SDP) je ohraničen shora a přísně přípustný (tedy pro některé ). Pak existuje optimální řešení přímé úlohy (P-SDP) a platí rovnost z (i). $\sum _{i=1}^{m}(y_{0})_{i}A_{i}\prec C$ ${\displaystyle y_{0}\in \mathbb {R} ^{m))$ $X^{*}$

Příklady

Příklad 1

Uvažujme tři náhodné proměnné a . Podle definice jsou jejich korelační koeficienty platné tehdy a jen tehdy $A$ $B$ $C$ $\rho _{AB},\ \rho _{AC},\rho _{BC}$

{\begin{pmatrix}1&\rho _{AB}&\rho _{AC}\\\rho _{AB}&1&\rho _{BC}\\\rho _{AC}&\rho _ {BC}&1\end{pmatrix}}\succeq 0

Předpokládejme, že z některých zdrojů (například z empirických nebo experimentálních dat) víme, že a . Problém určení nejmenší a největší hodnoty lze zapsat jako: $-0,2\leq \rho _{AB}\leq -0,1$ $0.4\leq \rho _{BC}\leq 0.5$ $\rho _{AC}\$

minimalizovat/maximalizovat

x_{13}

za podmínek

-0,2\leq x_{12}\leq -0,1

0,4\leq x_{23}\leq 0,5

x_{11}=x_{22}=x_{33}=1\

{\begin{pmatrix}1&x_{12}&x_{13}\\x_{12}&1&x_{23}\\x_{13}&x_{23}&1\end{pmatrix}}\succeq 0

Zde přijímáme . Problém lze formulovat jako problém SDP. Nerovnice doplníme rozšířením matice proměnných a zavedením dalších proměnných , např. ${\displaystyle \rho _{AB}=x_{12},\ \rho _{AC}=x_{13},\ \rho _{BC}=x_{23))$

$\mathrm {tr} \left(\left({\begin{array}{cccccc}0&1&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&1&0&0\c&0&0\0\t{0&0&0\0{0&0}\vpravo&0&0}\) \left({\begin{array}{cccccc}1&x_{12}&x_{13}&0&0&0\\x_{12}&1&x_{23}&0&0&0\\x_{13}&x_{23}&1&0&0&0\\0&0&0&s_{1} \\0&0&0&0&s_{2}&0\\0&0&0&0&0&s_{3}\end{array}}\right)\right)=x_{12}+s_{1}=-0,1$

Po vyřešení tohoto problému SDP získáme minimální a maximální hodnoty ( resp .). $\rho _{AC}=x_{13}\$ $-0,978$ $0,872$

Příklad 2

Zvažte problém

minimalizovat

{\frac {(c^{T}x)^{2}}{d^{T}x}}

za podmínek

Ax+b\geq 0

kde se předpokládá, že v . $d^{T}x>0$ $Ax+b\geq 0$

Zavedením další proměnné přepíšeme problém do tvaru: $t$

minimalizovat

t

za podmínek

Ax+b\geq 0,\,{\frac {(c^{T}x)^{2}}{d^{T}x}}\leq t

V této formulaci je účelová funkce lineární funkcí dvou proměnných ( ). $x,t$

První omezení lze přepsat jako

{\textbf {diag}}(Ax+b)\geq 0

kde matice je čtvercová matice s hodnotami na diagonále rovnými prvkům vektoru . ${\textbf {diag}}(Ax+b)$ $A+b$

Druhé omezení lze zapsat jako

td^{T}x-(c^{T}x)^{2}\geq 0

Matici definujeme následovně $D$

D=\left[{\begin{array}{cc}t&c^{T}x\\c^{T}x&d^{T}x\end{array}}\right]

K tomu můžeme použít Schurovu teorii doplňku

D\succeq 0

[jeden]

Semi-definitivní programovací problém pro tento problém bude ve tvaru

minimalizovat

t

za podmínek

\left[{\begin{array}{ccc}{\textbf {diag}}(Ax+b)&0&0\\0&t&c^{T}x\\0&c^{T}x&d^{T}x\ end{array}}\right]\succeq 0

Příklad 3 (Aproximační algoritmus Goemans-Williamson MAX CUT)

Semi-definitní programování je důležitým nástrojem pro vytváření aproximačních algoritmů pro NP-těžké maximalizační problémy. První aproximační algoritmus založený na SDP byl navržen Michelem Goemansem a Davidem Williamsonem [2] . Studovali problém MAX CUT : Daný graf G = ( V , E ), je nutné rozdělit vrcholy V na dvě části takovým způsobem, aby se maximalizoval počet hran spojujících tyto dvě části. Problém lze považovat za problém celočíselného kvadratického programování :

Maximalizovat předmět libovolného .

\sum _{(i,j)\in E}{\frac {1-v_{i}v_{j}}{2}},

{\displaystyle v_{i}\in \{1,-1\))

i

Pokud P = NP , nemůžeme tento problém efektivně vyřešit. Goemans a Williamson však nastínili třístupňový postup pro řešení tohoto druhu problému:

Oslabujeme problém celočíselného kvadratického programování na problém SDP.
Vyřešíme problém SDP (s jakoukoli libovolně malou chybou ). $\epsilon$
Řešení úlohy SDP zaokrouhlíme, abychom získali přibližné řešení původní úlohy celočíselného kvadratického programování.

Pro problém MAX CUT je nejpřirozenější relaxace

\max \sum _{(i,j)\in E}{\frac {1-\langle v_{i},v_{j}\rangle }{2)),

for , kde se maximalizace provádí přes vektory spíše než skalární celočíselné proměnné.

\lVert v_{i}\rVert ^{2}=1

\{v_{i}\}

Problém je problém SDP, protože jak cílová funkce, tak omezení jsou lineárními funkcemi skalárních součinů vektorů. Řešení problému SDP poskytuje sadu jednotkových vektorů v . Protože vektory nejsou nutně kolineární, hodnota uvolněného problému může být pouze větší než hodnota původního celočíselného problému kvadratického programování. K rozdělení je zapotřebí závěrečný postup zaokrouhlení. Goemans a Williamson si vyberou náhodnou nadrovinu (pomocí jednotného rozložení) přes počátek a rozdělí vrcholy na základě jejich umístění vzhledem k této rovině. Přímá analýza ukazuje, že tento postup poskytuje očekávaný aproximační faktor 0,87856 - ε. (Očekávaná hodnota řezu je rovna součtu přes všechny hrany pravděpodobností, že hrana vstoupí do řezu, a toto očekávání je úměrné úhlu mezi vektory v koncových vrcholech hrany. Porovnáme-li tuto pravděpodobnost s , očekávání poměru bude vždy alespoň 0,87856.) Za předpokladu hypotézy správnosti jedinečné hry lze ukázat, že aproximační koeficient této aproximace je převážně optimální. $\mathbf {R^{n}}$ $\cos ^{-1}\langle v_{i},v_{j}\rangle$ $(1-\langle v_{i},v_{j}\rangle )/{2}$

Od doby, kdy se objevil článek Goemanse a Williamsona, byly problémy SDP aplikovány na vývoj velkého počtu aproximačních algoritmů. Nedávno Prasad Raghavendra vyvinul obecné schéma pro problémy s uspokojením omezení založené na jedinečné herní hypotéze [3] .

Algoritmy

Existuje několik typů algoritmů pro řešení problémů SDP. Výsledkem těchto algoritmů je hodnota problému SDP až , která je získána v čase, který polynomiálně závisí na velikosti problému a . $\epsilon$ $\log(1/\epsilon )$

Vnitřní bodové metody

Většina systémů řešení je založena na metodě vnitřních bodů (CSDP, SeDuMi, SDPT3, DSDP, SDPA), která je robustní a efektivní pro obecné lineární problémy SDP. Použití tohoto přístupu je omezeno skutečností, že algoritmy jsou metodami druhého řádu a vyžadují velké (a často husté) matice k zapamatování a rozkladu.

Metody prvního řádu

Metody prvního řádu pro kuželovou optimalizaci se vyhýbají ukládání a rozkladu velkých Hessových matic a jsou použitelné na mnohem větší problémy než metody vnitřních bodů, za cenu ztráty přesnosti. Metoda je implementována v systému "SCS solver".

Metoda paprsku

Problém SDP je formulován jako nehladký optimalizační problém a je řešen metodou spektrálního svazku. Tento přístup je velmi účinný pro konkrétní třídy lineárních úloh SDP.

Ostatní

Algoritmy založené na zobecněné Lagrangiánově metodě (PENSDP) se chovají podobně jako metody vnitřních bodů a lze je upravit pro některé velmi velké problémy. Jiné algoritmy používají nízkoúrovňové informace a přeformulují problém SDP jako problém nelineárního programování (SPDLR).

Aplikace

Semi-definitní programování bylo použito k nalezení přibližných řešení kombinatorických optimalizačních problémů, jako je řešení problému maximálního řezu s aproximačním faktorem 0,87856. Problémy SDP se také používají v geometrii k definování grafů tensegrity a objevují se v teorii řízení jako lineární maticové nerovnosti .

Literatura

Lieven Vandenberghe, Stephen Boyd. Semidefinite Programming // SIAM Review 38. - 1996. - březen. - S. 49-95 .
Monique Laurent, Franz Rendl. Semidefinitní programování a celočíselné programování/sestava PNA-R0210, CWI, Amsterdam . - 2002. - Duben.
E. de Klerk. Aspekty semidefinitního programování: Algoritmy vnitřních bodů a vybrané aplikace. - Kluwer Academic Publishers, 2002. - ISBN 1-4020-0547-4 .
P. Raghavendra. Optimální algoritmy a nepřibližné výsledky pro každého CSP? // Proceedings of the 40th Annual ACM Symposium on theory of Computing (Victoria, British Columbia, Canada, May 17-20, 2008). STOC'08 . - New York, NY: ACM, 2008. - S. 245-254.
Robert M. Freund. Úvod do semidefinitního programování (SDP) .
Michel X. Goemans, David P. Williamson. Vylepšené aproximační algoritmy pro problémy s maximálním řezem a splnitelností pomocí semidefinitního programování // JACM. - 1995. - Listopad ( díl 42 , číslo 6 ). - S. 1115-1145 . doi : 10.1145 / 227683.227684 .

Odkazy

Spojení na úvody a události v poli
Poznámky z přednášek László Lovásze o semidefinitním programování

Optimalizační metody
Jednorozměrný	metoda zlatého řezu Dichotomie Parabolová metoda Vyhledávání v mřížce Jednotná metoda vyhledávání bloků Fibonacciho metoda Ternární hledání Piyavského metoda Stronginovou metodou
Nulové pořadí	Gaussova metoda Metoda Nelder-Mead Hook-Jeevesova metoda Rosenbrockova metoda Powellova metoda
První objednávka	gradientní sestup Zeutendijkova metoda Souřadnicový sestup Metoda konjugovaného gradientu Kvazi-newtonské metody Levenberg-Marquardtův algoritmus
druhá objednávka	Newtonova metoda Newton-Raphsonova metoda Algoritmus Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastické	Metoda Monte Carlo Simulované žíhání Evoluční algoritmy diferenciální evoluce Algoritmus mravenců Metoda roje částic Algoritmus včelstva Metoda náhodné chůze
Metody lineárního programování	Simplexní metoda Gomoriho algoritmus Elipsoidní metoda Potenciální metoda
Metody nelineárního programování	Sekvenční kvadratické programování