Programare semidefinită - Semidefinite programming

Programarea Semidefinite ( PDS ) este un subdomeniu de optimizare convexă în cauză cu optimizarea liniară funcție obiectiv (o funcție specificată de utilizator pe care utilizatorul dorește să minimizeze sau să maximizeze) peste intersecția conului de semidefinite pozitive matrici cu un spațiu afin , adică un spectraedru .

Programarea semidefinită este un domeniu de optimizare relativ nou, care prezintă un interes crescând din mai multe motive. Multe probleme practice în cercetarea operațională și optimizarea combinatorie pot fi modelate sau aproximate ca probleme de programare semidefinite. În teoria controlului automat, SDP-urile sunt folosite în contextul inegalităților matricei liniare . SDP-urile sunt de fapt un caz special de programare a conului și pot fi rezolvate eficient prin metode de punct interior . Toate programele liniare și programele pătratice (convexe) pot fi exprimate ca SDP-uri, iar prin ierarhiile SDP-urilor soluțiile problemelor de optimizare polinomială pot fi aproximate. Programarea semidefinită a fost utilizată în optimizarea sistemelor complexe. În ultimii ani, au fost formulate unele probleme cuantice de complexitate a interogărilor în termeni de programe semidefinite.

Motivație și definiție

Motivația inițială

O problemă de programare liniară este una în care dorim să maximizăm sau să minimalizăm o funcție obiectivă liniară a variabilelor reale pe un politop . În programarea semidefinită, folosim în schimb vectori cu valori reale și ni se permite să luăm produsul punct al vectorilor; constrângerile de non-negativitate asupra variabilelor reale în LP ( programare liniară ) sunt înlocuite de constrângeri de semidefinitate asupra variabilelor matricei în SDP ( programare semidefinită ). În mod specific, o problemă generală de programare semidefinită poate fi definită ca orice problemă de programare matematică a formei

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

unde , și sunt numere reale și este produsul punct al și . ${\ displaystyle c_ {i, j}, a_ {i, j, k}}$${\ displaystyle b_ {k}}$${\ displaystyle x ^ {i} \ cdot x ^ {j}}$${\ displaystyle x ^ {i}}$${\ displaystyle x ^ {j}}$

Formulări echivalente

Se spune că o matrice este semidefinită pozitivă dacă este matricea Gramiană a unor vectori (adică dacă există vectori astfel încât pentru toți ). Dacă acesta este cazul, vom nota acest lucru ca . Rețineți că există o serie de alte definiții echivalente de a fi semidefinite pozitive, de exemplu, matrici semidefinite pozitive sunt auto-adjuncte matrici care au doar nonnegative valori proprii . ${\ 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}$

Notăm prin spațiul tuturor matricilor simetrice reale. Spațiul este echipat cu produsul interior (unde indică urmele ) ${\ 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}.}$

Putem rescrie programul matematic dat în secțiunea anterioară echivalent ca

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

unde intrarea în este dată de la secțiunea anterioară și este simetrică cu matrice având th intrare din secțiunea anterioară. Astfel, matricile și sunt simetrice, iar produsele interioare de mai sus sunt bine definite. ${\ 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}}$

Rețineți că, dacă adăugăm variabile slack în mod corespunzător, acest SDP poate fi convertit într-unul din formular

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

Pentru comoditate, un SDP poate fi specificat într-o formă ușor diferită, dar echivalentă. De exemplu, expresiile liniare care implică variabile scalare nenegative pot fi adăugate la specificația programului. Acesta rămâne un SDP deoarece fiecare variabilă poate fi încorporată în matrice ca intrare diagonală ( pentru unii ). Pentru a vă asigura că , pot fi adăugate constrângeri pentru toți . Ca un alt exemplu, nota că pentru orice matrice semidefinite pozitivă , există un set de vectori astfel încât , intrarea este produsul scalar al și . Prin urmare, SDP-urile sunt adesea formulate în termeni de expresii liniare pe produse scalare de vectori. Având în vedere soluția SDP în forma standard, vectorii pot fi recuperați în timp (de exemplu, utilizând o descompunere incompletă Cholesky a lui 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})}$

