mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...

, a quadratically constrained quadratic program (QCQP) is an optimization problem in which both the objective function and the constraints are

quadratic function In mathematics, a quadratic polynomial is a polynomial of degree two in one or more variables. A quadratic function is the polynomial function defined by a quadratic polynomial. Before 20th century, the distinction was unclear between a polynomial ...

s. 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. 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 r ...

and the problem is a

quadratic program Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize (minimize or maximize) a multivariate quadratic function subject to linear constra ...

Hardness

Solving the general case is an

NP-hard In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

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 (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 Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear function#As a polynomial function, li ...

(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 In mathematics, a symmetric matrix M with real entries is positive-definite if the real number z^\textsfMz is positive for every nonzero real column vector z, where z^\textsf is the transpose of More generally, a Hermitian matrix (that is, a c ...

, the problem is convex 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 semidefinite programming.

Example

Max Cut For a graph, a maximum cut is a cut whose size is at least the size of any other cut. That is, it is a partition of the graph's vertices into two complementary sets and , such that the number of edges between and is as large as possible. F ...

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