Programació Semidefinida (SDP) és una subrama de l'optimisació convexa l'interés principal de la qual yacer en l'optimisació d'una funció objectiva llineal (una funció especificada per l'usuari, que dit usuari busca minimisar o maximizar) sobre l'intersecció del con de matrius positiu semidefinidas en un espai afí, i.i., un espectrahedro.

La programació semidefinida és una branca relativament nova d'optimisació que està rebent creixent atenció per vàries raons. Molts problemes pràctics en investigació d'operacions i optimisació combinatòria poden ser modelats o aproximats per programes semidefinidos. En teoria de control automàtic, els PSDs són utilisats en el context de desigualtats matriciales llineals. Els PSDs són de fet un cas especial de programació cònica i poden ser resolts eficientemente per métodos de punt interior. Tots els programes llineals i els programes quadràtics (convexos) poden ser expressats com PSDs, i via jerarquia de PSDs, les solucions de problemes d'optimisació polinomial poden ser aproximades. La programació semidefinida ha segut utilisada en l'optimisació de sistemes complexos. En anys recents, alguns problemes de complexitat de consulta quàntics han segut formulats en térmens de programes semidefinidos.

Motivació i definició

Motivació inicial

Un problema de programació llineal és un en el qual desigem maximizar o minimisar una funció objectiva llineal en variables reals sobre un polítop. En canvi, en programació semidefinida utilisem vectores en entrades reals i podem prendre el producte punt de vectors; les restriccions de no-negatividad en variables reals en LP (programació llineal) són reemplaçades per restriccions de semidefinició en les variables matriciales en PSD (programació semidefinida). Específicament, un problema semidefinido general pot ser definit com qualsevol problema de programació matemàtica de la següent forma

minx1,…,xn∈ℝn∑i,j∈[n]ci,j(xi⋅xj)sujeto a∑i,j∈[n]ai,j,k(xi⋅xj)≤bk para toda k

a on el ci,j,ai,j,k, i els bk són número real i xi⋅xj és el producte punt de xi i xj.

Formulació equivalents

Diem que una matriu M de n×n és positiu semidefinida si és la matriu de Gram d'alguns vectores (i.i. si existixen vectores x1,…,xn tal que mi,j=xi⋅xj para tot i,j). Si açò és el cas , ho denotem en M⪰0. Notem que hi ha moltes atres definicions equivalents de per a que una matriu siga positiu semidefinida; per eixemple, matrius positiu semidefinidas són matrius auto-adjuntes que tenen únicament eigenvalores no negatius.

Denotem per 𝕊n a l'espai de totes les matrius reals simètriques de n×n. L'espai està equipat en el producte intern (on tr denota la traça)⟨A,B⟩𝕊n=tr(ATB)=∑i=1,j=1nAijBij.

Podem reescriure el programa matemàtic dau en la secció anterior equivalentemente de la següent manera

minX∈𝕊n⟨C,X⟩𝕊nsujeto a⟨Ak,X⟩𝕊n≤bk,k=1,…,mX⪰0.

On l'entrada i,j en C està donada per ci,j+cj,i2 de la secció anterior, i Ak és una matriu simètrica de n×n l'entrada de la qual i,j és igual a ai,j,k+aj,i,k2 de la secció anterior. Aixina, les matrius C i Ak són simètriques, i els productes interiors de dalt estan ben definits.

Notem que si afegim variables de chala apropiadament, este PSD pot ser convertit a un de la forma

minX∈𝕊n⟨C,X⟩𝕊nsujeto a⟨Ak,X⟩𝕊n=bk,k=1,…,mX⪰0.


Per conveniència, un PSD pot ser especificat llaugerament diferent, pero forma equivalent. Per eixemple, les expressions llineals que tenen variables escalars no negatives poden ser afegides a l'especificació del programa. Açò seguix sent un PSD perque cada variable pot ser incorporada a la matriu X com a entrada diagonal (Xii per a alguns i). Per a assegurar que Xii≥0, les restriccions Xij=0 poden ser afegides per a tot j≠i. Per un atre eixemple, nota que per a qualsevol matriu positiu semidefinida X, existix un conjunt de vectors {vi} tal que l'entrada i, j de X és Xij=(vi,vj), el producte escalar de vi i vj. Per lo tant, els PSDs a sovint són formulats en térmens d'expressions llineals en productes escalares de vectors. Donada la solució al PSD en forma estàndar, els vectors {vi} poden ser recuperats en temps O(n3) (p. eix., per utilisant una factorisació de Cholesky incompleta de X).

Teoria de dualitat

Definicions

Análogamente a programació llineal, donat un PSD general de la forma

minX∈𝕊n⟨C,X⟩𝕊nsujeto a⟨Ai,X⟩𝕊n=bi,i=1,…,mX⪰0

(el problema primal o P-PSD), definim el programa semidefinido (D-PSD) dual com

maxy∈ℝm⟨b,y⟩ℝmsujeto a∑i=1myiAi⪯C

maxy∈ℝm⟨b,y⟩ℝmsujeto a∑i=1myi,Ai⪯C

a on para qualssevol dos matrius P i Q, P⪰Q significa que P−Q⪰0.

Dualitat dèbil

El teorema de la dualitat dèbil declara que el valor de el PSD primal és a lo manco el valor de el PSD dual. Per tant, qualsevol solució factible al PSD dual és una quota inferior per al valor primal de el PSD, i conversament, qualsevol solució factible al PSD primal és una quota superior per al valor de el PSD dual. Açò és perque

⟨C,X⟩−⟨b,y⟩=⟨C,X⟩−∑i=1myibi=⟨C,X⟩−∑i=1myi⟨Ai,X⟩=⟨C−∑i=1myiAi,X⟩≥0,

a on l'última desigualtat és perque abdós matrius són positives semidefinidas, i el resultat d'esta funció és a voltes referit com a brecha de dualitat.

Dualitat forta

Baix una condició coneguda com la condició de Slater, el valor de el PSD primal i dual és igual. açò se li crida dualitat forta. Diferent que per a programes llineals, no obstant, no qualsevol PSD satisfà dualitat forta; en general, el valor de el PSD dual pot ser estrictament menor al valor del programa primal.

(i) Supongam que el problema primal (P-SDP) està acotat avall i és estrictament viable (i.i., existix X0∈𝕊n,X0≻0 tal que ⟨Ai,X0⟩𝕊n=bi, i=1,…,m). Llavors hi ha un solució òptima y* para (D-SDP) i

⟨C,X*⟩𝕊n=⟨b,y*⟩ℝm.

(ii) Supongam que el problema dual (D-SDP) està acotat per dalt i és estrictament factible (i.i., ∑i=1m(y0)iAi≺C per a alguns y0∈ℝm). Llavors hi ha una solució òptima X* a (P-SDP) i la forma d'igualtat de (i) es complix.

Referències