Semidefinite programmering

Semidefinite programmering ( SDP ) är ett delfält av konvex optimering som handlar om optimering av en linjär objektivfunktion (en användarspecificerad funktion som användaren vill minimera eller maximera) över skärningspunkten mellan konen av positiva semidefinita matriser med ett affint utrymme , dvs en spektraeder .

Semidefinite programmering är ett relativt nytt område för optimering som är av växande intresse av flera skäl. Många praktiska problem inom operationsforskning och kombinatorisk optimering kan modelleras eller approximeras som semidefinita programmeringsproblem. I teorin om automatisk styrning används SDP:er i samband med linjära matrisojämlikheter . SDP är i själva verket ett specialfall av konprogrammering och kan effektivt lösas med invändiga punktmetoder . Alla linjära program och (konvexa) kvadratiska program kan uttryckas som SDP:er, och via hierarkier av SDP:er kan lösningarna av polynomoptimeringsproblem approximeras. Semidefinite programmering har använts vid optimering av komplexa system. Under de senaste åren har vissa problem med kvantfrågekomplexitet formulerats i termer av semidefinita program.

Motivation och definition

Initial motivation

Ett linjärt programmeringsproblem är ett problem där vi vill maximera eller minimera en linjär objektiv funktion av reella variabler över en polytop . I semidefinite programmering använder vi istället realvärderade vektorer och får ta prickprodukten av vektorer; icke-negativitetsbegränsningar på reella variabler i LP ( linjär programmering ) ersätts av semidefiniteness-begränsningar på matrisvariabler i SDP ( semidefinite programmering ). Specifikt kan ett allmänt semidefinitivt programmeringsproblem definieras som vilket matematiskt programmeringsproblem som helst av formen

${\begin{array}{rl}{\displaystyle \min _{x^{1},\ldots ,x^{n}\in \mathbb {R} ^ {n}}}&{\displaystyle \sum _{i,j\in [n]}c_{i,j}(x^{i}\cdot x^{j})}\\{\text{ämne till}}&{\displaystyle \sum _{i,j\in [n]}a_{i,j,k}(x^{i}\cdot x^{j})\leq b_{k}}{ \text{ för alla }}k\\\end{array}}$

där $c_{i,j},a_{i,j,k}$ och $b_{k}$ är reella tal och $x^{i}\cdot x^{j}$ är punktprodukten av $x^{i}$ och $x^{j}$ .

Likvärdiga formuleringar

En $n\times n$ matris $M$ sägs vara positiv semidefinit om den är grammatrisen för vissa vektorer (dvs. om det finns vektorer $x^{1},\ldots ,x^{n}$ så att $m_{i,j}=x^{i}\cdot x^{j}$ för alla $i,j$ ). Om så är fallet betecknar vi detta som $M\succeq 0$ . Observera att det finns flera andra ekvivalenta definitioner av att vara positiv semidefinit, till exempel är positiva semidefinita matriser självadjointade matriser som bara har icke-negativa egenvärden .

Beteckna med $\mathbb {S} ^{n}$ utrymmet för alla $n\ gånger n$ reella symmetriska matriser. Utrymmet är utrustat med den inre produkten (där ${\rm {tr}}$ betecknar spåret ) $\langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\summa _{i=1,j=1 }^{n}A_{ij}B_{ij}.$

Vi kan skriva om det matematiska programmet i föregående avsnitt på motsvarande sätt som

${\begin{array}{rl}{ \displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{med förbehåll för}} &\langle A_{k},X\rangle _{\mathbb {S} ^{n}}\leq b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{ array}}$

där posten $i,j$ i $C$ ges av ${\frac {c_{i,j}+c_{j, i}}{2}}$ från föregående avsnitt och $A_{k}$ är en symmetrisk $n\times n$ matris som har $i,j$ th post ${\frac {a_{i,j,k}+a_{j,i,k}}{2}}$ från föregående avsnitt. Sålunda är matriserna $C$ och $A_{k}$ symmetriska och ovanstående inre produkter är väldefinierade.

Observera att om vi lägger till slackvariabler på lämpligt sätt kan denna SDP konverteras till en av formerna

${\begin{array}{rl}{ \displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{med förbehåll för}} &\langle A_{k},X\rangle _{\mathbb {S} ^{n}}=b_{k},\quad k=1,\ldots ,m\\&X\succeq 0.\end{array }}$