Teoria dualității

Definiții

În mod analog programării liniare, având în vedere un SDP general al formei

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

(problema primară sau P-SDP), definim programul semidefinit dual (D-SDP) ca fiind

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

unde pentru orice două matrice și , înseamnă . ${\ displaystyle P}$${\ displaystyle Q}$${\ displaystyle P \ succeq Q}$${\ displaystyle PQ \ succeq 0}$

Dualitate slabă

Slabă dualitate Teorema afirmă că valoarea PDS primordial este de cel puțin valoarea dublă SDP. Prin urmare, orice soluție fezabilă la SDP dual limitează valoarea SDP primară și, invers, orice soluție fezabilă la SDP primară limitează valoarea SDP duală. Asta pentru ca

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

unde ultima inegalitate se datorează faptului că ambele matrice sunt semidefinite pozitive, iar rezultatul acestei funcții este uneori denumit decalaj de dualitate.

Dualitate puternică

Într-o condiție cunoscută sub numele de condiția lui Slater , valoarea SDP primar și dual este egală. Aceasta este cunoscută sub numele de dualitate puternică . Spre deosebire de programele liniare , totuși, nu fiecare SDP îndeplinește o dualitate puternică; în general, valoarea SDP dual poate fi strict sub valoarea primului.

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

Exemple

Exemplul 1

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

caz în care această matrice se numește matrice de corelație . Să presupunem că știm din anumite cunoștințe anterioare (de exemplu, rezultatele empirice ale unui experiment) că și . Problema determinării celor mai mici și mai mari valori pe care le poate lua este dată de: ${\ displaystyle -0.2 \ leq \ rho _ {AB} \ leq -0.1}$${\ displaystyle 0.4 \ leq \ rho _ {BC} \ leq 0.5}$${\ displaystyle \ rho _ {AC} \}$

minimiza / maximiza ${\ displaystyle x_ {13}}$

supus

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

Ne-am propus să obținem răspunsul. Acest lucru poate fi formulat de un SDP. Ne ocupăm de constrângerile de inegalitate mărind matricea variabilă și introducând variabile slack , de exemplu ${\ displaystyle \ rho _ {AB} = x_ {12}, \ \ rho _ {AC} = x_ {13}, \ \ rho _ {BC} = x_ {23}}$

${\ Displaystyle \ mathrm {tr} \ stânga (\ stânga ({\ 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 \ end {array}} \ dreapta) \ cdot \ 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 & 0 & 0 & s_ {2} & 0 \\ 0 & 0 & 0 & 0 & 0 & s_ {3} \ end {array}} \ right) \ right) = x_ {12} + s_ {1} = - 0.1}$

Rezolvarea acestei PDS prezintă valorile minime și maxime ale ca și respectiv. ${\ displaystyle \ rho _ {AC} = x_ {13} \}$${\ displaystyle -0.978}$${\ displaystyle 0.872}$

Exemplul 2

Luați în considerare problema

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

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

unde presupunem că ori de câte ori . ${\ displaystyle d ^ {T} x> 0}$${\ displaystyle Ax + b \ geq 0}$

Introducând o variabilă auxiliară , problema poate fi reformulată: ${\ displaystyle t}$

minimiza ${\ displaystyle t}$

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

În această formulare, obiectivul este o funcție liniară a variabilelor . ${\ displaystyle x, t}$

Prima restricție poate fi scrisă ca

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

unde matricea este matricea pătrată cu valori în diagonală egale cu elementele vectorului . ${\ displaystyle {\ textbf {diag}} (Ax + b)}$${\ displaystyle Ax + b}$

A doua restricție poate fi scrisă ca

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

Definind după cum urmează ${\ displaystyle D}$

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

