In mathematical optimization, a quadratically constrained quadratic program (QCQP) is an

optimization problem In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables ...

in which both the

objective function In mathematical optimization and decision theory, a loss function or cost function (sometimes also called an error function) is a function that maps an event or values of one or more variables onto a real number intuitively representing some "cost ...

and the constraints are quadratic functions. It has the form :

\begin
& \text && \tfrac12 x^\mathrm P_0 x + q_0^\mathrm x \\
& \text && \tfrac12 x^\mathrm P_i x + q_i^\mathrm x + r_i \leq 0 \quad \text i = 1,\dots,m , \\
&&& Ax = b, 
\end

where ''P''₀, …, ''P''_''m'' are ''n''-by-''n'' matrices and ''x'' ∈ R^''n'' is the optimization variable. If ''P''₀, …, ''P''_''m'' are all positive semidefinite, then the problem is

convex Convex or convexity may refer to: Science and technology * Convex lens, in optics Mathematics * Convex set, containing the whole line segment that joins points ** Convex polygon, a polygon which encloses a convex set of points ** Convex polytop ...

. 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 Linearity is the property of a mathematical relationship ('' function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the 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''₁ ∈ . 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 Semidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize) over the intersection of the cone of positive ...

(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 A second-order cone program (SOCP) is a convex optimization problem of the form :minimize \ f^T x \ :subject to ::\lVert A_i x + b_i \rVert_2 \leq c_i^T x + d_i,\quad i = 1,\dots,m ::Fx = g \ where the problem parameters are f \in \mathbb^n, ...

(SOCP) and linear programming (LP) relaxations providing the same objective value as the SDP relaxation are available. Nonconvex QCQPs with non-positive off-diagonal elements can be exactly solved by the SDP or SOCP relaxations, and there are polynomial-time-checkable sufficient conditions for SDP relaxations of general QCQPs to be exact. 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.

Semidefinite programming

When ''P''₀, …, ''P''_''m'' are all positive-definite matrices, the problem is

and can be readily solved using

interior point method Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in 1 ...

s, as done with

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.

Solvers and scripting (programming) languages

References

External links

NEOS Optimization Guide: Quadratic Constrained Quadratic Programming
Mathematical optimization