För enkelhetens skull kan en SDP specificeras i en något annorlunda, men likvärdig form. Till exempel kan linjära uttryck som involverar icke-negativa skalära variabler läggas till i programspecifikationen. Detta förblir en SDP eftersom varje variabel kan inkorporeras i matrisen $X$ som en diagonal post ( $X_{ii}$ för vissa $i$ ). För att säkerställa att ${\displaystyle X_{ii}\geq 0} , kan$ begränsningar $X_{ij}=0$ läggas till för alla $j\neq i$ . Som ett annat exempel, notera att för varje positiv semidefinitiv matris $X$ finns det en uppsättning vektorer $\{v_{i}\}$ så att $i$ , $j$ -posten i $X$ är ${\displaystyle X_{ij}=(v_{i},v_{j})$ } skalärprodukten av $v_{i}$ och $v_{j}$ . Därför formuleras SDP ofta i termer av linjära uttryck på skalära produkter av vektorer. Givet lösningen till SDP i standardformen, kan vektorerna $\{v_{i}\}$ återställas i $O(n^{3})$ tid (t.ex. genom att använda en ofullständig Cholesky-nedbrytning av X).

Dualitetsteori

Definitioner

Analogt med linjär programmering, givet en generell SDP av formen

${\begin{array}{rl}{\displaystyle \min _{X\in \mathbb {S} ^{n}}}&\langle C,X\rangle _{\mathbb {S} ^{n}}\\{\text{med förbehåll för}}&\ langle A_{i},X\rangle _{\mathbb {S} ^{n}}=b_{i},\quad i=1,\ldots ,m\\&X\succeq 0\end{array}}$

(det primära problemet eller P-SDP), definierar vi det dubbla semidefinita programmet (D-SDP) som

${\begin{array}{rl}{\displaystyle \max _{y\in \mathbb { R} ^{m}}}&\langle b,y\rangle _{\mathbb {R} ^{m}}\\{\text{med förbehåll för}}&{\displaystyle \sum _{i=1} ^{m}}y_{i}A_{i}\preceq C\end{array}}$

där för två valfria matriser $P$ och $Q$ , $P\succeq Q$ betyder $PQ\succeq 0$ .

Svag dualitet

Den svaga dualitetssatsen säger att värdet av den primära SDP:en är åtminstone värdet av den dubbla SDP:n. Därför begränsar varje möjlig lösning till den dubbla SDP:en det primära SDP-värdet, och omvänt, varje genomförbar lösning på den primära SDP:en övre gränsen för det dubbla SDP-värdet. Det här är för att

$\langle C,X\rangle -\langle b,y\rangle =\langle C,X\rangle -\summa _{i=1} ^{m}y_{i}b_{i}=\langle C,X\rangle -\summa _{i=1}^{m}y_{i}\langle A_{i},X\rangle =\langle C-\summa _{i=1}^{m}y_{i}A_{i},X\rangle \geq 0,$

där den sista olikheten beror på att båda matriserna är positiva semidefinita, och resultatet av denna funktion kallas ibland för dualitetsgap.

Stark dualitet

När värdet på de primära och dubbla SDP:erna är lika, sägs SDP:en tillfredsställa den starka dualitetsegenskapen . Till skillnad från linjära program , där varje dubbellinjärt program har ett optimalt mål som är lika med det primära målet, uppfyller inte varje SDP stark dualitet; i allmänhet kan värdet på den dubbla SDP:en ligga strikt under värdet av den primära, och P-SDP och D-SPD uppfyller följande egenskaper:

(i) Antag att det primära problemet (P-SDP) är begränsat nedanför och strikt genomförbart (dvs det finns $X_{0}\i \mathbb {S} ^{n},X_ {0}\succ 0$ så att $\langle A_{i},X_{0}\rangle _{\mathbb {S} ^{n}}=b_ {i}$ , ${\displaystyle i=1,\ldots ,m} )$ . Då finns det en optimal lösning $y^{*}$ till (D-SDP) och

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

(ii) Antag att det dubbla problemet (D-SDP) är begränsat ovanför och strikt genomförbart (dvs. $\sum _{i=1}^{m}( y_{0})_{i}A_{i}\prec C$ för vissa ${\displaystyle y_{0}\in \mathbb {R} ^{m}} )$ . Då finns det en optimal lösning $X^{*}$ till (P-SDP) och likheten från (i) gäller.

Ett tillräckligt villkor för att stark dualitet ska gälla för ett SDP-problem (och i allmänhet för alla konvexa optimeringsproblem) är Slaters tillstånd . Det är också möjligt att uppnå stark dualitet för SDP:er utan ytterligare regularitetsvillkor genom att använda ett utökat dubbelproblem som föreslagits av Ramana.

Exempel

Exempel 1

Betrakta tre slumpvariabler $A$ , $B$ och $C$ . Per definition är deras korrelationskoefficienter $\rho _{AB},\ \rho _{AC},\rho _{BC}$ giltiga om och endast om

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

i så fall kallas denna matris för korrelationsmatrisen . Antag att vi från vissa förkunskaper (exempelvis empiriska resultat av ett experiment) vet att $-0,2\leq \rho _{AB}\leq -0,1$ och $0,4\leq \rho _{BC}\leq 0,5$ . Problemet med att bestämma de minsta och största värdena som $\rho _{AC}\$ kan ta ges av:

