A Geometrical Analysis of a Class of Nonconvex Conic Programs for Convex Conic Reformulations of Quadratic and Polynomial Optimization Problems

Abstract

We present a geometrical analysis on the completely positive programming reformulation of quadratic optimization problems and its extension to polynomial optimization problems with a class of geometrically defined nonconvex conic programs and their covexification. The class of nonconvex conic programs is described with a linear objective functionin a linear space $V$, and the constraint set is represented geometrically as the intersection of a nonconvex cone $K\subset V$, a face $J$ of the convex hull of $K$ and a parallel translation $L$ of a supporting hyperplane of the nonconvex cone $K$. We show that under a moderate assumption, the original nonconvex conic program can equivalently be reformulated as a convex conic program by replacing the constraint set with the intersection of $J$ and the hyperplane $L$. The replacement procedure is applied to derive the completely positive programming reformulation of quadratic optimization problems and its extension to polynomial optimization problems.

27 pages, 2 figures

Cited by in corpus (1)

• Doubly nonnegative relaxations are equivalent to completely positive reformulations of quadratic optimization problems with block-clique graph structures