Seminefinitiv programmering - Semidefinite programming

Semidefinite-programmering ( SDP ) er et underfelt af konveks optimering, der beskæftiger sig med optimeringen af ​​en lineær objektivfunktion (en bruger-specificeret funktion, som brugeren ønsker at minimere eller maksimere) over skæringspunktet mellem keglen til positive semidefinite matrixer med et affin rum , dvs. et spektraeder .

Semidefinitiv programmering er et relativt nyt felt af optimering, der er af voksende interesse af flere grunde. Mange praktiske problemer i driftsundersøgelser og kombinatorisk optimering kan modelleres eller tilnærmes som halvbestemte programmeringsproblemer. I automatisk kontrolteori bruges SDP'er i sammenhæng med lineære matrixuligheder . SDP'er er faktisk et specielt tilfælde af kegleprogrammering og kan effektivt løses ved hjælp af interiørpunkter . Alle lineære programmer kan udtrykkes som SDP'er, og via hierarkier af SDP'er kan løsningen af ​​polynomiske optimeringsproblemer tilnærmes. Semidefinitiv programmering er blevet brugt til optimering af komplekse systemer. I de senere år er der formuleret nogle kvanteforespørgsel-kompleksitetsproblemer med hensyn til halvbestemte programmer.

Motivation og definition

Indledende motivation

Et lineært programmeringsproblem er et problem, hvor vi ønsker at maksimere eller minimere en lineær objektiv funktion af reelle variabler over en polytop . I semidefinitiv programmering bruger vi i stedet virkelige værdsatte vektorer og får lov til at tage dot-produktet af vektorer; nonnegativitetsbegrænsninger på virkelige variabler i LP ( lineær programmering ) erstattes af semidefinitetsbegrænsninger på matrixvariabler i SDP ( semidefinitiv programmering ). Specifikt kan et generelt semidefinitivt programmeringsproblem defineres som ethvert matematisk programmeringsproblem af formen

${\ displaystyle {\ begin {array} {rl} {\ displaystyle \ min _ {x ^ {1}, \ ldots, x ^ {n} \ in \ mathbb {R} ^ {n}}} & {\ displaystyle \ sum _ {i, j \ i [n]} c_ {i, j} (x ^ {i} \ cdot x ^ {j})} \\ {\ text {underlagt}} & {\ displaystyle \ sum _ {i, j \ i [n]} a_ {i, j, k} (x ^ {i} \ cdot x ^ {j}) \ leq b_ {k}} {\ tekst {for alle}} k \ \\ end {matrix}}}$

hvor , og det er reelle tal og er prikproduktet af og . ${\ displaystyle c_ {i, j}, a_ {i, j, k}}$${\ displaystyle b_ {k}}$${\ displaystyle x ^ {i} \ cdot x ^ {j}}$${\ displaystyle x ^ {i}}$${\ displaystyle x ^ {j}}$

Ækvivalente formuleringer

En matrix siges at være positiv semidefinit, hvis det er den gramiske matrix af nogle vektorer (dvs. hvis der findes vektorer, så det for alle ). Hvis dette er tilfældet, betegner vi dette som . Bemærk, at der er adskillige andre ækvivalente definitioner af at være positiv semidefinit, f.eks. Positive semidefinite matrixer er selvadjoint matrixer, der kun har ikke-negative egenværdier. ${\ displaystyle n \ times n}$${\ displaystyle M}$${\ displaystyle x ^ {1}, \ ldots, x ^ {n}}$${\ displaystyle m_ {i, j} = x ^ {i} \ cdot x ^ {j}}$${\ displaystyle i, j}$${\ displaystyle M \ succeq 0}$

Betegn ved rummet for alle rigtige symmetriske matrixer. Rummet er udstyret med det indre produkt (hvor betegner sporingen ) ${\ displaystyle \ mathbb {S} ^ {n}}$${\ displaystyle n \ times n}$${\ displaystyle {\ rm {tr}}}$${\ displaystyle \ langle A, B \ rangle _ {\ mathbb {S} ^ {n}} = {\ rm {tr}} (A ^ {T} B) = \ sum _ {i = 1, j = 1 } ^ {n} A_ {ij} B_ {ij}.}$