${\ }{\displaystyle \min /\max }&x_{13}\\{\text{med förbehåll för}}&-0.2\leq x_{12}\leq -0.1\\&0.4\leq x_{23}\leq 0.5\\&{\begin{pmatrix}1&x_{12}&x_{13}\\x_{12}&1&x_{23}\\x_{13}&x_{23}&1\end{pmatrix}}\succeq 0\end {array}}$

Vi sätter $\rho _{AB}=x_{12},\ \rho _{AC}=x_{13}, \ \rho _{BC}=x_{23}$ för att få svaret. Detta kan formuleras av en SDP. Vi hanterar ojämlikhetsbegränsningarna genom att utöka variabelmatrisen och introducera slackvariabler , till exempel

$\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\\0&0&0&0&0&0\\0&0&0&0&0&0&0}\end {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_\0&0\\0&0_\} 0&0&0&0&0&s_{3}\end{array}}\right)\right)=x_{12}+s_{1}=-0.1$

Att lösa denna SDP ger minimi- och maxvärdena för $\rho _{AC}=x_{13}\$ som $-0,978$ respektive $0,872$ .

Exempel 2

Tänk på problemet

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

med förbehåll för $Ax+b\geq 0$

där vi antar att $d^{T}x>0$ närhelst $Ax+b\geq 0$ .

Genom att introducera en hjälpvariabel $t$ kan problemet omformuleras:

minimera $t$

med förbehåll för $Ax+b\geq 0,\,{\frac {(c^{T}x) ^{2}}{d^{T}x}}\leq t$

I denna formulering är målet en linjär funktion av variablerna $x,t$ .

Den första begränsningen kan skrivas som

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

där matrisen ${\textbf {diag}}(Ax+b)$ är den kvadratiska matrisen med värden i diagonalen lika med elementen i vektorn $Ax +b$ .

Den andra begränsningen kan skrivas som

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

Definierar $D$ enligt följande

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

Vi kan använda teorin om Schur Complements för att se det

$D\succeq 0$

(Boyd och Vandenberghe, 1996)

Det semidefinita programmet som är associerat med detta problem är

minimera $t$

med förbehåll för $\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$

Exempel 3 (Goemans–Williamson max cut approximationsalgoritm)

Semidefinita program är viktiga verktyg för att utveckla approximationsalgoritmer för NP-hårda maximeringsproblem. Den första approximationsalgoritmen baserad på en SDP beror på Michel Goemans och David P. Williamson (JACM, 1995). De studerade maxsnittsproblemet : Givet en graf G = ( V , E ), mata ut en partition av hörnen V för att maximera antalet kanter som korsar från ena sidan till den andra. Detta problem kan uttryckas som ett heltals kvadratiskt program :

Maximera $\sum _{(i,j)\in E}{\frac {1-v_{i}v_{j}}{2 }},$ så att varje $v_{i}\in \{1,-1\}$ .

Om inte P = NP kan vi inte lösa detta maximeringsproblem effektivt. Men Goemans och Williamson observerade en allmän trestegsprocedur för att attackera denna typ av problem:

1. Koppla av heltalskvadratprogrammet till en SDP.
2. Lös SDP (till inom ett godtyckligt litet additivt fel ${\displaystyle \epsilon } )$ .
3. Runda SDP-lösningen för att få en ungefärlig lösning till det ursprungliga heltalskvadratprogrammet.

För max cut är den mest naturliga avslappningen

$\max \sum _{(i,j)\in E}{\frac {1-\langle v_{i} ,v_{j}\rangle }{2}},$ så att $\lVert v_{i}\rVert ^{2}=1$ , där maximeringen är över vektorer $\{v_{i}\}$ istället för heltalsskalärer.

Detta är en SDP eftersom objektivfunktionen och begränsningarna alla är linjära funktioner hos vektorinre produkter. Lösning av SDP ger en uppsättning enhetsvektorer i $\mathbf {R^{n}}$ ; eftersom vektorerna inte behöver vara kolinjära kan värdet på detta avslappnade program bara vara högre än värdet på det ursprungliga kvadratiska heltalsprogrammet. Slutligen behövs en avrundningsprocedur för att få en partition. Goemans och Williamson väljer helt enkelt ett likformigt slumpmässigt hyperplan genom origo och delar upp hörnen efter vilken sida av hyperplanet motsvarande vektorer ligger. Enkel analys visar att denna procedur uppnår ett förväntat approximationsförhållande (prestandagaranti) på 0,87856 - ε. (Det förväntade värdet av skärningen är summan över kanter av sannolikheten att kanten skärs, vilket är proportionellt mot vinkeln $\cos ^{-1}\langle v_{i},v_{j}\rangle$ mellan vektorerna vid ändpunkterna av kanten över $\pi$ Jämför denna sannolikhet med ${\displaystyle (1-\langle v_{i},v_{j}\rangle )/{2}} ,$ i förväntan är förhållandet alltid minst 0,87856.) Om man antar den unika spelförmodan kan det visas att detta approximationsförhållande i huvudsak är optimal.

