Programmazione semidefinita

La Programmazione semidefinita (O SDP) è un sottocampo dell'ottimizzazione convessa che si occupa dell'ottimizzazione di una funzione obiettivo lineare (una funzione specificata dall'utente che l'utente vuole minimizzare o massimizzare) su una intersezione di un cono di matrici positive semidefinite con uno spazio affine, come uno . La programmazione semidefinita è relativamente un nuovo campo dell'ottimizzazione di cui sta accrescendo l'interesse in quanto molti problemi pratici di ricerca operativa e possono essere modellati o approssimati come problemi di programmazione semidefinita.Nella teoria del controllo automatico, la SDP è usata nel contesto di ineguaglianze delle matrici lineari poiché sono un caso speciale della programmazione conica e possono essere risolte efficientemente dai . Tutti i programmi lineari possono essere espressi come SDP, e attraverso gerarchie di SDP si possono approssimare le soluzioni ai problemi di ottimizzazione polinomiale.Negli ultimi anni alcuni problema di complessità quantistica sono stati formulati in termini di programmi semidefiniti.