Semi-Definite Programmering

Semidefinite programmering (eller SDP från engelska. Semidefinite programmering ) är en underavdelning av konvex programmering , som handlar om optimering av en linjär objektivfunktion (objektivfunktionen är en användarspecificerad funktion vars värde användaren vill minimera eller maximera) vid skärningspunkten mellan koner av positivt halvdefinita matriser med affint utrymme .

Semidefinitiv programmering är ett relativt nytt område för optimering som växer i intresse av flera anledningar. Många praktiska problem inom områdena operationsforskning och kombinatorisk optimering kan modelleras eller approximeras som semidefinita programmeringsproblem. I teorin om automatisk styrning används SDP-problem i samband med linjära matrisojämlikheter . SDP-problem är i själva verket ett specialfall av konisk programmering och kan effektivt lösas med inre punktmetoden . Alla linjära programmeringsproblemkan uttryckas som SDP-problem, och med hjälp av SDP-problemhierarkier kan lösningar på polynomoptimeringsproblem approximeras. Semidefinitiv programmering används vid optimering av komplexa system . Under de senaste åren har vissa problem med kvantfrågekomplexitet formulerats i termer av semidefinite programmering.

Motivation och definition

Inledande motiveringar

Ett linjärt programmeringsproblem är ett problem där du behöver maximera eller minimera en linjär objektiv funktion av reella variabler på en polyeder . I semidefinitiv programmering använder vi istället reala vektorer och vi får använda punktprodukten av vektorer. Villkoret för icke-negativitet för de reella variablerna i LP-problemet ersätts av semi-definititetsbegränsningar på matrisen av variabler för SDP-problemet. I synnerhet kan ett allmänt semidefinitivt programmeringsproblem definieras som vilket matematiskt programmeringsproblem som helst av formen

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

under förhållanden

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

Motsvarande formuleringar

En matris sägs vara positiv halvdefinitiv om den är grammatrisen för vissa vektorer (dvs om det finns vektorer så att för alla ). Om detta är sant kommer vi att beteckna det som . Observera att det finns några andra ekvivalenta definitioner av positiv semidefiniteness, till exempel, positiva semidefinite matriser har bara icke-negativa egenvärden och har en positiv semidefinite kvadratrot. $n\ gånger n$ $M$ ${\displaystyle x^{1},\ldots ,x^{n))$ ${\displaystyle m_{i,j}=x^{i}\cdot x^{j))$ $I j$ $M \succeq 0$

Beteckna med utrymmet för alla reella symmetriska matriser. I detta utrymme finns en inre produkt (där betyder spår ) ${\mathbb {S}}^{n}$ $n\ gånger n$ $\langle A,B\rangle _{\mathbb {S} ^{n}}={\rm {tr}}(A^{T}B)=\summa _{i=1,j=1 }^{n}A_{ij}B_{ij}.$ ${\rm {tr))$

Vi kan skriva om det matematiska programmeringsproblemet från föregående avsnitt i motsvarande form

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

under förhållanden

{\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}}

där matriselementet är lika med från föregående avsnitt och är en matris som har värdet från föregående avsnitt som ett matriselement. $I j$ $C$ $c_{i,j}$ $A_k$ $n\ gånger n$ $I j$ ${\displaystyle a_{i,j,k))$

Observera att om vi lägger till ytterligare variabler korrekt, kan denna SDP-uppgift konverteras till

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

under förhållanden

{\begin{array}{ll}\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 SDP-problemet definieras i en något annorlunda men likvärdig form. Till exempel kan linjära uttryck som använder icke-negativa skalära variabler läggas till i uppgiftsspecifikationen. Uppgiften förblir SDP, eftersom varje variabel kan inkluderas i matrisen som ett diagonalt element ( för vissa ). För att säkerställa kan du lägga till begränsningar för alla . Som ett annat exempel, notera att för alla positiva semidefinite matriser finns det en uppsättning vektorer så att elementet i matrisen är lika med , skalärprodukten av vektorerna och . Sålunda formuleras SDP-problem ofta i termer av linjära uttryck av skalära produkter av vektorer. Givet en lösning på SDP-problemet i standardform kan vektorerna rekonstrueras i tid (till exempel genom att använda en ofullständig nedbrytning av Cholesky- matrisen 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})$

Dualitetsteori

Definitioner

Liknar linjär programmering, om det allmänna problemet SDP anges i formuläret

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

under förhållanden

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

(direkt problem, eller P-SDP), definierar vi det dubbla semidefinita problemet (D-SDP) som

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

under förhållanden

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

Var för två matriser och betyder . $P$ $F$ $P\succeq Q$ $PQ\succeq 0$

Svag dualitet

