Semidefinitní programování - Semidefinite programming

Semidefinitní programování (SDP) je podpole z konvexní optimalizace zabývající se optimalizací lineárního Objektivní funkce (uživatelem zadaná funkce, kterou chce uživatel minimalizovat nebo maximalizovat) na průsečíku kužel z pozitivní semidefinit matice s afinní prostor, tj. a spektrahedron.

Semidefinitní programování je relativně nové pole optimalizace, o které je z několika důvodů stále větší zájem. Mnoho praktických problémů v operační výzkum a kombinatorická optimalizace lze modelovat nebo aproximovat jako semidefinitní programovací problémy. V teorii automatického řízení se SDP používají v kontextu lineární maticové nerovnosti. SDP jsou ve skutečnosti zvláštním případem programování kužele a lze je efektivně vyřešit pomocí vnitřní bodové metody.Všechno lineární programy lze vyjádřit jako SDP a prostřednictvím hierarchií SDP lze aproximovat řešení problémů optimalizace polynomů. Semidefinitní programování bylo použito v EU optimalizace složitých systémů. V posledních letech byly formulovány některé problémy se složitostí kvantových dotazů, pokud jde o semidefinitní programy.

Motivace a definice

Počáteční motivace

A lineární programování problém je takový, ve kterém chceme maximalizovat nebo minimalizovat lineární objektivní funkci reálných proměnných přes a polytop. V semidefinitním programování místo toho používáme vektory se skutečnou hodnotou a je nám dovoleno brát bodový součin vektorů; omezení negenativity na skutečné proměnné v LP (lineární programování) jsou nahrazeny omezeními semidefiniteness na maticových proměnných v SDP (semidefinitní programování). Obecný semidefinitní programovací problém lze definovat jako jakýkoli matematický programovací problém formuláře

${displaystyle {egin {array} {rl} {displaystyle min _ {x ^ {1}, ldots, x ^ {n} in mathbb {R} ^ {n}}} & {displaystyle sum _ {i, jin [n ]} c_ {i, j} (x ^ {i} cdot x ^ {j})} {ext {podléhá}} & {displaystyle součet _ {i, jin [n]} a_ {i, j, k } (x ^ {i} cdot x ^ {j}) leq b_ {k}} {ext {pro všechny}} k end {pole}}}$

Kde ${displaystyle c_ {i, j}, a_ {i, j, k}}$a ${displaystyle b_ {k}}$ jsou reálná čísla a ${displaystyle x ^ {i} cdot x ^ {j}}$ je Tečkovaný produkt z ${displaystyle x ^ {i}}$ a ${displaystyle x ^ {j}}$.

Ekvivalentní formulace

An ${displaystyle n imes n}$ matice ${displaystyle M}$ se říká, že je pozitivní semidefinit pokud je to Gramianova matice některých vektorů (tj. pokud existují vektory ${displaystyle x ^ {1}, ldots, x ^ {n}}$ takhle ${displaystyle m_ {i, j} = x ^ {i} cdot x ^ {j}}$ pro všechny ${displaystyle i, j}$). Pokud tomu tak je, označíme to jako ${displaystyle Msucceq 0}$. Všimněte si, že existuje několik dalších ekvivalentních definic pozitivního semidefinitu, například pozitivní semidefinitní matice jsou samoadjung matice, které mají pouze nezáporné hodnoty vlastní čísla.

Označit podle ${displaystyle mathbb {S} ^ {n}}$ prostor všech ${displaystyle n imes n}$ skutečné symetrické matice. Prostor je vybaven vnitřní produkt (kde ${displaystyle {m {tr}}}$ označuje stopa )${displaystyle langle A, Bangle _ {mathbb {S} ^ {n}} = {m {tr}} (A ^ {T} B) = sum _ {i = 1, j = 1} ^ {n} A_ { ij} B_ {ij}.}$

Matematický program uvedený v předchozí části můžeme přepsat stejně

${displaystyle {egin {array} {rl} {displaystyle min _ {Xin mathbb {S} ^ {n}}} & langle C, Xangle _ {mathbb {S} ^ {n}} {ext {subject to}} & langle A_ {k}, Xangle _ {mathbb {S} ^ {n}} leq b_ {k}, kvadrant k = 1, ldots, m & Xsucceq 0end {pole}}}$