Putem folosi teoria complementelor Schur pentru a vedea asta

${\ displaystyle D \ succeq 0}$

(Boyd și Vandenberghe, 1996)

Programul semidefinit asociat cu această problemă este

minimiza ${\ displaystyle t}$

supus ${\ displaystyle \ 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}$

Exemplul 3 (algoritm de aproximare a tăieturii maxime Goemans – Williamson)

Programele semidefinite sunt instrumente importante pentru dezvoltarea algoritmilor de aproximare pentru problemele de maximizare NP-hard. Primul algoritm de aproximare bazat pe un SDP se datorează lui Michel Goemans și David P. Williamson (JACM, 1995). Au studiat problema de tăiere maximă : având în vedere un grafic G = ( V , E ), se realizează o partiție a vârfurilor V astfel încât să maximizeze numărul de muchii care se încrucișează de la o parte la alta. Această problemă poate fi exprimată ca un program pătratic întreg :

Maximizați astfel încât fiecare .${\ displaystyle \ sum _ {(i, j) \ în E} {\ frac {1-v_ {i} v_ {j}} {2}},}$${\ displaystyle v_ {i} \ in \ {1, -1 \}}$

Dacă P = NP , nu putem rezolva această problemă de maximizare în mod eficient. Cu toate acestea, Goemans și Williamson au observat o procedură generală în trei pași pentru a ataca acest tip de problemă:

1. Relaxați programul pătratic întreg într-un SDP.
2. Rezolvați SDP (într-o eroare de aditiv arbitrar mică ).${\ displaystyle \ epsilon}$
3. Runda soluția SDP pentru a obține o soluție aproximativă pentru programul pătratic întreg original.

Pentru tăierea maximă, cea mai naturală relaxare este

${\ displaystyle \ max \ sum _ {(i, j) \ în E} {\ frac {1- \ langle v_ {i}, v_ {j} \ rangle} {2}},}$astfel încât , în cazul în care maximizarea este peste vectori în loc de scalari întregi.${\ displaystyle \ lVert v_ {i} \ rVert ^ {2} = 1}$${\ displaystyle \ {v_ {i} \}}$

Acesta este un SDP deoarece funcția obiectivă și constrângerile sunt toate funcții liniare ale produselor interioare vectoriale. Rezolvarea SDP oferă un set de vectori unitari în ; deoarece vectorii nu trebuie să fie coliniari, valoarea acestui program relaxat poate fi mai mare decât valoarea programului întreg pătratic original. În cele din urmă, este necesară o procedură de rotunjire pentru a obține o partiție. Goemans și Williamson aleg pur și simplu un hiperplan uniform aleatoriu prin origine și împart vârfurile în funcție de ce parte a hiperplanului se află vectorii corespunzători. Analiza simplă arată că această procedură atinge un raport de aproximare așteptat (garanție de performanță) de 0,85856 - ε. (Valoarea așteptată a tăieturii este suma peste margini a probabilității ca muchia să fie tăiată, care este proporțională cu unghiul dintre vectori la punctele finale ale marginii peste . Comparând această probabilitate cu , în așteptare, raportul este întotdeauna la Presupunând conjectura unică a jocurilor , se poate demonstra că acest raport de aproximare este în esență optim. ${\ displaystyle \ mathbf {R ^ {n}}}$${\ displaystyle \ cos ^ {- 1} \ langle v_ {i}, v_ {j} \ rangle}$${\ displaystyle \ pi}$${\ displaystyle (1- \ langle v_ {i}, v_ {j} \ rangle) / {2}}$

De la lucrarea originală a lui Goemans și Williamson, SDP-urile au fost aplicate pentru a dezvolta numeroși algoritmi de aproximare. Recent, Prasad Raghavendra a dezvoltat un cadru general pentru problemele de satisfacție a constrângerilor bazate pe conjectura unică a jocurilor .

Algoritmi

Există mai multe tipuri de algoritmi pentru rezolvarea SDP-urilor. Acești algoritmi generează valoarea SDP până la o eroare aditivă în timp care este polinomială în dimensiunea descrierii programului și . ${\ displaystyle \ epsilon}$${\ displaystyle \ log (1 / \ epsilon)}$

Există, de asemenea, algoritmi de reducere a feței care pot fi utilizați pentru preprocesarea problemelor SDP prin inspectarea constrângerilor problemei. Acestea pot fi utilizate pentru a detecta lipsa de fezabilitate strictă, pentru a șterge rândurile și coloanele redundante și, de asemenea, pentru a reduce dimensiunea matricei variabile.

Metode de punct interior

Majoritatea codurilor se bazează pe metode de punct interior (CSDP, MOSEK , SeDuMi, SDPT3 , DSDP, SDPA). Robust și eficient pentru problemele generale SDP liniare. Restricționat de faptul că algoritmii sunt metode de ordinul doi și trebuie să stocheze și să factorizeze o matrice mare (și adesea densă).

Metode de prim ordin

Metodele de prim ordin pentru optimizarea conică evită calculul, stocarea și descompunerea unei matrici hessiene mari și a scalării la probleme mult mai mari decât metodele punctelor interioare, la un anumit cost de precizie. O metodă de prim ordin este implementată în Splitter Cone Solver (SCS). O altă metodă de prim ordin este metoda direcției alternative a multiplicatorilor (ADMM). Această metodă necesită în fiecare etapă proiecția pe conul matricilor semidefinite.

Metoda pachetului

Codul ConicBundle formulează problema SDP ca o problemă de optimizare fără rezistență și o rezolvă prin metoda Spectral Bundle de optimizare fără rezistență. Această abordare este foarte eficientă pentru o clasă specială de probleme SDP liniare.

Alte metode de rezolvare

Algoritmii bazați pe metoda Lagrangiană augmentată (PENSDP) sunt similare în comportament cu metodele punctelor interioare și pot fi specializate unor probleme la scară foarte mare. Alți algoritmi utilizează informații de rang scăzut și reformularea SDP ca o problemă de programare neliniară (SDPLR).

Metode aproximative

Au fost propuse și algoritmi care rezolvă aproximativ SDP-urile. Scopul principal al acestor metode este de a atinge o complexitate mai mică în aplicații în care soluțiile aproximative sunt suficiente și complexitatea trebuie să fie minimă. O metodă proeminentă care a fost utilizată pentru detectarea datelor în sistemele fără fir cu intrări multiple cu ieșiri multiple (MIMO) este Relaxarea triangulară aproximativă SEmidefinită (TASER), care operează pe factorii de descompunere Cholesky ai matricei semidefinite în loc de matricea semidefinită. Această metodă calculează soluțiile aproximative pentru o problemă de tip max-cut, care sunt adesea comparabile cu soluțiile de la rezolvatorii exacți, dar în doar 10-20 iterații algoritmice.

Aplicații

Programarea semidefinită a fost aplicată pentru a găsi soluții aproximative la problemele de optimizare combinatorie, cum ar fi soluția problemei de tăiere maximă cu un raport de aproximare de 0.87856. SDP-urile sunt, de asemenea, utilizate în geometrie pentru a determina graficele tensegrity și apar în teoria controlului ca LMI .

Referințe

• Lieven Vandenberghe, Stephen Boyd, „Semidefinite Programming”, SIAM Review 38, martie 1996, pp. 49–95. pdf
• Monique Laurent, Franz Rendl, „Semidefinite Programming and Integer Programming”, Raport PNA-R0210, CWI, Amsterdam, aprilie 2002. optimization-online
• E. de Klerk, "Aspecte ale programării semidefinite: algoritmi de punct interior și aplicații selectate", Kluwer Academic Publishers, martie 2002, ISBN  1-4020-0547-4 .
• Robert M. Freund, „Introducere în programarea semidefinită (SDP), SDP-Introducere

linkuri externe

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