quadratic programming
Linear programming optimizes a flat, tilted objective over a fenced region — the cost rises at a constant rate in each direction. But many real objectives CURVE: risk grows quadratically with exposure, energy with displacement, error with deviation. Quadratic programming is the next step up: minimize a quadratic (bowl-shaped) objective subject to LINEAR constraints. It is the simplest constrained problem with genuine curvature, and it sits at the heart of countless applications.
A quadratic program has the form: minimize (1/2) x^T Q x + c^T x subject to linear constraints A x <= b and possibly E x = d. The matrix Q encodes the curvature of the objective. If Q is positive semidefinite, the objective is convex (a bowl), the feasible region is a convex polyhedron, and the whole problem is a CONVEX optimization — solvable efficiently and reliably to a global optimum, typically by an interior-point method or an active-set method (the latter a close cousin of the simplex method that decides which inequality constraints are active). If Q has negative eigenvalues the problem is non-convex and much harder (NP-hard in general). The KKT conditions of a convex QP form a single LINEAR system (plus the complementary-slackness logic for inequalities), which is why convex QPs are so tractable.
Quadratic programming is everywhere it matters: it is the inner problem of support vector machines (maximizing a margin), of portfolio optimization (Markowitz mean-variance, minimizing risk x^T Q x for a target return), of model-predictive control (steering a system while penalizing effort), and of the sequential subproblems in SQP, a leading method for general nonlinear constrained optimization. The honest scope: the clean, efficient story holds for CONVEX QPs (Q positive semidefinite); a non-convex (indefinite Q) QP can have many local minima and is genuinely hard. And like all constrained methods it inherits the KKT machinery — getting feasibility, multiplier signs, and active-set bookkeeping right is where the real implementation effort goes.
Portfolio choice: pick weights x for assets to minimize risk (1/2) x^T Q x (Q is the covariance matrix, the curvature) subject to the budget sum x_i = 1 and a required return r^T x >= R, with x >= 0. This is a convex QP — its bowl-shaped objective and linear constraints yield a unique efficient portfolio, found in milliseconds by a QP solver.
Curved (quadratic) objective, straight (linear) constraints.
QP is easy only when Q is positive semidefinite (a convex bowl); then it solves reliably to a global optimum. An indefinite Q makes the QP non-convex with possibly many local minima and is NP-hard in general — so always check the curvature matrix's definiteness before trusting a fast solve.