kde vstup ${displaystyle i, j}$ v ${displaystyle C}$ darováno ${displaystyle {frac {c_ {i, j} + c_ {j, i}} {2}}}$ z předchozí části a ${displaystyle A_ {k}}$ je symetrický ${displaystyle n imes n}$ matice s ${displaystyle i, j}$th vstup ${displaystyle {frac {a_ {i, j, k} + a_ {j, i, k}} {2}}}$ z předchozí části. Tedy matice ${displaystyle C}$ a ${displaystyle A_ {k}}$ jsou symetrické a výše uvedené vnitřní produkty jsou dobře definované.

Všimněte si, že pokud přidáme uvolněné proměnné vhodně lze tento SDP převést na jeden z formulářů

${displaystyle {egin {array} {rl} {displaystyle min _ {Xin mathbb {S} ^ {n}}} & langle C, Xangle _ {mathbb {S} ^ {n}} {ext {subject to}} & langle A_ {k}, Xangle _ {mathbb {S} ^ {n}} = b_ {k}, kvadrant k = 1, ldots, m & Xsucceq 0.end {pole}}}$

Pro větší pohodlí může být SDP specifikován v mírně odlišné, ale ekvivalentní formě. Například lineární výrazy zahrnující nezáporné skalární do specifikace programu lze přidat proměnné. Toto zůstává SDP, protože každou proměnnou lze začlenit do matice ${displaystyle X}$ jako diagonální vstup (${displaystyle X_ {ii}}$ pro některé ${displaystyle i}$). Zajistit to ${displaystyle X_ {ii} geq 0}$omezení ${displaystyle X_ {ij} = 0}$ lze přidat pro všechny ${displaystyle jeq i}$. Jako další příklad si všimněte, že pro jakoukoli pozitivní semidefinitní matici ${displaystyle X}$, existuje sada vektorů ${displaystyle {v_ {i}}}$ takové, že ${displaystyle i}$, ${displaystyle j}$ vstup z ${displaystyle X}$ je ${displaystyle X_ {ij} = (v_ {i}, v_ {j})}$ the skalární součin z ${displaystyle v_ {i}}$ a ${displaystyle v_ {j}}$. Proto jsou SDP často formulovány ve smyslu lineárních výrazů na skalárních produktech vektorů. Vzhledem k řešení SDP ve standardní formě, vektory ${displaystyle {v_ {i}}}$ lze obnovit v ${displaystyle O (n ^ {3})}$ času (např. použitím neúplného Choleský rozklad X).

Teorie duality

Definice

Analogicky k lineárnímu programování, vzhledem k obecnému SDP formuláře

${displaystyle {egin {array} {rl} {displaystyle min _ {Xin mathbb {S} ^ {n}}} & langle C, Xangle _ {mathbb {S} ^ {n}} {ext {subject to}} & langle A_ {i}, Xangle _ {mathbb {S} ^ {n}} = b_ {i}, quad i = 1, ldots, m & Xsucceq 0end {pole}}}$

(primární problém nebo P-SDP), definujeme dvojí semidefinitní program (D-SDP) as

${displaystyle {egin {array} {rl} {displaystyle max _ {yin mathbb {R} ^ {m}}} & langle b, yangle _ {mathbb {R} ^ {m}} {ext {subject to}} & {displaystyle sum _ {i = 1} ^ {m}} y_ {i} A_ {i} preceq Cend {pole}}}$

kde pro libovolné dvě matice ${displaystyle P}$ a ${displaystyle Q}$, ${displaystyle Psucceq Q}$ prostředek ${displaystyle P-Qsucceq 0}$.

Slabá dualita

The slabá dualita věta říká, že hodnota primárního SDP je přinejmenším hodnota dvojitého SDP. Proto jakékoli proveditelné řešení pro duální SDP omezuje primární hodnotu SDP a naopak jakékoli proveditelné řešení pro primární SDP horní hranici duální hodnoty SDP. To je proto, že

${displaystyle langle C, Xangle -langle b, yangle = langle C, Xangle -sum _ {i = 1} ^ {m} y_ {i} b_ {i} = langle C, Xangle -sum _ {i = 1} ^ {m} y_ {i} langle A_ {i}, Xangle = langle C-sum _ {i = 1} ^ {m} y_ {i} A_ {i}, Xangle geq 0,}$

