Semi-Definite Programmering

Semidefinite programmering (eller SDP fra engelsk. Semidefinite programming ) er en underafsnit af konveks programmering , som omhandler optimering af en lineær objektivfunktion (objektivfunktionen er en brugerspecificeret funktion, hvis værdi brugeren ønsker at minimere eller maksimere) ved skæring af kegler af positivt semibestemte matricer med affint rum .

Semi-bestemt programmering er et relativt nyt område for optimering, der vokser i interesse af flere årsager. Mange praktiske problemer inden for operationsforskning og kombinatorisk optimering kan modelleres eller tilnærmes som semi-definite programmeringsproblemer. I automatisk kontrolteori bruges SDP-problemer i sammenhæng med lineære matrixuligheder . SDP-problemer er i virkeligheden et særligt tilfælde af kegleprogrammering og kan effektivt løses ved hjælp af den indre punktmetode . Alle lineære programmeringsproblemer kan udtrykkes som SDP-problemer, og ved hjælp af SDP-problemhierarkier kan løsninger på polynomielle optimeringsproblemer tilnærmes. Semi-bestemt programmering bruges til optimering af komplekse systemer . I de senere år er nogle kvanteforespørgselskompleksitetsproblemer blevet formuleret i form af semibestemt programmering.

Motivation og definition

Indledende motiveringer

Et lineært programmeringsproblem er et problem , hvor du skal maksimere eller minimere en lineær objektiv funktion af reelle variable på et polyeder . I semi-bestemt programmering bruger vi i stedet reelle vektorer, og vi har lov til at bruge punktproduktet af vektorer. Betingelsen for ikke-negativitet af de reelle variabler i LP-problemet erstattes af semi-definiteness-begrænsninger på matricen af variabler i SDP-problemet. Især kan et generelt semibestemt programmeringsproblem defineres som et hvilket som helst matematisk programmeringsproblem af 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 forhold

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

Tilsvarende formuleringer

En matrix siges at være positiv semidefinit , hvis den er grammatricen for nogle vektorer (dvs. hvis der er vektorer , således at for alle ). Hvis dette er sandt, vil vi betegne det som . Bemærk, at der er nogle andre ækvivalente definitioner af positiv semidefiniteness, for eksempel har positive semidefinite matricer kun ikke-negative egenværdier og har en positiv semidefinite kvadratrod. $n\ gange n$ $M$ ${\displaystyle x^{1},\ldots,x^{n))$ ${\displaystyle m_{i,j}=x^{i}\cdot x^{j))$ $i,j$ $M \succeq 0$

Betegn med rummet af alle reelle symmetriske matricer. I dette rum er der et indre produkt (hvor betyder spor ) ${\mathbb {S}}^{n}$ $n\ gange 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))$

Vi kan omskrive det matematiske programmeringsproblem fra forrige afsnit i tilsvarende form

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

under forhold

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

hvor matrixelementet er lig med fra forrige afsnit, og er en matrix, der har værdien fra forrige afsnit som matrixelement. $i,j$ $C$ ${\displaystyle c_{i,j))$ $A_k$ $n\ gange n$ $i,j$ ${\displaystyle a_{i,j,k))$

Bemærk, at hvis vi tilføjer yderligere variabler korrekt, kan denne SDP-opgave konverteres til

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

under forhold

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

For nemheds skyld kan SDP-problemet defineres i en lidt anderledes, men tilsvarende form. For eksempel kan lineære udtryk, der bruger ikke-negative skalarvariabler , tilføjes til opgavespecifikationen. Opgaven forbliver SDP, da hver variabel kan inkluderes i matricen som et diagonalt element ( for nogle ). For at sikre , kan du tilføje begrænsninger for alle . Som et andet eksempel skal du bemærke, at for enhver positiv semidefinit matrix er der et sæt vektorer , således at elementet i matrixen er lig med , skalarproduktet af vektorerne og . SDP-problemer er således ofte formuleret i form af lineære udtryk for skalarprodukter af vektorer. Givet en løsning på SDP-problemet i standardform, kan vektorerne rekonstrueres i tide (for eksempel ved at bruge en ufuldstændig dekomponering af Cholesky -matrixen X). $x$ ${\displaystyle X_{ii))$ $jeg$ $X_{ii}\geq 0$ $X_{ij}=0$ $j\neq i$ $x$ $\{v_{i}\}$ $jeg$ $j$ $x$ $X_{ij}=(v_{i},v_{j})$ $v_{i}$ $v_{j}$ $\{v_{i}\}$ $O(n^{3})$

Dualitetsteori

Definitioner

Svarende til lineær programmering, hvis det generelle problem SDP er angivet i formularen

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

under forhold

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

(direkte problem eller P-SDP), definerer vi det dobbelte semidefinite problem (D-SDP) som

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

under forhold

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

Hvor for alle to matricer og , betyder . $P$ $Q$ $P\succeq Q$ $PQ\succeq 0$

