Programació Semidefinida
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
a on el , i els són número real i és el producte punt de i .
Formulació equivalents
Diem que una matriu de és positiu semidefinida si és la matriu de Gram d'alguns vectores (i.i. si existixen vectores tal que para tot ). Si açò és el cas , ho denotem en . 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 a l'espai de totes les matrius reals simètriques de . L'espai està equipat en el producte intern (on denota la traça)
Podem reescriure el programa matemàtic dau en la secció anterior equivalentemente de la següent manera
On l'entrada en està donada per de la secció anterior, i és una matriu simètrica de l'entrada de la qual és igual a de la secció anterior. Aixina, les matrius i 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
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 com a entrada diagonal ( per a alguns ). Per a assegurar que , les restriccions poden ser afegides per a tot . Per un atre eixemple, nota que per a qualsevol matriu positiu semidefinida , existix un conjunt de vectors tal que l'entrada , de és , el producte escalar de i . 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 poden ser recuperats en temps (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
(el problema primal o P-PSD), definim el programa semidefinido (D-PSD) dual com
a on para qualssevol dos matrius i , significa que .
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
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 tal que , ). Llavors hi ha un solució òptima para (D-SDP) i
(ii) Supongam que el problema dual (D-SDP) està acotat per dalt i és estrictament factible (i.i., per a alguns ). Llavors hi ha una solució òptima a (P-SDP) i la forma d'igualtat de (i) es complix.
Referències
- Este artícul conté una traducció derivada de «Programación Semidefinida» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.