Quadratically constrained quadratic program
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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} & \text{minimize} && \tfrac12 x^\mathrm{T} P_0 x + q_0^\mathrm{T} x \\ & \text{subject to} && \tfrac12 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{align} where P 0 , ..., P m are n-by-n matrices and x ∈ R n is the optimization variable. If P 0 , ..., 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 1 , ... ,P m are all zero, then the constraints are in fact linear and the problem is a 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{align} & \text{minimize} && \tfrac12 x^\mathrm{T} P_0 x + q_0^\mathrm{T} x \\ & \text{subject to} && \tfrac12 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{align} where P 0 , ..., P m are n-by-n matrices and x ∈ R n is the optimization variable.
If P 0 , ..., 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 1 , ... ,P m are all zero, then the constraints are in fact linear and the problem is a quadratic program. To see this, note that the two constraints x 1 (x 1 − 1) ≤ 0 and x 1 (x 1 − 1) ≥ 0 are equivalent to the constraint x 1 (x 1 − 1) = 0, which is in turn equivalent to the constraint x 1 ∈ {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. 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.
Solvers and scripting (programming) languages
External links
NEOS Optimization Guide: Quadratic Constrained Quadratic Programming
Text derived from https://en.wikipedia.org/w/index.php?oldid=1304340409 under CC BY-SA 4.0; modifications have been made.