Quadratically Constrained Quadratic Programming

Quadratically-constrained quadratic programming (QCQP) problems are optimization problems with a quadratic objective function and quadratic constraints. The general QCQP problem has the following form:
$$\begin{array}{ll} \mbox{minimize} & q_0(y) \\ \mbox{subject to} & q_i(y) \leq 0 \, \forall i = 1, \cdots, m \end{array}$$ where $q_i(y) = \frac{1}{2} y^t Q_iy + y^tb_i + c_i, \, y \in R^n$ for all $i = 0, 1, \cdots, m$. The problem is convex if $Q_i$ is positive, semidefinite ($Q_i \succeq 0$) for all $i$, in which case an elegant duality structure is available.

References

• Baron, D. P. 1972. Quadratic programming with quadratic constraints. Naval Research Logistics Quarterly 19(2), 253 – 260.
• Ben-Tal, A. and Teboulle, M. 1996. Hidden convexity in some nonconvex quadratically constrained quadratic programming. Mathematical Programming 72, 51 – 63.
• Ecker, J. G. and Niemi, R. D. 1975. A dual method for quadratic programs with quadratic constraints. SIAM Journal on Applied Mathematics 28(3), 568 – 576.
• Kim, S. and Kojima, M. 2003. Exact solutions of some nonconvex quadratic optimization problems via SDP and SOCP relaxations. Computational Optimization and Applications 26, 143 – 154.
• Linderoth, J. 2005. A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs. Mathematical Programming, Series B 103, 251 – 282.
• Yuan, Y. 1991. A dual algorithm for minimizing a quadratic function with two quadratic constraints. Journal of Computational Mathematics 9(4), 348 – 359.
• Optimization Online Global Optimization area