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