Quadratically Constrained Quadratic Program

See: Optimization Problem, Objective Function, Function Constraint, Quadratic Function, Quadratically Constrained Quadratic Programming Problem, Quadratic Programming Problem, Nonconvex Quadratically Constrained Quadratic Program.

References

(Wikipedia - QCQP, 2011-Jun-13) ⇒ http://en.wikipedia.org/wiki/Quadratically_constrained_quadratic_program
- QUOTE: In mathematics, 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: minimize [math]\displaystyle{ \tfrac12 x^\top P_0 x + q_0^\top x }[/math] subject to [math]\displaystyle{ \tfrac12 x^\top P_i x + q_i^\top x + r_i \leq 0 \quad \text{for } i = 1,\dots,m }[/math] and to [math]\displaystyle{ Ax = b }[/math], where P₀, … P_m are n-by-n matrices and [math]\displaystyle{ x }[/math] ∈ Rⁿ is the optimization variable. If P₀, … Pm are all positive semidefinite, then the problem is convex. If these matrices are neither positive or negative semidefinite, the problem is non-convex. If these are all zero, then the constraints are in fact linear and the problem is a quadratic program. … Solving the general case is an NP-hard problem.

(Charles Audet, Pierre Hansen, Brigitte Jaumard and Gilles Savard, 2000) ⇒ Charles Audet, Pierre Hansen, Brigitte Jaumard and Gilles Savard. (2000). “A branch and cut algorithm for nonconvex quadratically constrained quadratic programming.” In: Mathematical Programming, 87(1). doi:10.1007/s101079900106
- ABSTRACT: We present a branch and cut algorithm that yields in finite time, a globally ε-optimal solution (with respect to feasibility and optimality) of the nonconvex quadratically constrained quadratic programming problem. The idea is to estimate all quadratic terms by successive linearizations within a branching tree using Reformulation-Linearization Techniques (RLT). To do so, four classes of linearizations (cuts), depending on one to three parameters, are detailed. For each class, we show how to select the best member with respect to a precise criterion. The cuts introduced at any node of the tree are valid in the whole tree, and not only within the subtree rooted at that node. In order to enhance the computational speed, the structure created at any node of the tree is flexible enough to be used at other nodes. Computational results are reported that include standard test problems taken from the literature. Some of these problems are solved for the first time with a proof of global optimality.