kde poslední nerovnost je, protože obě matice jsou kladné semidefinitní, a výsledek této funkce se někdy označuje jako dualita mezery.

Silná dualita

Za podmínky známé jako Slaterův stav, hodnota primárního a duálního SDP jsou stejné. Toto je známé jako silná dualita. Na rozdíl od pro lineární programy ne každý SDP však uspokojuje silnou dualitu; obecně může hodnota duálního SDP ležet striktně pod hodnotou primála.

(i) Předpokládejme, že primární problém (P-SDP) je omezen níže a je přísně proveditelný (tj. existuje${displaystyle X_ {0} v mathbb {S} ^ {n}, X_ {0} succ 0}$ takhle ${displaystyle langle A_ {i}, X_ {0} úhel _ {mathbb {S} ^ {n}} = b_ {i}}$, ${displaystyle i = 1, ldots, m}$) Pak existuje optimální řešení ${displaystyle y ^ {*}}$ do (D-SDP) a

${displaystyle langle C, X ^ {*} angle _ {mathbb {S} ^ {n}} = langle b, y ^ {*} angle _ {mathbb {R} ^ {m}}.}$

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

Příklady

Příklad 1

Zvažte tři náhodné proměnné ${displaystyle A}$, ${displaystyle B}$, a ${displaystyle C}$. Podle definice jejich korelační koeficienty ${displaystyle ho _ {AB}, ho _ {AC}, ho _ {BC}}$ jsou platné právě tehdy

${displaystyle {egin {pmatrix} 1 & ho _ {AB} & ho _ {AC} ho _ {AB} & 1 & ho _ {BC} ho _ {AC} & ho _ {BC} & 1end {pmatrix}} succeq 0,}$

v takovém případě se tato matice nazývá korelační matice. Předpokládejme, že z některých předchozích znalostí (například empirických výsledků experimentu) víme, že ${displaystyle -0,2leq ho _ {AB} leq -0,1}$ a ${displaystyle 0.4leq ho _ {BC} leq 0,5}$. Problém stanovení nejmenší a největší hodnoty ${displaystyle ho _ {AC}}$ can take je dáno:

minimalizovat / maximalizovat ${displaystyle x_ {13}}$

podléhá

${displaystyle -0,2leq x_ {12} leq -0,1}$

${displaystyle 0.4leq x_ {23} leq 0,5}$

${displaystyle {egin {pmatrix} 1 & x_ {12} & x_ {13} x_ {12} & 1 & x_ {23} x_ {13} & x_ {23} & 1end {pmatrix}} succeq 0.}$

Jsme si stanovili ${displaystyle ho _ {AB} = x_ {12}, ho _ {AC} = x_ {13}, ho _ {BC} = x_ {23}}$ získat odpověď. To lze formulovat pomocí SDP. Omezení nerovnosti řešíme rozšířením matice proměnných a zavedením uvolněné proměnné, například

