This paper studies several classes of nonconvex optimization problems defined over convex cones, establishing connections between them and demonstrating that they can be equivalently formulated as convex completely positive programs. The problems being studied include: a quadratically constrained quadratic program (QCQP), a quadratic program with complementarity constraints (QPCC), and rank constrained semidefinite programs. Our results do not make any boundedness assumptions on the feasible regions of the various problems considered. The first stage in the reformulation is to cast the problem as a conic QCQP with just one nonconvex constraint $q(x) \leq 0$, where $q(x)$ is nonnegative over the (convex) conic and linear constraints, so the problem fails the Slater constraint qualification. A quadratic program with (linear) complementarity constraints (or QPCC) has such a structure; we prove the converse, namely that any conic QCQP satisfying a constraint qualification can be expressed as an equivalent conic QPCC. The second stage of the reformulation lifts the problem to a completely positive program, and exploits and generalizes a result of Burer. We also show that a Frank-Wolfe type result holds for a subclass of this class of QCQPs. Further, we derive necessary and sufficient optimality conditions for nonlinear programs where the only nonconvex constraint is a quadratic constraint of the structure considered elsewhere in the paper.
Citation
Mathematical Sciences, Rensselaer Polytechnic Institute, Troy NY 12180 USA. January 26, 2014. Revised October 17, 2014.