Programmazione Quadratica (QP)

La programmazione quadratica è la classe di problemi min (1/2) x^T Q x + c^T x s.t. Ax ≤ b, x ≥ 0 in forma canonica, dove Q ∈ R^(n×n) è simmetrica, c ∈ R^n è il termine lineare e i vincoli sono lineari come in LP. La natura del problema è determinata dal segno di Q: (1) se Q è semidefinita positiva il QP è convesso, le condizioni KKT sono necessarie e sufficienti per l'ottimalità, e il problema è risolvibile in tempo polinomiale tramite metodi dei punti interni o di insieme attivo (Kozlov, Tarasov e Khachiyan 1979 dimostrarono la risolvibilità polinomiale del QP convesso); (2) se Q è indefinita il problema è non convesso e in generale NP-difficile (Sahni 1974). La formulazione canonica è il modello media-varianza di Markowitz (1952): min (1/2) x^T Σ x s.t. μ^T x ≥ R, Σ x_i = 1, x ≥ 0 — Σ matrice di covarianza, μ vettore dei rendimenti attesi, R rendimento obiettivo; la frontiera efficiente è tracciata variando R. Markowitz ricevette il Premio Nobel per l'Economia nel 1990 per questo lavoro. Il QP è anche alla base dell'addestramento delle macchine a vettori di supporto (Cortes e Vapnik 1995), del controllo predittivo basato sul modello (MPC), dei minimi quadrati vincolati, della programmazione quadratica sequenziale (SQP, ciclo interno dell'ottimizzazione non lineare, Wilson 1963 / Han 1976 / Powell 1978) e dell'ottimizzazione di traiettorie. Algoritmi: Wolfe (1959) e Beale (1959) svilupparono i principi dell'insieme attivo; i metodi dei punti interni predittore-correttore (logica di Mehrotra 1992 estesa al QP) e quelli di insieme attivo (cugini del simplesso LP) dominano i solver pratici.