Quadratically constrained quadratic program

In

objective function and the constraints are quadratic functions

{\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

quadratic program

.

Hardness

Solving the general case is an

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

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

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.
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 KNITRO .
Wolfram Mathematica	Able to solve QCQP type of problems using functions like Minimize.

References

S2CID 254701008
.

S2CID 1241391
.

^
S2CID 254143721
.

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

Further reading

In statistics

Albers C. J., Critchley F., Gower, J. C. (2011). "Quadratic Minimisation Problems in Statistics" (PDF). Journal of Multivariate Analysis. 102 (3): 698–713.
hdl:11370/6295bde7-4de1-48c2-a30b-055eff924f3e.{{cite journal}}: CS1 maint: multiple names: authors list (link
)

External links

NEOS Optimization Guide: Quadratic Constrained Quadratic Programming

Retrieved from "https://en.wikipedia.org/w/index.php?title=Quadratically_constrained_quadratic_program&oldid=1199100605"

[1] S2CID 254701008
.

[2] S2CID 1241391
.

[:0-3] 
S2CID 254143721
.

[1]

[2]

[3]