Quadratically constrained quadratic program

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{aligned}&{\text{minimize}}&&{\tfrac {1}{2}}x^{\mathrm {T} }P_{0}x+q_{0}^{\mathrm {T} }x\\&{\text{subject to}}&&{\tfrac {1}{2}}x^{\mathrm {T} }P_{i}x+q_{i}^{\mathrm {T} }x+r_{i}\leq 0\quad {\text{for }}i=1,\dots ,m,\\&&&Ax=b,\end{aligned}}

where P₀, ..., P_m are n-by-n matrices and x ∈ Rⁿ is the optimization variable.

If P₀, ..., P_m are all positive semidefinite, then the problem is convex. If these matrices are neither positive nor negative semidefinite, the problem is non-convex. If P₁, ... ,P_m are all zero, then the constraints are in fact linear and the problem is a quadratic program.

Hardness

Solving the general case is an NP-hard problem. To see this, note that the two constraints x₁(x₁ − 1) ≤ 0 and x₁(x₁ − 1) ≥ 0 are equivalent to the constraint x₁(x₁ − 1) = 0, which is in turn equivalent to the constraint x₁ ∈ {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.

Relaxation

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.^[3]

Semidefinite programming

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

Example

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.
QCQP is used to finely tune machine setting in high-precision applications such as photolithography.

Solvers and scripting (programming) languages

References

^ Kimizuka, Masaki; Kim, Sunyoung; Yamashita, Makoto (2019). "Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods". Journal of Global Optimization. 75 (3): 631–654. doi:10.1007/s10898-019-00795-w. ISSN 0925-5001. S2CID 254701008.
^ Kim, Sunyoung; Kojima, Masakazu (2003). "Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations". Computational Optimization and Applications. 26 (2): 143–154. doi:10.1023/A:1025794313696. S2CID 1241391.
^ a b Burer, Samuel; Ye, Yinyu (2019-02-04). "Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs". Mathematical Programming. 181: 1–17. arXiv:1802.02688. doi:10.1007/s10107-019-01367-2. ISSN 0025-5610. S2CID 254143721.

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

External links

NEOS Optimization Guide: Quadratic Constrained Quadratic Programming