Den svaga dualitetssatsen säger att den primära SDP har ett värde som inte är mindre än värdet på den dubbla SDP. Sålunda begränsar varje tillåten lösning av det dubbla SDP-problemet värdet av den direkta SDP:n underifrån, och vice versa, vilket som helst tillåtet värde av det direkta SDP-problemet begränsar värdet av den dubbla SDP:n ovanifrån. Detta händer pga

\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 återspeglar det faktum att båda matriserna är positiva semidefinita. Värdet på denna funktion kallas ibland för dubbelspel.

Stark dualitet

Under ett tillstånd som kallas Slater-villkoret är värdena för de primära och dubbla SDP-problemen lika. Detta kallas stark dualitet . Till skillnad från linjära programmeringsproblem har inte alla SDP-problem strikt dualitet. I det allmänna fallet kan värdet av det dubbla problemet SDP vara strikt mindre än värdet av det direkta problemet.

(i) Antag att det direkta problemet (P-SDP) är begränsat underifrån och strikt tillåtet (det vill säga att det finns , så att , ). Då finns det en optimal lösning för det dubbla problemet (D-SDP) och $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) Antag att det dubbla problemet (D-SDP) är begränsat uppifrån och strikt tillåtet (det vill säga för vissa ). Då finns det en optimal lösning för det direkta problemet (P-SDP) och jämställdheten från (i) gäller. $\sum _{i=1}^{m}(y_{0})_{i}A_{i}\prec C$ ${\displaystyle y_{0}\in \mathbb {R} ^{m))$ $X^{*}$

Exempel

Exempel 1

Betrakta tre slumpvariabler och . Per definition är deras korrelationskoefficienter giltiga om och endast om $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

Låt oss anta att vi från vissa källor (till exempel från empiriska eller experimentella data) vet att och . Problemet med att bestämma de minsta och största värdena kan skrivas som: $-0.2\leq \rho _{AB}\leq -0.1$ $0.4\leq \rho _{BC}\leq 0.5$ $\rho _{AC}\$

minimera/maximera

x_{13}

under förhållanden

-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

Här accepterar vi . Problemet kan formuleras som ett SDP-problem. Vi kompletterar ojämlikheterna genom att utöka matrisen av variabler och införa ytterligare variabler , till exempel ${\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\\0&0&0&0&0&0&0}\{end)&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$

Efter att ha löst detta SDP-problem får vi minimi- och maximivärden ( och respektive). $\rho _{AC}=x_{13}\$ $-0,978$ $0,872$

Exempel 2

Tänk på problemet

minimera

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

under förutsättningarna

Ax+b\geq 0

där det antas att vid . $d^{T}x>0$ $Ax+b\geq 0$

Genom att införa en extra variabel skriver vi om problemet i formen: $t$

minimera

t

under förhållanden

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

I denna formulering är objektivfunktionen en linjär funktion av två variabler ( ). $x,t$

Den första begränsningen kan skrivas om som

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

där matris är en kvadratisk matris med värden på diagonalen lika med elementen i vektorn . ${\textbf {diag}}(Ax+b)$ $A+b$

Den andra begränsningen kan skrivas som

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

Vi definierar matrisen enligt följande $D$

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

Vi kan använda Schurs komplementteori för att visa det

D\succeq 0

[ett]

Det halvdefinierade programmeringsproblemet för detta problem kommer att vara av formen

minimera

t

under förhållanden

\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 Approximation Algorithm)

Semidefinitiv programmering är ett viktigt verktyg för att skapa approximationsalgoritmer för NP-hårda maximeringsproblem. Den första approximationsalgoritmen baserad på SDP föreslogs av Michel Goemans och David Williamson [2] . De studerade MAX CUT- problemet : Givet en graf G = ( V , E ), är det nödvändigt att dela upp hörnen av V i två delar på ett sådant sätt att antalet kanter som förbinder dessa två delar maximeras. Problemet kan ses som ett heltals kvadratiskt programmeringsproblem :

Maximera föremål för någon .

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

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

i

Om inte P = NP kan vi inte lösa detta problem effektivt. Men Goemans och Williamson beskrev ett trestegsförfarande för att angripa denna typ av problem:

Vi försvagar det heltals kvadratiska programmeringsproblemet till SDP-problemet.
Vi löser SDP-problemet (med vilket som helst godtyckligt litet fel ). $\epsilon$
Vi avrundar lösningen av SDP-problemet för att få en ungefärlig lösning av det ursprungliga problemet med heltalskvadratprogrammering.

För MAX CUT- problemet är den mest naturliga avslappningen

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

för , där maximering utförs över vektorer snarare än skalära heltalsvariabler.

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

\{v_{i}\}

