Quadratic programming

related topics
{math, number, function}
{area, part, region}

Quadratic programming (QP) is a special type of mathematical optimization problem. It is the problem of optimizing (minimizing or maximizing) a quadratic function of several variables subject to linear constraints on these variables.

The quadratic programming problem can be formulated as:[1]

Assume x belongs to \mathbb{R}^{n} space. The n×n matrix Q is symmetric, and c is any n×1 vector.

Minimize (with respect to x)

Subject to one or more constraints of the form:

where \mathbf{x}^T indicates the vector transpose of \mathbf{x}. The notation  Ax \leq b means that every entry of the vector Ax is less than or equal to the corresponding entry of the vector \mathbf b.

If the matrix Q\; is positive semidefinite matrix, then f() is a convex function: In this case the quadratic program has a global minimizer if there exists some feasible vector x (satisfying the constraints) and if f() is bounded below on the feasible region. If the matrix Q is positive definite and the problem has a feasible solution, then the global minimizer is unique.

If Q\; is zero, then the problem becomes a linear program.

Contents

Solution methods

If there are only equality constraints, then the QP can be solved by a linear system. Otherwise, a variety of methods for solving the QP are commonly used, including

Convex quadratic programming is a special case of the more general field of convex optimization.

Full article ▸

related documents
Graph of a function
General number field sieve
Currying
Binary operation
Closed set
Sharp-P-complete
Concatenation
Domain (mathematics)
Unique factorization domain
Hamming distance
Equality (mathematics)
Alexandroff extension
Bijection
Snake lemma
Heap (data structure)
Fibonacci coding
Alternating group
Waring's problem
Haar wavelet
Bogosort
Pseudometric space
Degenerate distribution
Data integrity
Bernoulli process
Boundary (topology)
Static code analysis
Geometric mean
Hilbert's fifth problem
Zeta distribution
Bucket sort