Quadratic Programming (QP)

Quadratic programming is the problem class min (1/2) x^T Q x + c^T x s.t. Ax ≤ b, x ≥ 0 in canonical form, where Q ∈ R^(n×n) is symmetric, c ∈ R^n is the linear cost term, and the constraints are linear as in LP. Problem character is dictated by the sign of Q: (1) if Q is positive semidefinite the QP is convex, the KKT conditions are necessary and sufficient for optimality, and the problem is solvable in polynomial time by interior-point or active-set methods (Kozlov, Tarasov, and Khachiyan 1979 proved polynomial solvability of convex QP); (2) if Q is indefinite the problem is non-convex and NP-hard in general (Sahni 1974). The canonical formulation is Markowitz's (1952) mean-variance portfolio selection model: min (1/2) x^T Σ x s.t. μ^T x ≥ R, Σ x_i = 1, x ≥ 0 — Σ the covariance matrix, μ the expected-return vector, R the target return; the efficient frontier is traced by solving the QP across R values. Markowitz received the 1990 Nobel Memorial Prize in Economics for this work. QP also underlies support vector machine training (Cortes and Vapnik 1995), model predictive control (MPC), constrained least squares, sequential quadratic programming (SQP, the inner loop of nonlinear optimization, Wilson 1963 / Han 1976 / Powell 1978), and trajectory optimization. Algorithms: Wolfe (1959) and Beale (1959) developed the active-set principles; interior-point predictor-corrector (Mehrotra 1992 logic extended to QP) and active-set methods (cousins of the LP simplex) dominate practical solvers.