Vi kan omskrive det matematiske program, der er givet i det foregående afsnit, ligeligt

${\ displaystyle {\ begin {array} {rl} {\ displaystyle \ min _ {X \ in \ mathbb {S} ^ {n}}} & \ langle C, X \ rangle _ {\ mathbb {S} ^ { n}} \\ {\ text {underlagt}} & \ langle A_ {k}, X \ rangle _ {\ mathbb {S} ^ {n}} \ leq b_ {k}, \ quad k = 1, \ ldots, m \\ & X \ succeq 0 \ end {array}}}$

hvor indgang i er givet ved fra det foregående afsnit og er en symmetrisk matrix med th post fra det foregående afsnit. Således matricerne og er symmetriske og ovennævnte indre produkter er veldefinerede. ${\ displaystyle i, j}$${\ displaystyle C}$${\ displaystyle {\ frac {c_ {i, j} + c_ {j, i}} {2}}}$${\ displaystyle A_ {k}}$${\ displaystyle n \ times n}$${\ displaystyle i, j}$${\ displaystyle {\ frac {a_ {i, j, k} + a_ {j, i, k}} {2}}}$${\ displaystyle C}$${\ displaystyle A_ {k}}$

Bemærk, at hvis vi tilføjer slappe variabler korrekt, kan denne SDP konverteres til en af ​​formularen

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

For nemheds skyld kan en SDP specificeres i en lidt anden, men ækvivalent form. For eksempel kan lineære udtryk, der involverer ikke-negative scalarvariabler, føjes til programspecifikationen. Dette forbliver en SDP, fordi hver variabel kan inkorporeres i matrixen som en diagonal indgang ( for nogle ). For at sikre, at der kan tilføjes begrænsninger for alle . Som et andet eksempel, note at for ethvert positivt semidefinite matrix eksisterer der et sæt af vektorer , således at , optagelse af er det skalarproduktet af og . Derfor formuleres SDP'er ofte med hensyn til lineære udtryk på skalære produkter af vektorer. Givet løsningen på SDP i standardformen, kan vektorerne gendannes i tide (f.eks. Ved anvendelse af en ufuldstændig Cholesky nedbrydning af X). ${\ displaystyle X}$${\ displaystyle X_ {ii}}$${\ displaystyle i}$${\ displaystyle X_ {ii} \ geq 0}$${\ displaystyle X_ {ij} = 0}$${\ displaystyle j \ neq i}$${\ displaystyle X}$${\ displaystyle \ {v_ {i} \}}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle X}$${\ displaystyle X_ {ij} = (v_ {i}, v_ {j})}$${\ displaystyle v_ {i}}$${\ displaystyle v_ {j}}$${\ displaystyle \ {v_ {i} \}}$${\ displaystyle O (n ^ {3})}$

Dualitetsteori

Definitioner

Analogt til lineær programmering, givet en generel SDP af formularen

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

(det primære problem eller P-SDP) definerer vi det dobbelte semidefinite-program (D-SDP) som

${\ displaystyle {\ begin {array} {rl} {\ displaystyle \ max _ {y \ in \ mathbb {R} ^ {m}}} & \ langle b, y \ rangle _ {\ mathbb {R} ^ { m}} \\ {\ text {underlagt}} & {\ displaystyle \ sum _ {i = 1} ^ {m}} y_ {i} A_ {i} \ forud C \ end {array}}}$

hvor for eventuelle to matricer og , midler . ${\ displaystyle P}$${\ displaystyle Q}$${\ displaystyle P \ succeq Q}$${\ displaystyle PQ \ succeq 0}$

Svag dualitet

