128.141.76.69 at 15:21, 6 June 2025

2025-06-06T15:21:45Z

New page

{{Short description|Optimization problem in mathematics}}
In [[mathematical optimization]], a '''quadratically constrained quadratic program''' ('''QCQP''') is an [[optimization problem]] in which both the [[objective function]] and the [[constrained optimization|constraints]] are [[quadratic function]]s. It has the form

:<math> \begin{align}
& \text{minimize} && \tfrac12 x^\mathrm{T} P_0 x + q_0^\mathrm{T} x \\
& \text{subject to} && \tfrac12 x^\mathrm{T} P_i x + q_i^\mathrm{T} x + r_i \leq 0 \quad \text{for } i = 1,\dots,m , \\
&&& Ax = b,
\end{align} </math>

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

If ''P''0, ..., ''P''''m'' are all [[Positive-definite matrix|positive semidefinite]], then the problem is [[Convex set|convex]]. If these matrices are neither positive nor negative semidefinite, the problem is non-convex. If ''P''1, ... ,''P''''m'' are all zero, then the constraints are in fact [[Linear map|linear]] and the problem is a [[quadratic program]].

== 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]] 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. 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]] (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]] (LP) relaxations providing the same objective value as the SDP relaxation are available.<ref>{{Cite journal|last1=Kimizuka|first1=Masaki|last2=Kim|first2=Sunyoung|last3=Yamashita|first3=Makoto|date=2019|title=Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods|journal=Journal of Global Optimization|language=en|volume=75|issue=3|pages=631–654|doi=10.1007/s10898-019-00795-w|s2cid=254701008 |issn=0925-5001}}</ref>

Nonconvex QCQPs with non-positive off-diagonal elements can be exactly solved by the SDP or SOCP relaxations,<ref>{{Cite journal|last1=Kim|first1=Sunyoung|last2=Kojima|first2=Masakazu|date=2003|title=Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations|journal=Computational Optimization and Applications|volume=26|issue=2|pages=143–154|doi=10.1023/A:1025794313696|s2cid=1241391 }}</ref> and there are polynomial-time-checkable sufficient conditions for SDP relaxations of general QCQPs to be exact.<ref name=":0">{{Cite journal|last1=Burer|first1=Samuel|last2=Ye|first2=Yinyu|date=2019-02-04|title=Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs|journal=Mathematical Programming|volume=181|pages=1–17|language=en|doi=10.1007/s10107-019-01367-2|issn=0025-5610|arxiv=1802.02688|s2cid=254143721 }}</ref> 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.<ref name=":0" />

=== Semidefinite programming ===
When ''P''0, ..., ''P''''m'' are all [[Positive-definite matrix|positive-definite matrices]], the problem is [[Convex optimization|convex]] and can be readily solved using [[interior point method]]s, as done with [[semidefinite programming]].

== Example ==

* [[Cut (graph theory)|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.
* QCQP is used to finely tune machine setting in high-precision applications such as [[photolithography]].

==Solvers and scripting (programming) languages==

{| class="wikitable"
|-
!Name
!Brief info
|-
|[[ALGLIB]]|| ALGLIB, an open source/commercial numerical library, includes a QP solver supporting quadratic equality/inequality/range constraints, as well as other (conic) constraint types.
|-
|[[Artelys Knitro]]|| Knitro is a solver specialized in nonlinear optimization, but also solves linear programming problems, quadratic programming problems, second-order cone programming, systems of nonlinear equations, and problems with equilibrium constraints.
|-
|[[FICO Xpress]]|| A commercial optimization solver for linear programming, non-linear programming, mixed integer linear programming, convex quadratic programming, convex quadratically constrained quadratic programming, second-order cone programming and their mixed integer counterparts.
|-
|[[AMPL]]||
|-
|[[CPLEX]]|| Popular solver with an API for several programming languages. Free for academics.
|-
|[[MOSEK]]|| A solver for large scale optimization with API for several languages (C++, java, .net, Matlab and python)
|-
|[[TOMLAB]]||Supports global optimization, integer programming, all types of least squares, linear, quadratic and unconstrained programming for [[MATLAB]]. TOMLAB supports solvers like [[CPLEX]], [[SNOPT]] and [[KNITRO]].
|-
|[[Wolfram Mathematica]]||Able to solve QCQP type of problems using functions like {{mono|Minimize}}.
|-
|[https://clarabel.org/ clarabel]|| Open source interior point numerical solver for convex optimization problems, supports second-order cone programming.
|}

== References ==
{{Reflist}}
* {{cite book
| last = Boyd
| first = Stephen
|author2=Lieven Vandenberghe
| title = Convex Optimization
| publisher = Cambridge University Press
| year = 2004
| location = Cambridge
| url = https://web.stanford.edu/~boyd/cvxbook/
| isbn = 978-0-521-83378-3}}

== Further reading ==

=== In statistics ===
* {{cite journal |author=Albers C. J., Critchley F., Gower, J. C. |title=Quadratic Minimisation Problems in Statistics |journal=Journal of Multivariate Analysis |volume=102 |issue=3 |pages=698–713 |year=2011 |doi=10.1016/j.jmva.2009.12.018 |url=https://pure.rug.nl/ws/files/111582994/1_s2.0_S0047259X09002498_main.pdf |hdl=11370/6295bde7-4de1-48c2-a30b-055eff924f3e |hdl-access=free }}

==External links==
* [http://neos-guide.org/content/quadratic-constrained-quadratic-programming NEOS Optimization Guide: Quadratic Constrained Quadratic Programming]

[[Category:Mathematical optimization]]

Quadratically constrained quadratic program - Revision history

128.141.76.69 at 15:21, 6 June 2025