Quadratically constrained quadratic program

From Wikipedia, the free encyclopedia

In mathematics, a general quadratically constrained quadratic program (QCQP) is an optimization problem of the form

$\begin{align} & \text{minimize} && \tfrac12 x^\top P_0 x + q_0^\top x \\ & \text{subject to} && x^\top P_i x + q_i^\top x + r_i \leq 0 \quad \text{for } i = 1,\dots,m , \\ &&& Ax = b. \end{align}$

where $P_0,\dots,P_m \in \mathbb{R}^{n\times n}$ and $x \$ is the optimization variable.

1 Hardness
2 Examples
- 2.1 Max Cut
3 Special cases
- 3.1 Semidefinite_programming
4 References

[edit] Hardness

Solving the general case is an NP-hard problem. To see this, note that the constraints can be used to model Boolean constraints or any polynomial minimization. For example, the constraint $x_1(1-x_1) \leq 0$ and $x_1(1-x_1) \geq 0$ is equivalent to the constraint $x_1(1-x_1) = 0 \$ , which is in turn equivalent to the constraint $x_1 \in \{0,1\}$ . This is a constraint in integer programming.

[edit] Examples

[edit] Max Cut

Maximum Cut is a problem graph theory, whic h is NP-hard. Given a graph G=(V,E), the prpblem is to find a subset of the vertices $S \in V$ , such that the sum of edges between vertices that belong to the set, and the rest of the verices is maximized. Max Cut can be easily formulated as a QCQP, which allows to obtain good lower bounds using SDP relazation of the dual.