Quadratically constrained quadratic program
In mathematical optimization, 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
- [math]\displaystyle{ \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 P0, ..., Pm are n-by-n matrices and x ∈ Rn is the optimization variable.
If P0, ..., Pm are all positive semidefinite, then the problem is convex. If these matrices are neither positive nor negative semidefinite, the problem is non-convex. If P1, ... ,Pm 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 x1(x1 − 1) ≤ 0 and x1(x1 − 1) ≥ 0 are equivalent to the constraint x1(x1 − 1) = 0, which is in turn equivalent to the constraint x1 ∈ {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.
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.[1]
Nonconvex QCQPs with non-positive off-diagonal elements can be exactly solved by the SDP or SOCP relaxations,[2] and there are polynomial-time-checkable sufficient conditions for SDP relaxations of general QCQPs to be exact.[3] 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.[3]
Semidefinite programming
When P0, ..., Pm are all positive-definite matrices, the problem is convex and can be readily solved using interior point methods, as done with semidefinite programming.
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 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
| Name | Brief info |
|---|---|
| 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 Minimize. |
References
- ↑ Kimizuka, Masaki; Kim, Sunyoung; Yamashita, Makoto (2019). "Solving pooling problems with time discretization by LP and SOCP relaxations and rescheduling methods" (in en). Journal of Global Optimization 75 (3): 631–654. doi:10.1007/s10898-019-00795-w. ISSN 0925-5001.
- ↑ Kim, Sunyoung; Kojima, Masakazu (2003). "Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations". Computational Optimization and Applications 26 (2): 143–154. doi:10.1023/A:1025794313696.
- ↑ 3.0 3.1 Burer, Samuel; Ye, Yinyu (2019-02-04). "Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs" (in en). Mathematical Programming 181: 1–17. doi:10.1007/s10107-019-01367-2. ISSN 0025-5610.
- Boyd, Stephen; Lieven Vandenberghe (2004). Convex Optimization. Cambridge: Cambridge University Press. ISBN 978-0-521-83378-3. https://web.stanford.edu/~boyd/cvxbook/.
Further reading
In statistics
- Albers C. J., Critchley F., Gower, J. C. (2011). "Quadratic Minimisation Problems in Statistics". Journal of Multivariate Analysis 102 (3): 698–713. doi:10.1016/j.jmva.2009.12.018. https://pure.rug.nl/ws/files/111582994/1_s2.0_S0047259X09002498_main.pdf.
External links
 |  |
