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 spettraedro.

La programmazione semidefinita è relativamente un nuovo campo dell'ottimizzazione di cui sta accrescendo l'interesse in quanto molti problemi pratici di ricerca operativa e ottimizzazione combinatorica 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 metodi del punto interno.

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.