Optimization Online


On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity

Amir Ali Ahmadi(a_a_a***at***princeton.edu)
Georgina Hall(gh4***at***princeton.edu)

Abstract: In recent years, techniques based on convex optimization and real algebra that produce converging hierarchies of lower bounds for polynomial optimization problems (POPs) have gained much popularity. At their heart, these hierarchies rely crucially on Positivstellens\"atze from the late 20th century (e.g., due to Stengle, Putinar, or Schm\"udgen) that certify positivity of a polynomial on an arbitrary basic semialgebraic set. In this paper, we show that such hierarchies could in fact be designed from much more limited Positivstellens\"atze dating back to the early 20th century that only certify positivity of a polynomial globally. More precisely, we show that any inner approximation to the cone of positive homogeneous polynomials that is arbitrarily tight can be turned into a converging hierarchy for general polynomial optimization problems with compact feasible sets. This in particular leads to a semidefinite programming-based hierarchy that relies solely on Artin's solution to Hilbert's 17th problem. We also use a classical result of Poly\'a on global positivity of even forms to construct an ``optimization-free'' converging hierarchy for general POPs with compact feasible sets. This hierarchy only requires polynomial multiplication and checking nonnegativity of coefficients of certain fixed polynomials. As a corollary, we obtain new linear programming and second-order cone programming-based hierarchies for POPs that rely on the recently introduced concepts of dsos (diagonally dominant sum of squares) and sdsos (scaled diagonally dominant sum of squares) polynomials.

Keywords: Positivstellensatze, polynomial optimization, convex optimization

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming

Category 3: Global Optimization


Download: [PDF]

Entry Submitted: 10/09/2017
Entry Accepted: 10/09/2017
Entry Last Modified: 10/09/2017

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