A new approximation hierarchy for polynomial conic optimization

Peter J.C. Dickinson, Janez Povh*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

In this paper we consider polynomial conic optimization problems, where the feasible set is defined by constraints in the form of given polynomial vectors belonging to given nonempty closed convex cones, and we assume that all the feasible solutions are non-negative. This family of problems captures in particular polynomial optimization problems (POPs), polynomial semi-definite polynomial optimization problems (PSDPs) and polynomial second-order cone-optimization problems (PSOCPs). We propose a new general hierarchy of linear conic optimization relaxations inspired by an extension of Pólya’s Positivstellensatz for homogeneous polynomials being positive over a basic semi-algebraic cone contained in the non-negative orthant, introduced in Dickinson and Povh (J Glob Optim 61(4):615–625, 2015). We prove that based on some classic assumptions, these relaxations converge monotonically to the optimal value of the original problem. Adding a redundant polynomial positive semi-definite constraint to the original problem drastically improves the bounds produced by our method. We provide an extensive list of numerical examples that clearly indicate the advantages and disadvantages of our hierarchy. In particular, in comparison to the classic approach of sum-of-squares, our new method provides reasonable bounds on the optimal value for POPs, and strong bounds for PSDPs and PSOCPs, even outperforming the sum-of-squares approach in these latter two cases.

Original languageEnglish
Pages (from-to)37-67
Number of pages31
JournalComputational optimization and applications
Volume73
Issue number1
DOIs
Publication statusPublished - 15 May 2019

Keywords

  • Approximation hierarchy
  • Linear programming
  • Polynomial conic optimization
  • Polynomial second-order cone programming
  • Polynomial semi-definite programming
  • Semi-definite programming

Fingerprint Dive into the research topics of 'A new approximation hierarchy for polynomial conic optimization'. Together they form a unique fingerprint.

Cite this