Sedan den ursprungliga uppsatsen av Goemans och Williamson har SDP:er använts för att utveckla många approximationsalgoritmer. Nyligen har Prasad Raghavendra utvecklat ett allmänt ramverk för problem med tillfredsställelse av begränsningar baserat på den unika spelförmodan .

Algoritmer

Det finns flera typer av algoritmer för att lösa SDP:er. Dessa algoritmer matar ut värdet på SDP upp till ett additivt fel $\epsilon$ i tid som är polynom i programbeskrivningens storlek och $\log(1/\epsilon )$ .

Det finns också ansiktsreduktionsalgoritmer som kan användas för att förbehandla SDP-problem genom att inspektera problemets begränsningar. Dessa kan användas för att upptäcka brist på strikt genomförbarhet, för att ta bort redundanta rader och kolumner, och även för att minska storleken på variabelmatrisen.

Invändiga punktmetoder

De flesta koder är baserade på inre punktmetoder (CSDP, MOSEK , SeDuMi, SDPT3 , DSDP, SDPA). Dessa är robusta och effektiva för generella linjära SDP-problem, men begränsade av det faktum att algoritmerna är andra ordningens metoder och behöver lagra och faktorisera en stor (och ofta tät) matris. Teoretiskt sett är de toppmoderna SDP-algoritmerna med hög precision baserade på detta tillvägagångssätt.

Första ordningens metoder

Första ordningens metoder för konisk optimering undviker att beräkna, lagra och faktorisera en stor hessisk matris och skala till mycket större problem än inre punktmetoder, till viss kostnad i noggrannhet. En första ordningens metod är implementerad i Splitting Cone Solver (SCS). En annan första ordningens metod är den alternerande riktningsmetoden för multiplikatorer ( ADMM). Denna metod kräver i varje steg projektion på konen av semidefinita matriser.

Buntmetoden

Koden ConicBundle formulerar SDP-problemet som ett ojämnt optimeringsproblem och löser det med Spectral Bundle-metoden för ojämn optimering. Detta tillvägagångssätt är mycket effektivt för en speciell klass av linjära SDP-problem.

Andra lösningsmetoder

Algoritmer baserade på Augmented Lagrangian-metoden (PENSDP) liknar i beteende de inre punktmetoderna och kan specialiseras på vissa mycket storskaliga problem. Andra algoritmer använder lågrankad information och omformulering av SDP som ett icke-linjärt programmeringsproblem (SDPLR).

Ungefärliga metoder

Algoritmer som ungefär löser SDP:er har också föreslagits. Huvudmålet med sådana metoder är att uppnå lägre komplexitet i applikationer där ungefärliga lösningar är tillräckliga och komplexiteten måste vara minimal. En framträdande metod som har använts för datadetektering i trådlösa MIMO-system (multiple-input multiple-output) är Triangular Approximate SEmidefinite Relaxation (TASER), som arbetar på Cholesky-nedbrytningsfaktorerna för den semidefinita matrisen istället för den semidefinite matrisen. Denna metod beräknar ungefärliga lösningar för ett max-cut-liknande problem som ofta är jämförbara med lösningar från exakta lösare men i endast 10-20 algoritmiterationer.

Ansökningar

Semidefinite programmering har använts för att hitta ungefärliga lösningar på kombinatoriska optimeringsproblem, såsom lösningen av max cut -problemet med ett approximationsförhållande på 0,87856. SDP:er används också i geometri för att bestämma tensegritetsgrafer och uppstår i kontrollteori som LMI:er och i inversa elliptiska koefficientproblem som konvexa, icke-linjära, semidefiniteness-begränsningar. Det används också i stor utsträckning inom fysik för att begränsa konforma fältteorier med den konforma bootstrap .

• Lieven Vandenberghe, Stephen Boyd, "Semidefinite Programming", SIAM Review 38, mars 1996, s. 49–95. pdf
• Monique Laurent, Franz Rendl, "Semidefinite Programming and Integer Programming", Rapport PNA-R0210, CWI, Amsterdam, april 2002. optimization-online
•   E. de Klerk, "Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications", Kluwer Academic Publishers, mars 2002, ISBN 1-4020-0547-4 .
• Robert M. Freund, "Introduktion till Semidefinite Programmering (SDP), SDP-Introduktion

externa länkar

• Länkar till introduktioner och evenemang inom området
• Föreläsningsanteckningar från László Lovász om Semidefinite Programmering