Den svage dualitetsteorem siger, at værdien af ​​den primære SDP mindst er værdien af ​​den dobbelte SDP. Derfor begrænser enhver mulig løsning på den dobbelte SDP den primære SDP-værdi, og omvendt, enhver mulig løsning på den primære SDP øvre grænser den dobbelte SDP-værdi. Dette er fordi

${\ displaystyle \ 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 skyldes, at begge matrixer er positive semidefinite, og resultatet af denne funktion kaldes undertiden som dualitetsgap.

Stærk dualitet

Under en tilstand, der kaldes Slater's tilstand , er værdien af ​​de primære og dual SDP'er ens. Dette er kendt som stærk dualitet . I modsætning til for lineære programmer tilfredsstiller imidlertid ikke enhver SDP stærk dualitet; generelt kan værdien af ​​det dobbelte SDP ligge strengt under værdien af ​​det primære.

(i) Antag at primal problem (P-SDP) er afgrænset nedenfor og strengt muligt (dvs. der eksisterer sådan, at , ). Så er der en optimal løsning til (D-SDP) og ${\ displaystyle X_ {0} \ in \ mathbb {S} ^ {n}, X_ {0} \ succ 0}$${\ displaystyle \ langle A_ {i}, X_ {0} \ rangle _ {\ mathbb {S} ^ {n}} = b_ {i}}$${\ displaystyle i = 1, \ ldots, m}$${\ displaystyle y ^ {*}}$

${\ displaystyle \ 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 ovenfor og er strengt gennemførligt (dvs. for nogle ). Så er der en optimal løsning på (P-SDP), og ligheden fra (i) holder. ${\ displaystyle \ sum _ {i = 1} ^ {m} (y_ {0}) _ {i} A_ {i} \ prec C}$${\ displaystyle y_ {0} \ in \ mathbb {R} ^ {m}}$${\ displaystyle X ^ {*}}$

eksempler

Eksempel 1

Betragt tre stokastiske variable , og . Per definition er deres korrelationskoefficienter gyldige, hvis og kun hvis ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle C}$ ${\ displaystyle \ rho _ {AB}, \ \ rho _ {AC}, \ rho _ {BC}}$

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

i hvilket tilfælde denne matrix kaldes korrelationsmatrix . Antag, at vi ved en vis forudgående viden (empiriske resultater af et eksperiment, for eksempel), at og . Problemet med at bestemme de mindste og største værdier, der kan tage, gives ved: ${\ displaystyle -0.2 \ leq \ rho _ {AB} \ leq -0.1}$${\ displaystyle 0.4 \ leq \ rho _ {BC} \ leq 0.5}$${\ displaystyle \ rho _ {AC} \}$

minimere / maksimere ${\ displaystyle x_ {13}}$

underlagt

${\ displaystyle -0.2 \ leq x_ {12} \ leq -0.1}$

${\ displaystyle 0.4 \ leq x_ {23} \ leq 0.5}$

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

Vi satte os ind for at få svaret. Dette kan formuleres af en SDP. Vi håndtere ulighedsbegrænsninger ved at øge den variable matrix og indføre slack variabler , f.eks ${\ displaystyle \ rho _ {AB} = x_ {12}, \ \ rho _ {AC} = x_ {13}, \ \ rho _ {BC} = x_ {23}}$

${\ displaystyle \ mathrm {tr} \ venstre (\ venstre ({\ start {array} {cccccc} 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 & 0 & 0 & 0 \ venstre ({\ begin {matrix} {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 & S_ {2} & 0 \\ 0 & 0 & 0 & 0 & 0 & S_ {3} \ end {matrix}} \ højre) \ højre) = x_ {12} + S_ {1} = - 0,1}$

Løse dette SDP giver værdierne af minimale og maksimale som og henholdsvis. ${\ displaystyle \ rho _ {AC} = x_ {13} \}$${\ displaystyle -0.978}$${\ displaystyle 0.872}$

Eksempel 2

Overvej problemet

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

underlagt ${\ displaystyle Ax + b \ geq 0}$

hvor vi antager det hver gang . ${\ displaystyle d ^ {T} x> 0}$${\ displaystyle Ax + b \ geq 0}$

Ved at introducere en hjælpevariabel kan problemet omformuleres: ${\ displaystyle t}$

minimere ${\ displaystyle t}$

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

I denne formulering er målet en lineær funktion af variablerne . ${\ displaystyle x, t}$

Den første begrænsning kan skrives som

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

hvor matrixen er den firkantede matrix med værdier i diagonalen lig med elementerne i vektoren . ${\ displaystyle {\ textbf {diag}} (Ax + b)}$${\ displaystyle Ax + b}$

Den anden begrænsning kan skrives som

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

Definition som følger ${\ displaystyle D}$

${\ displaystyle D = \ venstre [{\ start {array} {cc} t & c ^ {T} x \\ c ^ {T} x & d ^ {T} x \ end {array}} \ højre]}$

Vi kan bruge teorien om Schur Complements for at se det

${\ displaystyle D \ succeq 0}$

(Boyd og Vandenberghe, 1996)

Det halvbestemte program, der er forbundet med dette problem, er

minimere ${\ displaystyle t}$

underlagt ${\ displaystyle \ left [{\ begin {array} {ccc} {\ textbf {diag}} (Ax + b) & 0 & 0 \\ 0 & t & c ^ {T} x \\ 0 & c ^ {T} x & d ^ {T} x \ slut {array}} \ højre] \ succeq 0}$

Eksempel 3 (Goemans-Williamson MAX CUT tilnærmelsesalgoritme)

Semidefinite-programmer er vigtige værktøjer til at udvikle tilnærmelsesalgoritmer til NP-harde maksimeringsproblemer. Den første tilnærmelsesalgoritme baseret på en SDP skyldes Michel Goemans og David P. Williamson (JACM, 1995). De studerede MAX CUT-problemet : Givet en graf G = ( V , E ), udsend en partition af knudepunkterne V for at maksimere antallet af kanter, der krydser fra den ene side til den anden. Dette problem kan udtrykkes som et helt tal kvadratisk program :

Maksimer sådan, at hver .${\ displaystyle \ sum _ {(i, j) \ in E} {\ frac {1-v_ {i} v_ {j}} {2}},}$${\ displaystyle v_ {i} \ in \ {1, -1 \}}$

Medmindre P = NP , kan vi ikke løse dette maksimeringsproblem effektivt. Goemans og Williamson observerede imidlertid en generel tretrinsprocedure til angreb på denne slags problemer:

1. Slap af det heltals kvadratiske program i en SDP.
2. Løs SDP'en (inden for en vilkårlig lille additiv fejl ).${\ displaystyle \ epsilon}$
3. Rund SDP-løsningen for at få en omtrentlig løsning til det originale heltals kvadratiske program.

For MAX CUT er den mest naturlige afslapning

${\ displaystyle \ max \ sum _ {(i, j) \ i E} {\ frac {1- \ langle v_ {i}, v_ {j} \ rangle} {2}},}$sådan at hvor maksimering er over vektorer i stedet for heltalskalarer.${\ displaystyle \ lVert v_ {i} \ rVert ^ {2} = 1}$${\ displaystyle \ {v_ {i} \}}$

Dette er en SDP, fordi objektivfunktionen og begrænsningerne alle er lineære funktioner i indre indre vektorprodukter. Løsning af SDP giver et sæt enhedsvektorer ind ; da vektorerne ikke kræves kollinære, kan værdien af ​​dette afslappede program kun være højere end værdien af ​​det originale kvadratiske heltalsprogram. Endelig er der behov for en afrundingsprocedure for at få en partition. Goemans og Williamson vælger simpelthen et ensartet tilfældigt hyperplan gennem oprindelsen og opdeler toppunktene efter hvilken side af hyperplanet de tilsvarende vektorer ligger. Enkel analyse viser, at denne procedure opnår et forventet tilnærmelsesforhold (ydelsesgaranti) på 0,87856 - ε. (Den forventede værdi af udskæringen er summen over kanterne for sandsynligheden for, at kanten er skåret, hvilket er proportional med vinklen mellem vektorerne ved endepunkterne af kanten over . Sammenligning af denne sandsynlighed til , i forventning er forholdet altid på mindst 0,87856.) Forudsat at den unikke spil-formodning er , kan det vises, at dette tilnærmelsesforhold i det væsentlige er optimalt. ${\ displaystyle \ mathbf {R ^ {n}}}$${\ displaystyle \ cos ^ {- 1} \ langle v_ {i}, v_ {j} \ rangle}$${\ displaystyle \ pi}$${\ displaystyle (1- \ langle v_ {i}, v_ {j} \ rangle) / {2}}$

Siden Goemans og Williamsons originale papir er SDP'er blevet anvendt til at udvikle adskillige tilnærmelsesalgoritmer. For nylig har Prasad Raghavendra udviklet en generel ramme for problemer med begrænsningstilfredshed baseret på Unique Games Conjecture .

Algoritmer

Der er flere typer algoritmer til løsning af SDP'er. Disse algoritmer udsender værdien af ​​SDP op til en additiv fejl i tiden, der er polynomisk i programbeskrivelsesstørrelsen og . ${\ displaystyle \ epsilon}$${\ displaystyle \ log (1 / \ epsilon)}$

Indvendige punktmetoder

De fleste koder er baseret på indre-punkts metoder (FSFP, MOSEK , SeDuMi, SDPT3, DSDP, SDPA). Robust og effektiv til generelle lineære SDP-problemer. Begrænset af det faktum, at algoritmerne er andenordens metoder og har brug for at gemme og faktorisere en stor (og ofte tæt) matrix.

Første ordens metoder

Første ordens metoder til konisk optimering undgår beregning, lagring og faktorisering af en stor Hessian-matrix og skala til meget større problemer end interiørpunkter, til en vis pris i nøjagtighed. En førsteordens metode implementeres i Splitting Cone Solver (SCS). En anden førsteordens metode er multiplikatorernes ADML- metode . Denne metode kræver i hvert trin projektion på keglen til semidefinit matrixer.

Bundle-metode

Koden ConicBundle formulerer SDP-problemet som et problem uden optimering og løser det ved hjælp af Spectral Bundle-metoden til nonsmooth-optimering. Denne tilgang er meget effektiv til en særlig klasse af lineære SDP-problemer.

Andet

Algoritmer baseret på Augmented Lagrangian-metoden (PENSDP) ligner adfærd som de indre punktmetoder og kan specialiseres til nogle meget store skala-problemer. Andre algoritmer bruger information om lav rangering og reformulering af SDP'en som et ikke-lineært programmeringsproblem (SDPLR).

Applikationer

Seminefinitiv programmering er blevet anvendt til at finde tilnærmede løsninger til kombinatoriske optimeringsproblemer, såsom løsningen af max-cut- problemet med et tilnærmelsesforhold på 0,87856. SDP'er bruges også i geometri til at bestemme tensegrity-grafer og opstår i kontrolteori som LMI'er .

Referencer

• Lieven Vandenberghe, Stephen Boyd, "Semidefinite Programming", SIAM Review 38, marts 1996, s. 49–95. pdf
• Monique Laurent, Franz Rendl, "Semidefinite Programming and Integer Programming", Rapport PNA-R0210, CWI, Amsterdam, april 2002. optimering-online
• E. de Klerk, "Aspekter af semidefinit programmering: Interiørpunktalgoritmer og valgte applikationer", Kluwer Academic Publisher, marts 2002, ISBN  1-4020-0547-4 .
• Robert M. Freund, "Introduktion til Semidefinite Programming (SDP), SDP-Introduction

eksterne links

• Links til introduktioner og begivenheder i marken
• Forelæsningsnotater fra László Lovász om Semidefinite Programming