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
\begin{align} &minimize&&\tfrac12xTP0x+
| T | |
| q | |
| 0 |
x\\ &subjectto&&\tfrac12xTPix+
| T | |
| q | |
| i |
x+ri\leq0 fori=1,...,m,\\ &&&Ax=b,\end{align}
where P0, ..., Pm are n-by-n matrices and x ∈ Rn 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.
A convex QCQP problem can be efficiently solved using an interior point method (in a polynomial time), typically requiring around 30-60 iterations to converge. Solving the general non-convex 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 ∈ . 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.
However, even for a nonconvex QCQP problem a local solution can generally be found with a nonconvex variant of the interior point method. In some cases (such as when solving nonlinear programming problems with a sequential QCQP approach) these local solutions are sufficiently good to be accepted.
There are two main relaxations of QCQP: using semidefinite programming (SDP), and using the reformulation-linearization technique (RLT). For some classes of QCQP problems (precisely, QCQPs with zero diagonal elements in the data matrices), second-order cone programming (SOCP) and linear programming (LP) relaxations providing the same objective value as the SDP relaxation are available.[1]
Nonconvex QCQPs with non-positive off-diagonal elements can be exactly solved by the SDP or SOCP relaxations,[2] and there are polynomial-time-checkable sufficient conditions for SDP relaxations of general QCQPs to be exact.[3] Moreover, it was shown that a class of random general QCQPs has exact semidefinite relaxations with high probability as long as the number of constraints grows no faster than a fixed polynomial in the number of variables.
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.
| Name | Brief info | |
|---|---|---|
| ALGLIB | ALGLIB, an open source/commercial numerical library, includes a QP solver supporting quadratic equality/inequality/range constraints, as well as other (conic) constraint types. | |
| 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. | |
| AMPL | ||
| CPLEX | Popular solver with an API for several programming languages. Free for academics. | |
| 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 CPLEX, SNOPT and KNITRO. | |
| Wolfram Mathematica | Able to solve QCQP type of problems using functions like . |