Optimization Online


New linear and positive semidefinite programming based approximation hierarchies for polynomial optimisation

Peter J.C. Dickinson (peter.dickinson***at***cantab.net)
Janez Povh (janez.povh***at***fis.unm.si)

Abstract: In this paper we consider the set of polynomials which are nonnegative over a subset of the nonnegative orthant, where this subset is described by homogeneous polynomial inequalities. The study of such a set of polynomials is motivated by copositivity and the fact that any bounded polynomial optimisation problem can be reformulated into a conic optimisation problem over such a set. The main work of this paper is to introduce a new hierarchy of linear inner approximations for such a set. This hierarchy can then be improved through the use of positive semidefiniteness. Advantages to these approaches are discussed and some examples are presented.

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

Category 1: Linear, Cone and Semidefinite Programming

Citation: Submitted

Download: [PDF]

Entry Submitted: 06/16/2013
Entry Accepted: 06/16/2013
Entry Last Modified: 04/18/2014

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