Svag dualitet

Den svage dualitetssætning siger, at den primære SDP har en værdi, der ikke er mindre end værdien af den dobbelte SDP. Enhver tilladt løsning af det dobbelte SDP-problem begrænser således værdien af den direkte SDP nedefra, og omvendt begrænser enhver tilladelig værdi af det direkte SDP-problem værdien af den dobbelte SDP ovenfra. Dette sker pga

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

hvor den sidste ulighed afspejler det faktum, at begge matricer er positive semidefinite. Værdien af denne funktion kaldes nogle gange det dobbelte mellemrum.

Stærk dualitet

Under en tilstand kendt som Slater-tilstanden er værdierne af de primære og dobbelte SDP-problemer ens. Dette kaldes stærk dualitet . I modsætning til lineære programmeringsproblemer har ikke alle SDP-problemer streng dualitet. I det generelle tilfælde kan værdien af det dobbelte problem SDP være strengt mindre end værdien af det direkte problem.

(i) Antag, at det direkte problem (P-SDP) er afgrænset nedefra og strengt tilladt (det vil sige, at der eksisterer , sådan at , ). Så er der en optimal løsning på det dobbelte problem (D-SDP) og $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, at det dobbelte problem (D-SDP) er afgrænset ovenfra og strengt tilladt (det vil sige for nogle ). Så er der en optimal løsning på det direkte problem (P-SDP) og ligestillingen fra (i) gælder. $\sum _{i=1}^{m}(y_{0})_{i}A_{i}\prec C$ ${\displaystyle y_{0}\in \mathbb {R} ^{m))$ $X^{*}$

Eksempler

Eksempel 1

Overvej tre tilfældige variable , og . Per definition er deres korrelationskoefficienter gyldige hvis og kun hvis $EN$ $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

Lad os antage, at vi fra nogle kilder (for eksempel fra empiriske eller eksperimentelle data) ved, at og . Problemet med at bestemme de mindste og største værdier kan skrives som: $-0.2\leq \rho _{AB}\leq -0.1$ $0.4\leq \rho _{BC}\leq 0.5$ $\rho _{AC}\$

minimere/maksimere

x_{13}

under forhold

-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

Her tager vi imod . Problemstillingen kan formuleres som et SDP-problem. Vi fuldender ulighederne ved at udvide matricen af variabler og introducere yderligere variable , for eksempel ${\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}\t \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 at have løst dette SDP-problem opnår vi minimums- og maksimumværdierne ( hhv .). $\rho _{AC}=x_{13}\$ $-0,978$ $0.872$

Eksempel 2

Overvej problemet

minimere

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

under betingelserne

Ax+b\geq 0

hvor det antages at kl . $d^{T}x>0$ $Ax+b\geq 0$

Ved at introducere en ekstra variabel omskriver vi problemet i formen: $t$

minimere

t

under forhold

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

I denne formulering er objektivfunktionen en lineær funktion af to variable ( ). $x,t$

Den første begrænsning kan omskrives som

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

hvor matrix er en kvadratisk matrix med værdier på diagonalen lig med vektorens elementer . ${\textbf {diag}}(Ax+b)$ $A+b$

Den anden begrænsning kan skrives som

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

Vi definerer matrixen som følger $D$

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

Det kan vi bruge Schurs komplementteori til at vise

D\succeq 0

[en]

Det semi-definitive programmeringsproblem for dette problem vil være af formen

minimere

t

under forhold

\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

Eksempel 3 (Goemans-Williamson MAX CUT Approximation Algorithm)

Semi-bestemt programmering er et vigtigt værktøj til at skabe tilnærmelsesalgoritmer til NP-hårde maksimeringsproblemer. Den første tilnærmelsesalgoritme baseret på SDP blev foreslået af Michel Goemans og David Williamson [2] . De undersøgte MAX CUT- problemet : Givet en graf G = ( V , E ), er det nødvendigt at opdele V -spidserne i to dele på en sådan måde, at antallet af kanter, der forbinder disse to dele, maksimeres. Problemet kan opfattes som et heltals kvadratisk programmeringsproblem :

Maksimer underlagt evt .

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

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

jeg

Medmindre P = NP , kan vi ikke løse dette problem effektivt. Men Goemans og Williamson skitserede en tre-trins procedure for at angribe denne form for problem:

Vi svækker det kvadratiske heltalsprogrammeringsproblem til SDP-problemet.
Vi løser SDP-problemet (med enhver vilkårlig lille fejl ). $\epsilon$
Vi runder løsningen af SDP-problemet af for at opnå en omtrentlig løsning på det oprindelige problem med heltals kvadratisk programmering.

For MAX CUT- problemet er den mest naturlige afslapning

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

for , hvor maksimering udføres over vektorer frem for skalære heltalsvariable.

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

\{v_{i}\}

