A geometrical analysis on convex conic reformulations of quadratic and polynomial optimization problems

Sunyoung Kim, Masakazu Kojima, Kim Chuan Toh

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

We present a unified geometrical analysis on the completely positive programming (CPP) reformulations of quadratic optimization problems (QOPs) and their extension to polynomial optimization problems (POPs) based on a class of geometrically defined nonconvex conic programs and their convexification. The class of nonconvex conic programs minimize a linear objective function in a vector space V over the constraint set represented geometrically as the intersection of a nonconvex cone K ⊂ V, a face J of the convex hull of K, and a parallel translation L of a hyperplane. We show that under moderate assumptions, 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 L. The replacement procedure is applied for deriving the CPP reformulations of QOPs and their extension to POPs.

Original languageEnglish
Pages (from-to)1251-1273
Number of pages23
JournalSIAM Journal on Optimization
Volume30
Issue number2
DOIs
StatePublished - 2020

Keywords

  • Completely positive programming reformulation
  • Conic optimization problems
  • Faces of the completely positive cone
  • Polynomial optimization problems
  • Quadratic programs

Fingerprint

Dive into the research topics of 'A geometrical analysis on convex conic reformulations of quadratic and polynomial optimization problems'. Together they form a unique fingerprint.

Cite this