What Is Quadratic Programming?

Quadratic programming (QP) is a class of mathematical optimization in which the objective function is quadratic and the constraints are linear. The goal is to find a vector of decision variables that minimizes or maximizes an expression of the form (1/2)x^T Q x + c^T x subject to constraints Ax = b and Gx ≤ h, where Q is a symmetric matrix encoding pairwise variable interactions. When Q is positive semidefinite, the problem is convex and has a unique global minimum; when Q is indefinite, the problem may have multiple local minima and is generally NP-hard. Quadratic programming sits between linear programming, which handles only linear objectives, and general nonlinear programming, and its special structure admits efficient specialized solvers that outperform general-purpose nonlinear methods.

The discipline draws on linear algebra, convex analysis, and computational optimization. It emerged as a practical tool in the 1950s alongside the development of the simplex method for linear programming, with early contributions from Harold Kuhn and Albert Tucker, whose Karush-Kuhn-Tucker conditions characterize optimality for constrained nonlinear programs including QP. These conditions are now a cornerstone of theoretical and computational optimization.

Problem Formulation and Convexity

The matrix Q determines the geometry of the QP. If Q is positive definite, the objective surface is strictly bowl-shaped and the unique minimizer can be found by setting the gradient to zero and solving a linear system, although constraints complicate this simple picture. If Q is positive semidefinite but not positive definite, the objective has flat directions and the minimizer may not be unique. Indefinite Q leads to non-convex problems where the feasible region may contain many distinct local optima. The Cornell Computational Optimization wiki on quadratic programming provides worked examples of each case and illustrates how the shape of Q governs the choice of solution method. Practical problems in engineering and statistics most often yield convex QPs because they arise from least-squares objectives or regularized formulations where Q is constructed as a covariance or Gram matrix.

Solution Algorithms

Three families of algorithms dominate QP solvers. The active-set method maintains a working set of inequality constraints that are treated as equalities at each iteration, solving a sequence of equality-constrained subproblems and updating the working set based on optimality conditions. This approach is efficient when the number of active constraints at the solution is small relative to the total problem size. Interior-point methods, also called barrier methods, traverse the interior of the feasible region by adding a logarithmic barrier term to the objective and solving a sequence of increasingly exact approximations; they are preferred for large-scale dense or structured problems because their convergence does not depend strongly on the number of constraints. The paper Algorithms for Convex Quadratic Programming by Hungerlaender (arXiv:1409.5222) surveys these families and proposes a hybrid approach combining augmented Lagrangian and infeasible active-set steps that converges in very few outer iterations for many practical problem instances.

Applications in Machine Learning and Engineering

The training of support vector machine (SVM) classifiers reduces to a convex QP: finding the maximum-margin hyperplane separating two classes is equivalent to minimizing a quadratic objective over the coefficients of the decision function subject to linear constraints from the training data. Portfolio optimization in quantitative finance requires minimizing a quadratic risk (variance) objective subject to linear budget and position constraints, a formulation first studied systematically by Harry Markowitz. In model predictive control, a QP is solved at each time step to compute optimal control inputs over a finite horizon while respecting physical constraints on actuators and states. The NIST Digital Library of Mathematical Functions documents the mathematical foundations underlying many of these formulations.

Applications

Quadratic programming has applications in a wide range of disciplines, including:

• Support vector machine training in machine learning classification and regression
• Portfolio optimization and risk minimization in quantitative finance
• Model predictive control and trajectory planning in robotics and autonomous systems
• Structural analysis and shape optimization in mechanical and civil engineering
• Signal recovery and compressed sensing in signal processing