Programare semidefinită

Programarea semidefinită (sau SDP din engleză. Programarea semidefinită ) este o subsecțiune a programării convexe , care se ocupă cu optimizarea unei funcții obiectiv liniare (funcția obiectiv este o funcție specificată de utilizator a cărei valoare utilizatorul dorește să o minimizeze sau să o maximizeze) la intersectia conurilor de matrice pozitiv semidefinite cu spatiu afin .

Programarea semidefinită este o zonă de optimizare relativ nouă, care crește în interes din mai multe motive. Multe probleme practice din domeniile cercetării operaționale și optimizării combinatorii pot fi modelate sau aproximate ca probleme de programare semidefinite. În teoria controlului automat, problemele SDP sunt utilizate în contextul inegalităților matriceale liniare . Problemele SDP sunt, de fapt, un caz special de programare conică și pot fi rezolvate eficient prin metoda punctului interior . Toate problemele de programare liniară pot fi exprimate ca probleme SDP și folosind ierarhiile de probleme SDP, soluțiile la problemele de optimizare polinomială pot fi aproximate. Programarea semidefinită este utilizată în optimizarea sistemelor complexe . În ultimii ani, unele probleme de complexitate a interogărilor cuantice au fost formulate în termeni de programare semidefinită.

Motivație și definiție

Motivații inițiale

O problemă de programare liniară este o problemă în care trebuie să maximizați sau să minimizați o funcție obiectiv liniară a variabilelor reale pe un poliedru . În programarea semidefinită, folosim în schimb vectori reali și avem voie să folosim produsul scalar al vectorilor. Condiția de non-negativitate a variabilelor reale ale problemei LP este înlocuită de constrângeri de semidefiniție pe matricea de variabile ale problemei SDP. În special, o problemă generală de programare semidefinită poate fi definită ca orice problemă de programare matematică de formă

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

in conditii

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

Formulări echivalente

Se spune că o matrice este semidefinită pozitivă dacă este matricea Gram a unor vectori (adică, dacă există vectori astfel încât pentru toți ). Dacă acest lucru este adevărat, îl vom nota ca . Rețineți că există și alte definiții echivalente ale semidefinitității pozitive, de exemplu, matricele semidefinite pozitive au doar valori proprii nenegative și au o rădăcină pătrată semidefinită pozitivă. $n\ ori n$ $M$ $x^{1},\ldots,x^{n)$ $m_{i,j}=x^{i}\cdot x^{j)$ $i,j$ $M \succeq 0$

Se notează prin spațiul tuturor matricelor simetrice reale. În acest spațiu există un produs interior (unde înseamnă urmă ) ${\mathbb {S}}^{n}$ $n\ ori 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)}$

Putem rescrie problema de programare matematică din secțiunea anterioară în forma echivalentă

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

in conditii

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

unde elementul de matrice este egal cu din secțiunea anterioară și este o matrice care are valoarea din secțiunea anterioară ca element de matrice. $i,j$ $C$ $c_{i,j)$ $A_k$ $n\ ori n$ $i,j$ $a_{i,j,k)$

Rețineți că dacă adăugăm variabile suplimentare mod corespunzător, această sarcină SDP poate fi convertită în

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

in conditii

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

Pentru comoditate, problema SDP poate fi definită într-o formă ușor diferită, dar echivalentă. De exemplu, expresii liniare care utilizează variabile scalare nenegative pot fi adăugate la specificația sarcinii. Sarcina rămâne SDP, deoarece fiecare variabilă poate fi inclusă în matrice ca element diagonal ( pentru unii ). Pentru a vă asigura , puteți adăuga restricții pentru toți . Ca un alt exemplu, rețineți că pentru orice matrice semidefinită pozitivă , există un set de vectori astfel încât elementul matricei să fie egal cu produsul scalar al vectorilor și . Astfel, problemele SDP sunt adesea formulate în termeni de expresii liniare ale produselor scalare ale vectorilor. Având în vedere o soluție la problema SDP în formă standard, vectorii pot fi reconstruiți în timp (de exemplu, folosind o descompunere incompletă a matricei Cholesky X). $X$ $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})$

Teoria dualității

Definiții

Similar cu programarea liniară, dacă problema generală SDP este dată sub formă

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

in conditii

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

(problema directă, sau P-SDP), definim problema duală semidefinită (D-SDP) ca

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

in conditii

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

Unde pentru oricare două matrice și , înseamnă . $P$ $Q$ $P\succeq Q$ $PQ\succeq 0$

Dualitate slabă

Teorema dualității slabe afirmă că SDP-ul primar are o valoare nu mai mică decât valoarea SDP-ului dual. Astfel, orice soluție admisibilă a problemei SDP duale limitează valoarea SDP-ului direct de jos și invers, orice valoare admisibilă a problemei SDP-ului direct limitează valoarea SDP-ului dual de sus. Acest lucru se întâmplă pentru că

