Quadratically constrained quadratic program

Quadratically constrained quadratic program

In mathematics, 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

: egin{align}& ext{minimize} && frac12 x^ op P_0 x + q_0^ op x \& ext{subject to} && x^ op P_i x + q_i^ op x + r_i leq 0 quad ext{for } i = 1,dots,m , \&&& Ax = b, end{align}

where "P"0, … "P""n" are "n"-by-"n" matrices and "x" ∈ R"n" is the optimization variable.

If "P"1, … "P""n" 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"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. But 0–1 integer programming is NP-hard, so QCQP is also NP-hard.

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 easily formulated as a QCQP, which allows obtaining good lower bounds using SDP realization of the dual.

Special cases

There are two main relaxations of QCQP: using semidefinite programming (SDP), and using the reformulation- linearization technique (RLT).

Semidefinite programming

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

References

* Stephen Boyd and Lieven Vandenberghe, [http://www.stanford.edu/~boyd/cvxbook/ Convex Optimization] (book in pdf)


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of mathematics articles (Q) — NOTOC Q Q analog Q analysis Q derivative Q difference polynomial Q exponential Q factor Q Pochhammer symbol Q Q plot Q statistic Q systems Q test Q theta function Q Vandermonde identity Q.E.D. QED project QR algorithm QR decomposition Quadratic… …   Wikipedia

  • 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 Vert 2 leq c i^T x + d i,quad i = 1,dots,m:Fx = g where the problem parameters are f in mathbb{R}^n, A i in mathbb{R}^n i} …   Wikipedia

  • QQP — Quantum Quality Productions (Business » Firms) * Quality Quick Print (Computing » General) * Quadratically constrained Quadratic Program (Academic & Science » Mathematics) * Qatar Quality Products (Business » Firms) * Qatar Quality Products… …   Abbreviations dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”