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.
Algoritmi
[modifica | modifica wikitesto]- Metodi del punto interno (o della barriera): CSDP, MOSEK, SeDuMi, SDPT3, DSDP, SDPA
- Metodi del prim'ordine: SCS o ADMM
- Metodo del malloppo
- altri
Voci correlate
[modifica | modifica wikitesto]Collegamenti esterni
[modifica | modifica wikitesto]- (EN) Links to introductions and events in the field
- (EN) Lecture notes from László Lovász Archiviato il 14 marzo 2017 in Internet Archive. on Semidefinite Programming