\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,

unde ultima inegalitate reflectă faptul că ambele matrice sunt semidefinite pozitive. Valoarea acestei funcții este uneori numită dual gap.

Dualitate puternică

Într-o condiție cunoscută sub numele de condiția Slater , valorile problemelor SDP primale și duale sunt egale. Aceasta se numește dualitate puternică . Spre deosebire de problemele de programare liniară , nu orice problemă SDP are o dualitate strictă. În cazul general, valoarea problemei duale SDP poate fi strict mai mică decât valoarea problemei directe.

(i) Să presupunem că problema directă (P-SDP) este mărginită de jos și strict admisibilă (adică există , astfel încât , ). Apoi există o soluție optimă pentru problema duală (D-SDP) și $X_{0}\in \mathbb {S} ^{n},X_{0}\succ 0$ $\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) Să presupunem că problema duală (D-SDP) este mărginită de sus și strict admisibilă (adică pentru unii ). Atunci există o soluție optimă pentru problema directă (P-SDP) și egalitatea din (i) este valabilă. $\sum _{i=1}^{m}(y_{0})_{i}A_{i}\prec C$ $y_{0}\in \mathbb {R} ^{m)$ $X^{*}$

Exemple

Exemplul 1

Luați în considerare trei variabile aleatoare și . Prin definiție, coeficienții lor de corelație sunt validi dacă și numai dacă $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

Să presupunem că din unele surse (de exemplu, din date empirice sau experimentale) știm că și . Problema determinării celor mai mici și mai mari valori poate fi scrisă astfel: $-0,2\leq \rho _{AB}\leq -0,1$ $0,4\leq \rho _{BC}\leq 0,5$ $\rho _{AC}\$

minimiza/maximiza

x_{13}

in conditii

-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

