Optimization Online


On QPCCs, QCQPs and Completely Positive Programs

Lijie Bai (bail.rpi***at***gmail.com)
John E Mitchell (mitchj***at***rpi.edu)
Jong-Shi Pang (jongship***at***usc.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/2014
Entry Accepted: 01/26/2014
Entry Last Modified: 10/27/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society