- On QPCCs, QCQPs and Completely Positive Programs Lijie Bai (bail.rpigmail.com) John E Mitchell (mitchjrpi.edu) Jong-Shi Pang (jongshipusc.edu) Abstract: 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. Keywords: QCQP · QPCC · Completely Positive Representation · rank- constrained SDP · Local Optimality Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization ) Category 2: Complementarity and Variational Inequalities Category 3: Linear, Cone and Semidefinite Programming Citation: Mathematical Sciences, Rensselaer Polytechnic Institute, Troy NY 12180 USA. January 26, 2014. Revised October 17, 2014. Download: [PDF]Entry Submitted: 01/26/2014Entry Accepted: 01/26/2014Entry Last Modified: 10/27/2014Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.