Aici acceptăm . Problema poate fi formulată ca o problemă SDP. Completam inegalitățile extinzând matricea de variabile și introducând variabile suplimentare , de exemplu ${\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&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&1&0&0\\0&0&0&0&0&0&0&0&0&0&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$

După rezolvarea acestei probleme SDP, obținem valorile minime și maxime ( și respectiv). $\rho _{AC}=x_{13}\$ $-0,978$ $0,872$

Exemplul 2

Luați în considerare problema

minimiza

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

in conditiile

Ax+b\geq 0

unde se presupune că la . $d^{T}x>0$ $Ax+b\geq 0$

Prin introducerea unei variabile suplimentare , rescriem problema sub forma: $t$

minimiza

t

in conditii

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

În această formulare, funcția obiectiv este o funcție liniară a două variabile ( ). $x,t$

Prima constrângere poate fi rescrisă ca

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

unde matricea este o matrice pătrată cu valori pe diagonală egale cu elementele vectorului . ${\textbf {diag}}(Ax+b)$ $A+b$

A doua constrângere poate fi scrisă ca

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

Definim matricea după cum urmează $D$

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

Putem folosi teoria complementului lui Schur pentru a demonstra asta

D\succeq 0

[unu]

Problema de programare semidefinită pentru această problemă va fi de forma

minimiza

t

in conditii

\left[{\begin{array}{ccc}{\textbf {diag}}(Ax+b)&0&0\\0&t&c^{T}x\\0&c^{T}x&d^{T}x\ sfârșit{matrice}}\right]\succeq 0

Exemplul 3 (Algoritmul de aproximare Goemans-Williamson MAX CUT)

Programarea semidefinită este un instrument important pentru crearea algoritmilor de aproximare pentru problemele de maximizare NP-hard. Primul algoritm de aproximare bazat pe SDP a fost propus de Michel Goemans și David Williamson [2] . Ei au studiat problema MAX CUT : Având în vedere un grafic G = ( V , E ), este necesar să se împartă vârfurile lui V în două părți, astfel încât să se maximizeze numărul de muchii care conectează aceste două părți. Problema poate fi gândită ca o problemă de programare pătratică cu numere întregi :

Maximizați sub rezerva oricărei .

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

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

i

Cu excepția cazului în care P = NP , nu putem rezolva această problemă în mod eficient. Cu toate acestea, Goemans și Williamson au subliniat o procedură în trei pași pentru a ataca acest tip de problemă:

Slăbim problema de programare pătratică întregă la problema SDP.
Rezolvăm problema SDP (cu orice eroare arbitrar mică ). $\epsilon$
Rotunjim soluția problemei SDP pentru a obține o soluție aproximativă a problemei inițiale a programării pătratice întregi.

Pentru problema MAX CUT , cea mai naturală relaxare este

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

pentru , unde maximizarea se realizează mai degrabă pe vectori decât pe variabile întregi scalare.

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

\{v_{i}\}

Problema este o problemă SDP deoarece atât funcția obiectiv, cât și constrângerile sunt funcții liniare ale produselor scalare ale vectorilor. Soluția problemei SDP oferă un set de vectori unitari în . Deoarece vectorii nu sunt neapărat coliniari, valoarea problemei relaxate poate fi doar mai mare decât valoarea problemei de programare pătratică cu numere întregi originale. Este necesară o procedură finală de rotunjire pentru a obține împărțirea. Goemans și Williamson aleg un hiperplan aleatoriu (folosind o distribuție uniformă) prin origine și împart vârfurile în funcție de locația lor în raport cu acel plan. Analiza directă arată că această procedură oferă factorul de aproximare așteptat de 0,87856 - ε. (Valoarea așteptată a unei tăieturi este egală cu suma peste toate muchiile probabilităților ca muchia să intre în tăietură, iar această așteptare este proporțională cu unghiul dintre vectorii de la vârfurile de capăt ale muchiei. Dacă comparăm această probabilitate cu , așteptarea raportului va fi întotdeauna de cel puțin 0,87856.) Presupunând ipoteza de corectitudine a jocului unic se poate demonstra că coeficientul de aproximare al acestei aproximări este în principal optim. $\mathbf {R^{n}}$ $\cos ^{-1}\langle v_{i},v_{j}\rangle$ $(1-\langle v_{i},v_{j}\rangle )/{2)$

De la apariția lucrării de către Goemans și Williamson, problemele SDP au fost aplicate la dezvoltarea unui număr mare de algoritmi de aproximare. Recent, Prasad Raghavendra a dezvoltat o schemă generală pentru problemele de satisfacție a constrângerilor bazată pe ipoteza jocului unic [3] .

Algoritmi

Există mai multe tipuri de algoritmi pentru rezolvarea problemelor SDP. Rezultatul acestor algoritmi este valoarea problemei SDP până la , care se obține într-un timp care depinde polinom de mărimea problemei și . $\epsilon$ $\log(1/\epsilon )$

Metode de punct interior

Majoritatea sistemelor de soluții se bazează pe metoda punctului interior (CSDP, SeDuMi, SDPT3, DSDP, SDPA), care este robustă și eficientă pentru probleme generale SDP liniare. Abordarea este limitată în utilizare de faptul că algoritmii sunt metode de ordinul doi și necesită matrici mari (și adesea dense) pentru a fi memorate și descompuse.

Metode de primă ordine

Metodele de ordinul întâi pentru optimizarea conică evită stocarea și descompunerea matricelor mari Hessian și sunt aplicabile la probleme mult mai mari decât metodele punctuale interioare, cu prețul unei pierderi de precizie. Metoda este implementată în sistemul „SCS solver”.

Metoda fasciculului

Problema SDP este formulată ca o problemă de optimizare neuniformă și este rezolvată prin metoda fasciculului spectral. Această abordare este foarte eficientă pentru anumite clase de probleme liniare SDP.

Altele

Algoritmii bazați pe metoda Lagrangiană generalizată (PENSDP) au un comportament similar cu metodele punctului interior și pot fi adaptați pentru unele probleme foarte mari. Alți algoritmi folosesc informații de nivel scăzut și reformulează problema SDP ca o problemă de programare neliniară (SPDLR).

Aplicații

Programarea semidefinită a fost folosită pentru a găsi soluții aproximative la problemele de optimizare combinatorie, cum ar fi rezolvarea problemei de tăiere maximă cu un factor de aproximare de 0,87856. Problemele SDP sunt, de asemenea, folosite în geometrie pentru a defini grafice de tensegritate și apar în teoria controlului ca inegalități matrice liniare .

Literatură

Lieven Vandenberghe, Stephen Boyd. Programare Semidefinită // Revista SIAM 38. - 1996. - Martie. - S. 49-95 .
Monique Laurent, Franz Rendl. Programare semidefinită și programare cu numere întregi/Raport PNA-R0210, CWI, Amsterdam . - 2002. - Aprilie.
E. de Klerk. Aspecte ale programării semidefinite: algoritmi de punct interior și aplicații selectate. - Kluwer Academic Publishers, 2002. - ISBN 1-4020-0547-4 .
P. Raghavendra. Algoritmi optimi și rezultate de inaproximabilitate pentru fiecare CSP? // Proceedings of the 40th Annual ACM Symposium on theory of Computing (Victoria, British Columbia, Canada, 17–20 mai 2008). STOC'08 . - New York, NY: ACM, 2008. - S. 245-254.
Robert M Freund. Introducere în programarea semidefinită (SDP) .
Michel X. Goemans, David P. Williamson. Algoritmi de aproximare îmbunătățiți pentru probleme maxime de tăiere și satisfacție folosind programarea semidefinită // JACM. - 1995. - Noiembrie ( vol. 42 , numărul 6 ). - S. 1115-1145 . doi : 10.1145 / 227683.227684 .

Link -uri

Link-uri către introduceri și evenimente în domeniu
Note de curs de la László Lovász despre programarea semidefinită

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock Metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică