Optimization Online


A new approximation hierarchy for polynomial conic optimization

Peter J.C. Dickinson (peter.dickinson***at***cantab.net)
Janez Povh (janez.povh***at***lecad.fs.uni-lj.si)

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 nonnegative. This family of problems captures in particular polynomial optimization problems, polynomial semidefinite polynomial optimization problems and polynomial second order cone optimization problems. We propose a general hierarchy of linear conic optimization relaxations inspired by an extension of Pólya's Positivstellensatz for homogeneous polynomials being positive over a basic semialgebraic cone contained in the nonnegative orthant. Under some classical assumptions these relaxations converge monotonically to the optimal value of the original problem. The members of this hierarchy provide strong bounds for the optimum value, especially for polynomial semidefinite problems and polynomial second order cone optimization problems, where these bounds are comparable or even outperform the existing bounds based on sum-of-squares. Adding a redundant polynomial positive semidefinite constraint to the original problem improves the bounds drastically. We provide an extensive list of numerical examples which clearly indicate the advantages and disadvantages of our hierarchy.

Keywords: real algebraic geometry; copositive optimization; approximation hierarchy; conic optimization; non-negative polynomials; polynomial optimization

Category 1: Linear, Cone and Semidefinite Programming

Citation: Dickinson, P.J.C. & Povh, J. Comput Optim Appl (2019). https://doi.org/10.1007/s10589-019-00066-0

Download: [PDF]

Entry Submitted: 06/16/2013
Entry Accepted: 06/16/2013
Entry Last Modified: 02/06/2019

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