${displaystyle mathrm {tr} left (left ({egin {array} {cccccc} 0 & 1 & 0 & 0 & 0 & 0 0 & 0 & 0 & 0 & 0 0 & 0 & 0 & 0 & 0 0 & 0 & 0 & 1 & 0 & 0 0 & 0 & 0 & 0 & 0 & 0 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 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 & 0 & 0 & s_ {2} & 0 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & s ) = x_ {12} + s_ {1} = - 0,1}$

Řešení tohoto SDP dává minimální a maximální hodnoty ${displaystyle ho _ {AC} = x_ {13}}$ tak jako ${displaystyle -0,978}$ a ${displaystyle 0,872}$ resp.

Příklad 2

Zvažte problém

minimalizovat ${displaystyle {frac {(c ^ {T} x) ^ {2}} {d ^ {T} x}}}$

podléhá ${displaystyle Axe + bgeq 0}$

kde to předpokládáme ${displaystyle d ^ {T} x> 0}$ kdykoli ${displaystyle Axe + bgeq 0}$.

Představujeme pomocnou proměnnou ${displaystyle t}$ problém lze přeformulovat:

minimalizovat ${displaystyle t}$

podléhá ${displaystyle Ax + bgeq 0 ,, {frac {(c ^ {T} x) ^ {2}} {d ^ {T} x}} leq t}$

V této formulaci je cílem lineární funkce proměnných ${displaystyle x, t}$.

První omezení lze zapsat jako

${displaystyle {extbf {diag}} (Ax + b) geq 0}$

kde matice ${displaystyle {extbf {diag}} (Ax + b)}$ je čtvercová matice s hodnotami v úhlopříčce rovnými prvkům vektoru ${displaystyle Axe + b}$.

Druhé omezení lze zapsat jako

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

Definování ${displaystyle D}$ jak následuje

${displaystyle D = left [{egin {array} {cc} t & c ^ {T} x c ^ {T} x & d ^ {T} xend {array}} ight]}$

K tomu můžeme použít teorii Schurových doplňků

${displaystyle Dsucceq 0}$

(Boyd a Vandenberghe, 1996)

Semidefinitní program spojený s tímto problémem je

minimalizovat ${displaystyle t}$

podléhá ${displaystyle left [{egin {array} {ccc} {extbf {diag}} (Ax + b) & 0 & 0 0 & t & c ^ {T} x 0 & c ^ {T} x & d ^ {T} xend {array}} ight] succeq 0}$

Příklad 3 (Goemans – Williamsonův maximální aproximační algoritmus řezu)

Semidefinitní programy jsou důležitými nástroji pro vývoj aproximačních algoritmů pro NP-hard maximalizační problémy. První aproximační algoritmus založený na SDP je způsoben Michel Goemans a David P. Williamson (JACM, 1995). Studovali problém maximálního řezu: Vzhledem k graf G = (PROTI, E), výstup a rozdělit vrcholů PROTI tak, aby se maximalizoval počet hran přecházejících z jedné strany na druhou. Tento problém lze vyjádřit jako celočíselný kvadratický program:

Maximalizovat ${displaystyle sum _ {(i, j) in E} {frac {1-v_ {i} v_ {j}} {2}},}$ takové, že každý ${displaystyle v_ {i} v {1, -1}}$.

Ledaže P = NP, nemůžeme tento problém s maximalizací efektivně vyřešit. Goemans a Williamson však pozorovali obecný tříkrokový postup útoku na tento druh problému:

1. Odpočinout si celočíselný kvadratický program do SDP.
2. Vyřešte SDP (do libovolně malé chyby aditiva ${displaystyle epsilon}$).
3. Kolo řešení SDP k získání přibližného řešení původního celočíselného kvadratického programu.

Pro maximální řez je nejpřirozenější relaxace

${displaystyle max sum _ {(i, j) in E} {frac {1-langle v_ {i}, v_ {j} angle} {2}},}$ takhle ${displaystyle lVert v_ {i} Vert ^ {2} = 1}$, kde je maximalizace nad vektory ${displaystyle {v_ {i}}}$ místo celočíselných skalárů.

Toto je SDP, protože objektivní funkce a omezení jsou všechny lineární funkce vektorových vnitřních produktů. Vyřešením SDP získáte sadu jednotkových vektorů ${displaystyle mathbf {R ^ {n}}}$; protože vektory nemusí být kolineární, hodnota tohoto uvolněného programu může být pouze vyšší než hodnota původního kvadratického celočíselného programu. Nakonec je pro získání oddílu zapotřebí postup zaokrouhlování. Goemans a Williamson jednoduše zvolí rovnoměrně náhodnou nadrovinu přes počátek a rozdělí vrcholy podle toho, na které straně nadroviny leží odpovídající vektory. Přímá analýza ukazuje, že tento postup dosahuje očekávaného přibližný poměr (záruka výkonu) 0,87856 - ε. (Očekávaná hodnota řezu je součet přes hrany pravděpodobnosti, že je hrana řezána, která je úměrná úhlu ${displaystyle cos ^ {- 1} jazyk v_ {i}, v_ {j} úhel}$ mezi vektory v koncových bodech hrany nad ${displaystyle pi}$. Porovnání této pravděpodobnosti s ${displaystyle (1-langle v_ {i}, v_ {j} úhel) / {2}}$, v očekávání je poměr vždy alespoň 0,87856.) Za předpokladu domněnky o jedinečných hrách, lze ukázat, že tento aproximační poměr je v zásadě optimální.

Od původního článku Goemansa a Williamsona byly SDP použity k vývoji mnoha aproximačních algoritmů. V poslední době Prasad Raghavendra vytvořil obecný rámec pro problémy s uspokojením omezení založený na domněnky o jedinečných hrách.^[1]

Algoritmy

Existuje několik typů algoritmů pro řešení SDP. Tyto algoritmy vydávají hodnotu SDP až do aditivní chyby ${displaystyle epsilon}$ v čase, který je polynomem ve velikosti popisu programu a ${displaystyle log (1 / epsilon)}$.

Existují také algoritmy redukce obličeje, které lze použít k předzpracování problémů s SDP kontrolou omezení daného problému. Lze je použít k detekci nedostatku přísné proveditelnosti, k odstranění nadbytečných řádků a sloupců a také ke zmenšení velikosti matice proměnných.^[2]

Metody vnitřních bodů

Většina kódů je založena na vnitřní bodové metody (CSDP, MOSEK, SeDuMi, SDPT3, DSDP, SDPA). Robustní a efektivní pro obecné lineární problémy SDP. Omezeno skutečností, že algoritmy jsou metody druhého řádu a je třeba je ukládat a rozdělovat na velkou (a často hustou) matici.

Metody prvního řádu

Metody prvního řádu pro kónická optimalizace vyhnout se výpočtu, ukládání a faktorizaci velké hesenské matice a škálování na mnohem větší problémy než metody vnitřních bodů, za určitou přesnost. Metoda prvního řádu je implementována v řešení Splitting Cone Solver (SCS).^[3] Další metodou prvního řádu je metoda střídavého směru multiplikátorů (ADMM).^[4] Tato metoda vyžaduje v každém kroku projekci na kužel semidefinitních matic.

Metoda svazku

Kód ConicBundle formuluje problém SDP jako nehladká optimalizace problém a řeší ho metodou Spectral Bundle nehladké optimalizace. Tento přístup je velmi efektivní pro speciální třídu problémů lineárního SDP.

Další metody řešení

Algoritmy založené na Rozšířená Lagrangeova metoda (PENSDP) se chováním podobají metodám vnitřních bodů a lze je specializovat na některé velmi rozsáhlé problémy. Jiné algoritmy používají informace nízké úrovně a přeformulování SDP jako a nelineární programování problém (SDPLR).^[5]

Přibližné metody

Byly také navrženy algoritmy, které přibližně řeší SDP. Hlavním cílem těchto metod je dosáhnout nižší složitosti v aplikacích, kde jsou přibližná řešení dostatečná a složitost musí být minimální. Prominentní metodou, která byla použita pro detekci dat v bezdrátových systémech s více vstupy a více výstupy (MIMO), je Triangular Přibližná relaxace SEmidefinite (TASER),^[6] který pracuje na Choleského rozkladných faktorech semidefinitní matice namísto semidefinitní matice. Tato metoda počítá přibližné řešení pro problém typu max-cut, který je často srovnatelný s řešením od přesných řešitelů, ale pouze v 10-20 iteracích algoritmu.

Aplikace

Semidefinitní programování bylo použito k nalezení přibližných řešení kombinačních optimalizačních problémů, jako je například řešení max. řez problém s přibližný poměr 0,87856. SDP se také používají v geometrii k určení tensegritních grafů a vznikají v teorii řízení jako LMI.

Reference

• Lieven Vandenberghe, Stephen Boyd, „Semidefinite Programming“, SIAM Review 38, březen 1996, str. 49–95. pdf
• Monique Laurent, Franz Rendl, „Semidefinite Programming and Integer Programming“, zpráva PNA-R0210, CWI, Amsterdam, duben 2002. optimalizace-online
• E. de Klerk, „Aspekty semidefinitního programování: Algoritmy vnitřních bodů a vybrané aplikace“, Kluwer Academic Publishers, březen 2002, ISBN  1-4020-0547-4.
• Robert M. Freund, „Úvod do semidefinitního programování (SDP), SDP-Úvod

externí odkazy

• Odkazy na úvody a události v terénu
• Přednášky z László Lovász o semidefinitním programování