Quadratische Programmierung (QP)

Die quadratische Programmierung ist die Problemklasse min (1/2) x^T Q x + c^T x s.t. Ax ≤ b, x ≥ 0 in kanonischer Form, wobei Q ∈ R^(n×n) symmetrisch ist, c ∈ R^n der lineare Anteil und die Restriktionen wie beim LP linear sind. Der Charakter des Problems wird durch das Vorzeichen von Q bestimmt: (1) ist Q positiv semidefinit, ist das QP konvex, die KKT-Bedingungen sind notwendig und hinreichend für Optimalität, und das Problem ist polynomiell durch Innere-Punkte- oder Aktive-Menge-Verfahren lösbar (Kozlov, Tarasov und Khachiyan 1979 zeigten die polynomielle Lösbarkeit konvexer QP); (2) ist Q indefinit, ist das Problem nicht-konvex und im Allgemeinen NP-schwer (Sahni 1974). Die kanonische Formulierung ist Markowitz' (1952) Mittelwert-Varianz-Portfoliomodell: min (1/2) x^T Σ x s.t. μ^T x ≥ R, Σ x_i = 1, x ≥ 0 — Σ Kovarianzmatrix, μ Erwartungsrenditen, R Zielrendite; die Effizienzgrenze wird durch Variation von R abgetastet. Markowitz erhielt dafür 1990 den Nobel-Gedächtnispreis für Wirtschaftswissenschaften. QP liegt zudem dem Training von Support Vector Machines (Cortes und Vapnik 1995), der modellprädiktiven Regelung (MPC), den restringierten kleinsten Quadraten, der Sequential Quadratic Programming (SQP, innerer Iterationskern nichtlinearer Optimierung, Wilson 1963 / Han 1976 / Powell 1978) und der Trajektorienoptimierung zugrunde. Algorithmen: Wolfe (1959) und Beale (1959) entwickelten die Aktive-Menge-Prinzipien; Innere-Punkte-Prädiktor-Korrektor-Verfahren (Mehrotra 1992 auf QP übertragen) und Aktive-Menge-Verfahren (eng verwandt mit dem LP-Simplex) dominieren praktische Löser.