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

, a quadratically constrained quadratic program (QCQP) is an

optimization problem In mathematics, engineering, computer science and economics Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...

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 Constraint may refer to: * Constraint (computer-aided design), a demarcation of geometrical characteristics between two or more entities or solid modeling bodies * Constraint (mathematics), a condition of an optimization problem that the solution m ...

are

quadratic function In mathematics, a quadratic function of a single variable (mathematics), variable is a function (mathematics), function of the form :f(x)=ax^2+bx+c,\quad a \ne 0, where is its variable, and , , and are coefficients. The mathematical expression, e ...

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 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 In mathematics, the term ''linear'' is used in two distinct senses for two different properties: * linearity of a '' function'' (or '' mapping''); * linearity of a '' polynomial''. An example of a linear function is the function defined by f(x) ...

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 constrai ...

Hardness

A convex QCQP problem can be efficiently solved using an interior point method (in a polynomial time), typically requiring around 30-60 iterations to converge. Solving the general non-convex case is an

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

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 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 and objective are represented by linear relationships. Linear ...

(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.

Relaxation

There are two main relaxations of QCQP: using

semidefinite programming Semidefinite programming (SDP) is a subfield of mathematical programming 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 po ...

(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 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 and objective are represented by linear function#As a polynomia ...

(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 \mathbf^\mathsf M \mathbf is positive for every nonzero real column vector \mathbf, where \mathbf^\mathsf is the row vector transpose of \mathbf. Mo ...

, the problem is

and can be readily solved using

interior point method Interior-point methods (also referred to as barrier methods or IPMs) are algorithms for solving Linear programming, linear and nonlinear programming, non-linear convex optimization problems. IPMs combine two advantages of previously-known algorit ...

s, as done with

Example

Max Cut In 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. ...

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. * QCQP is used to finely tune machine setting in high-precision applications such as

photolithography Photolithography (also known as optical lithography) is a process used in the manufacturing of integrated circuits. It involves using light to transfer a pattern onto a substrate, typically a silicon wafer. The process begins with a photosensiti ...

Solvers and scripting (programming) languages

References

External links

NEOS Optimization Guide: Quadratic Constrained Quadratic Programming
Mathematical optimization