Problemet er et SDP-problem, fordi både den objektive funktion og begrænsningerne er lineære funktioner af skalarprodukterne af vektorer. Løsningen på SDP-problemet giver et sæt enhedsvektorer i . Da vektorerne ikke nødvendigvis er kollineære, kan værdien af det afslappede problem kun være større end værdien af det oprindelige heltals kvadratiske programmeringsproblem. En sidste afrundingsprocedure er nødvendig for at få opdelingen. Goemans og Williamson vælger et tilfældigt hyperplan (ved hjælp af en ensartet fordeling) gennem oprindelsen og opdeler hjørnerne baseret på deres placering i forhold til dette plan. Direkte analyse viser, at denne procedure giver den forventede tilnærmelsesfaktor på 0,87856 - ε. (Forventningsværdien af et snit er lig med summen over alle kanter af sandsynligheden for, at kanten går ind i snittet, og denne forventning er proportional med vinklen mellem vektorerne ved kantens endespidser. Hvis vi sammenligner denne sandsynlighed med , vil forventningen til forholdet altid være mindst 0,87856.) Forudsat korrekthedshypotesen for det unikke spil kan det påvises, at approksimationskoefficienten for denne tilnærmelse hovedsageligt er optimal. $\mathbf {R^{n}}$ $\cos ^{-1}\langle v_{i},v_{j}\rangle$ ${\displaystyle (1-\langle v_{i},v_{j}\rangle )/{2))$

Siden fremkomsten af papiret af Goemans og Williamson, er SDP-problemer blevet anvendt på udviklingen af et stort antal tilnærmelsesalgoritmer. For nylig udviklede Prasad Raghavendra en generel ordning for problemer med begrænsningstilfredshed baseret på den unikke spilhypotese [3] .

Algoritmer

Der findes flere typer algoritmer til løsning af SDP-problemer. Resultatet af disse algoritmer er værdien af SDP-problemet op til , som opnås i en tid, der afhænger polynomisk af problemets størrelse og . $\epsilon$ $\log(1/\epsilon )$

Interior Point Methods

De fleste løsningssystemer er baseret på den indre punktmetode (CSDP, SeDuMi, SDPT3, DSDP, SDPA), som er robust og effektiv til generelle lineære SDP-problemer. Tilgangen er begrænset i brug af det faktum, at algoritmerne er andenordens metoder og kræver store (og ofte tætte) matricer, der skal huskes og dekomponeres.

Første ordensmetoder

Førsteordensmetoder til konisk optimering undgår lagring og nedbrydning af store hessiske matricer og er anvendelige til meget større problemer end indre punktmetoder på bekostning af et tab i præcision. Metoden er implementeret i "SCS solver" systemet.

Strålemetoden

SDP-problemet er formuleret som et ikke-glat optimeringsproblem og løses ved spektralstrålemetoden. Denne tilgang er meget effektiv til særlige klasser af lineære SDP-problemer.

Andre

Algoritmer baseret på den generaliserede lagrangiske metode (PENSDP) ligner i adfærd til indre punktmetoder og kan tilpasses til nogle meget store problemer. Andre algoritmer bruger information på lavt niveau og omformulerer SDP-problemet som et ikke-lineært programmeringsproblem (SPDLR).

Ansøgninger

Semi-bestemt programmering er blevet brugt til at finde omtrentlige løsninger på kombinatoriske optimeringsproblemer, såsom at løse det maksimale cut -problem med en tilnærmelsesfaktor på 0,87856. SDP-problemer bruges også i geometri til at definere tensegrity-grafer og optræder i kontrolteori som lineære matrixuligheder .

Litteratur

Lieven Vandenberghe, Stephen Boyd. Semidefinite Programmering // SIAM Review 38. - 1996. - Marts. - S. 49-95 .
Monique Laurent, Franz Rendl. Semidefinite programmering og heltalsprogrammering/rapport PNA-R0210, CWI, Amsterdam . - 2002. - April.
E. de Klerk. Aspekter af semibestemt programmering: Indvendige punktalgoritmer og udvalgte applikationer. - Kluwer Academic Publishers, 2002. - ISBN 1-4020-0547-4 .
P. Raghavendra. Optimale algoritmer og utilnærmelighedsresultater for hver CSP? // Proceedings of the 40th Annual ACM Symposium on theory of Computing (Victoria, British Columbia, Canada, 17.-20. maj 2008). STOC'08 . - New York, NY: ACM, 2008. - S. 245-254.
Robert M Freund. Introduktion til Semidefinite Programmering (SDP) .
Michel X. Goemans, David P. Williamson. Forbedrede tilnærmelsesalgoritmer til maksimal snit- og tilfredshedsproblemer ved brug af semidefinite programmering // JACM. - 1995. - November ( bind 42 , hæfte 6 ). - S. 1115-1145 . doi : 10.1145 / 227683.227684 .

Links

Links til introduktioner og arrangementer på området
Forelæsningsnoter fra László Lovász om Semidefinite Programmering

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algoritme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentiel metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering