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 câmp relativ nou de optimizare care prezintă un interes din ce în ce mai mare din mai multe motive. Multe probleme practice în cercetarea operațională și optimizarea combinatorială pot fi modelate sau aproximate ca probleme de programare semidefinite. În teoria controlului automat, SDP-urile sunt utilizate în contextul inegalităților matricei liniare . SDP-urile sunt de fapt un caz special de programare a conurilor și pot fi rezolvate eficient prin metode de punct interior . Toate programele liniare pot fi exprimate sub formă de SDP, iar prin ierarhiile SDP-urile, soluțiile problemelor de optimizare polinomială pot fi aproximate. Programarea semidefinită a fost utilizată în optimizarea sistemelor complexe. În ultimii ani, unele probleme de complexitate a interogărilor cuantice au fost formulate în termeni de programe semidefinite.

Motivație și definiție

Motivația inițială

O problemă de programare liniară este cea în care dorim să maximizăm sau să minimalizăm o funcție obiectivă liniară a variabilelor reale pe un polipop . În programarea semidefinită, folosim în schimb vectori cu valoare reală și avem voie să ia produsul punct al vectorilor; constrângerile nonnegativității asupra variabilelor reale din LP ( programare liniară ) sunt înlocuite de constrângerile de semidefinitate asupra variabilelor matrice din SDP ( programare semidefinită ). Mai exact, 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}}} & {\ displaystyle \ sum _ {i, j \ in [n]} c_ {i, j} (x ^ {i} \ cdot x ^ {j})} \\ {\ text {supus}} & {\ displaystyle \ sum _ {i, j \ in [n]} a_ {i, j, k} (x ^ {i} \ cdot x ^ {j}) \ leq b_ {k}} {\ text {pentru toate}} 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, denotăm acest lucru ca fiind . Rețineți că există mai multe alte definiții echivalente ale semidefinitului pozitiv, de exemplu, matricile semidefinite pozitive sunt matrici auto-adiacente care au doar valori proprii non-negative. ${\ 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}$

Notează prin spațiul tuturor matricilor simetrice reale. Spatiul este echipat cu produsul interior (unde denota 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) = \ suma _ {i = 1, j = 1 } ^ {n} A_ {ij} B_ {ij}.}$

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

${\ displaystyle {\ begin {array} {rl} {\ displaystyle \ min _ {X \ in \ mathbb {S} ^ {n}}} & \ langle C, X \ rangle _ {\ mathbb {S} ^ { n}} \\ {\ text {supus}} & \ 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 slabe în mod corespunzător, acest SDP poate fi convertit într-una din forme

${\ displaystyle {\ begin {array} {rl} {\ displaystyle \ min _ {X \ in \ mathbb {S} ^ {n}}} & \ langle C, X \ rangle _ {\ mathbb {S} ^ { n}} \\ {\ text {supus}} & \ 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 negative pot fi adăugate la specificația programului. Acesta rămâne un SDP, deoarece fiecare variabilă poate fi încorporată în matrice ca o intrare în diagonală ( pentru unii ). Pentru a vă asigura că , toate restricțiile pot fi adăugate 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 sunt deseori formulate în termeni de expresii liniare pe produsele scalare ale vectorilor. Având în vedere soluția SDP în forma standard, vectorii pot fi recuperați la timp (de exemplu, utilizând o descompunere incompletă Cholesky a 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

Analog la programarea liniară, dat un SDP general al formularului

${\ displaystyle {\ begin {array} {rl} {\ displaystyle \ min _ {X \ in \ mathbb {S} ^ {n}}} & \ langle C, X \ rangle _ {\ mathbb {S} ^ { n}} \\ {\ text {supus}} & \ 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 dual semidefinit (D-SDP) ca fiind

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

unde pentru orice două matrici ș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ă pentru valoarea SDP dublă limitează valoarea SDP primară și, invers, orice soluție posibilă 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 numit decalaj dual.

Dualitate puternică

În condițiile cunoscute sub denumirea de starea Slater , valoarea SDP-urilor primare și duble este egală. Aceasta este cunoscută sub numele de dualitate puternică . Spre deosebire de programele liniare , însă, nu fiecare SDP satisface o dualitate puternică; în general, valoarea SDP dual poate fi strict sub valoarea primară.

(i) Să presupunem că problema primordială (P-SDP) , este delimitată de mai jos și strict fezabilă ( de exemplu, 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 delimitată mai sus și strict fezabilă (adică pentru unii ). Apoi, există o soluție optimă pentru (P-SDP) și egalitatea de la (i) reține. ${\ 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 este numită matrice de corelație . Să presupunem că știm din anumite cunoștințe anterioare (rezultatele empirice ale unui experiment, de exemplu) că și . Problema determinării celor mai mici și mai mari valori care pot fi luate este dată de: ${\ displaystyle -0.2 \ leq \ rho _ {AB} \ leq -0.1}$${\ displaystyle 0.4 \ leq \ rho _ {BC} \ leq 0.5}$${\ displaystyle \ rho _ {AC} \}$

minimizarea / Maximizați ${\ 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. Aceasta poate fi formulată de un SDP. Ne ocupăm de constrângerile de inegalitate prin mărirea matricei variabile și prin introducerea variabilelor slabe , de exemplu ${\ displaystyle \ rho _ {AB} = x_ {12}, \ \ rho _ {AC} = x_ {13}, \ \ rho _ {BC} = x_ {23}}$

${\ displaystyle \ 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 \ stânga ({\ 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}} \ dreapta) \ dreapta) = X_ {12} + s_ {1} = - 0,1}$

Rezolvarea acestui SDP oferă valorile minime și maxime de la , respectiv și . ${\ displaystyle \ rho _ {AC} = x_ {13} \}$${\ displaystyle -0.978}$${\ displaystyle 0.872}$

Exemplul 2

Luați în considerare problema

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

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

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

Introducerea unei variabile auxiliare problema poate fi reformulată: ${\ displaystyle t}$

minimaliza ${\ 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ă egală 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}$

Definirea 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

minimaliza ${\ 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 (algoritmul de aproximare Goemans-Williamson MAX CUT)

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

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

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

1. Relaxați programul quadratic integral într-un SDP.
2. Rezolvați SDP (într-o eroare aditivă mică în mod arbitrar ).${\ displaystyle \ epsilon}$
3. Rotunjiți soluția SDP pentru a obține o soluție aproximativă la programul curatic integral inițial.

Pentru MAX CUT, cea mai naturală relaxare este

${\ displaystyle \ max \ sum _ {(i, j) \ in E} {\ frac {1- \ langle v_ {i}, v_ {j} \ rangle} {2}},}$astfel încât , unde 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 și constrângerile obiective sunt toate funcții liniare ale produselor interioare vectoriale. Rezolvarea SDP oferă un set de vectori de unitate în ; întrucât vectorii nu sunt obligați să fie coliniari, valoarea acestui program relaxat poate fi mai mare decât valoarea programului integrat original cuadratic. În final, 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 vertexurile în funcție de ce parte a hiperplanului se află vectorii corespunzători. Analiza simplă arată că această procedură atinge un raport de aproximare preconizat (garanție de performanță) de 0,87856 - ε. (Valoarea așteptată a tăierii este suma peste margini a probabilității ca marginea să fie tăiată, care este proporțională cu unghiul dintre vectori la punctele finale ale muchiei deasupra . Compararea acestei probabilități cu , în așteptare, raportul este întotdeauna la cel puțin 0,87856.) Presupunând conjectura jocurilor unice , se poate demonstra că acest raport de aproximare este esențial 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 de constrângere bazate pe Conjectura Jocurilor Unice .

algoritmi

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

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. Limitat 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ă ordine pentru optimizarea conică evită calcularea, stocarea și factorizarea unei matrice și o scară mare din Hessian la probleme mult mai mari decât metodele punctelor interioare, cu un anumit cost cu precizie. O metodă de primă comandă este pusă în aplicare în Split Cone Solver (SCS). O altă metodă de prim ordin este metoda de direcție alternativă 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 nesmooth și o rezolvă prin metoda Spectral Bundle de optimizare nonsmooth. Această abordare este foarte eficientă pentru o clasă specială de probleme lineare SDP.

Alte

Algoritmii pe baza metodei Lagrangianului augmentat (PENSDP) sunt similare în comportament cu metodele punctului interior și pot fi specializate în unele 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).

Aplicații

Programarea semidefinită a fost aplicată pentru a găsi soluții aproximative la probleme 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 de tensegritate și apar în teoria controlului ca LMI-uri .

Referințe

• Lieven Vandenberghe, Stephen Boyd, „Programare semidefinită”, SIAM Review 38, martie 1996, p. 49–95. pdf
• Monique Laurent, Franz Rendl, „Programare semidefinită și programare integrală”, Raport PNA-R0210, CWI, Amsterdam, aprilie 2002. optimizare-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), Introducere SDP

linkuri externe

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