On conic QPCCs, conic QCQPs and completely positive programs

• 成果类型: Article
• 署名作者: Bai, Lijie; Mitchell, John E.; Pang, Jong-Shi
• 署名单位: MathWorks; Rensselaer Polytechnic Institute; University of Southern California
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-015-0951-9
• 发表日期: 2016
• 页码: 109-136
• 关键词: constrained quadratic programs; linear complementarity constraints; mathematical programs; optimization problems; nonconvex; approximation; relaxations; EXISTENCE; DECOMPOSITION; semidefinite

摘要

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 conic quadratically constrained quadratic program (QCQP), a conic 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 , where q(x) is nonnegative over the (convex) conic and linear constraints, so the problem fails the Slater constraint qualification. A conic 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 conic 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.