Back to Continuous Optimization

** 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