Quadratically constrained quadratic program

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In mathematical optimization, a quadratically constrained quadratic program (QCQP) is an optimization problem in which both the objective function and the constraints are quadratic functions. It has the form

where P0, … Pm are n-by-n matrices and xRn is the optimization variable.

If P0, … Pm are all positive semidefinite, then the problem is convex. If these matrices are neither positive nor negative semidefinite, the problem is non-convex. If P1, … Pm are all zero, then the constraints are in fact linear and the problem is a quadratic program.


Solving the general case is an NP-hard problem. To see this, note that the two constraints x1(x1 − 1) ≤ 0 and x1(x1 − 1) ≥ 0 are equivalent to the constraint x1(x1 − 1) = 0, which is in turn equivalent to the constraint x1 ∈ {0, 1}. Hence, any 0–1 integer program (in which all variables have to be either 0 or 1) can be formulated as a quadratically constrained quadratic program. Since 0–1 integer programming is NP-hard in general, QCQP is also NP-hard.


There are two main relaxations of QCQP: using semidefinite programming (SDP), and using the reformulation-linearization technique (RLT).

Semidefinite programming[edit]

When P0, … Pm are all positive-definite matrices, the problem is convex and can be readily solved using interior point methods, as done with semidefinite programming.


Max Cut is a problem in graph theory, which is NP-hard. Given a graph, the problem is to divide the vertices in two sets, so that as many edges as possible go from one set to the other. Max Cut can be formulated as a QCQP, and SDP relaxation of the dual provides good lower bounds.

Solvers and scripting (programming) languages[edit]

Name Brief info
Artelys Knitro Knitro is a solver specialized in nonlinear optimization, but also solves linear programming problems, quadratic programming problems, second-order cone programming, systems of nonlinear equations, and problems with equilibrium constraints.
FICO Xpress A commercial optimization solver for linear programming, non-linear programming, mixed integer linear programming, convex quadratic programming, convex quadratically constrained quadratic programming, second-order cone programming and their mixed integer counterparts.
CPLEX Popular solver with an API for several programming languages. Free for academics.
Gurobi Solver with parallel algorithms for large-scale linear programs, quadratic programs and mixed-integer programs. Free for academic use.
MOSEK A solver for large scale optimization with API for several languages (C++,java,.net, Matlab and python)
TOMLAB Supports global optimization, integer programming, all types of least squares, linear, quadratic and unconstrained programming for MATLAB. TOMLAB supports solvers like Gurobi, CPLEX, SNOPT and KNITRO.


  • Boyd, Stephen; Lieven Vandenberghe (2004). Convex Optimization. Cambridge: Cambridge University Press. ISBN 978-0-521-83378-3.

Further reading[edit]

In statistics[edit]

  • Albers CJ, Critchley F, Gower, JC (2011). "Quadratic Minimisation Problems in Statistics". Journal of Multivariate Analysis. 102 (3): 698–713. doi:10.1016/j.jmva.2009.12.018.CS1 maint: Multiple names: authors list (link)

External links[edit]