Problemet är ett SDP-problem eftersom både objektivfunktionen och begränsningarna är linjära funktioner av skalära produkter av vektorer. Lösningen på SDP-problemet ger en uppsättning enhetsvektorer i . Eftersom vektorerna inte nödvändigtvis är kolinjära, kan värdet på det avslappnade problemet bara vara större än värdet på det ursprungliga heltalskvadratprogrammeringsproblemet. En sista avrundningsprocedur behövs för att få delningen. Goemans och Williamson väljer ett slumpmässigt hyperplan (med en enhetlig fördelning) genom ursprunget och delar upp hörnen baserat på deras plats i förhållande till det planet. Direkt analys visar att denna procedur ger den förväntade approximationsfaktorn på 0,87856 - ε. (Förväntningsvärdet för ett snitt är lika med summan över alla kanter av sannolikheterna för att kanten går in i snittet, och denna förväntan är proportionell mot vinkeln mellan vektorerna vid kantens ändpunkt. Om vi jämför denna sannolikhet med , förväntan på förhållandet kommer alltid att vara minst 0,87856.) Om man antar korrekthetshypotesen för det unika spelet kan det visas att approximationskoefficienten för denna approximation huvudsakligen är optimal. $\mathbf {R^{n}}$ $\cos ^{-1}\langle v_{i},v_{j}\rangle$ $(1-\langle v_{i},v_{j}\rangle )/{2}$

Sedan uppsatsen av Goemans och Williamson publicerades har SDP-problem tillämpats på utvecklingen av ett stort antal approximationsalgoritmer. Nyligen utvecklade Prasad Raghavendra ett allmänt schema för problem med begränsningstillfredsställelse baserat på den unika spelhypotesen [3] .

Algoritmer

Det finns flera typer av algoritmer för att lösa SDP-problem. Resultatet av dessa algoritmer är värdet av SDP-problemet upp till , vilket erhålls i en tid som beror polynomiellt på problemets storlek och . $\epsilon$ $\log(1/\epsilon )$

Interior Point Methods

De flesta lösningssystem är baserade på den inre punktmetoden (CSDP, SeDuMi, SDPT3, DSDP, SDPA), som är robust och effektiv för generella linjära SDP-problem. Tillvägagångssättet begränsas i användning av det faktum att algoritmerna är andra ordningens metoder och kräver att stora (och ofta täta) matriser memoreras och dekomponeras.

Första ordningens metoder

Första ordningens metoder för konisk optimering undviker att lagra och bryta ner stora hessiska matriser och är tillämpliga på mycket större problem än inre punktmetoder, till priset av en förlust i noggrannhet. Metoden är implementerad i "SCS solver"-systemet.

Strålmetoden

SDP-problemet är formulerat som ett icke-smidigt optimeringsproblem och löses med spektralstrålemetoden. Detta tillvägagångssätt är mycket effektivt för speciella klasser av linjära SDP-problem.

Andra

Algoritmer baserade på den generaliserade lagrangiska metoden (PENSDP) liknar beteendet med inre punktmetoder och kan anpassas för några mycket stora problem. Andra algoritmer använder lågnivåinformation och omformulerar SDP-problemet till ett icke-linjärt programmeringsproblem (SPDLR).

Applikationer

Semi-definitiv programmering har använts för att hitta ungefärliga lösningar på kombinatoriska optimeringsproblem, som att lösa det maximala cut -problemet med en approximationsfaktor på 0,87856. SDP-problem används också i geometri för att definiera tensegrity-grafer och visas i kontrollteorin som linjära matrisojämlikheter .

Litteratur

Lieven Vandenberghe, Stephen Boyd. Semidefinite programmering // SIAM Review 38. - 1996. - Mars. - S. 49-95 .
Monique Laurent, Franz Rendl. Semidefinite programmering och heltalsprogrammering/rapport PNA-R0210, CWI, Amsterdam . - 2002. - April.
E. de Klerk. Aspekter av Semidefinite Programmering: Interiörpunktalgoritmer och utvalda tillämpningar. - Kluwer Academic Publishers, 2002. - ISBN 1-4020-0547-4 .
P. Raghavendra. Optimala algoritmer och otillräcklighetsresultat för varje CSP? // Proceedings of the 40th Annual ACM Symposium on theory of Computing (Victoria, British Columbia, Kanada, 17–20 maj 2008). STOC'08 . - New York, NY: ACM, 2008. - S. 245-254.
Robert M Freund. Introduktion till Semidefinite Programmering (SDP) .
Michel X. Goemans, David P. Williamson. Förbättrade approximationsalgoritmer för maximal skärning och tillfredsställelseproblem med semidefinite programmering // JACM. - 1995. - November ( vol. 42 , nummer 6 ). - S. 1115-1145 . doi : 10.1145 / 227683.227684 .

Länkar

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

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powells metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering