TY - JOUR

T1 - On the construction of converging hierarchies for polynomial optimization based on certificates of global positivity

AU - Ahmadi, Amir Ali

AU - Hall, Georgina

N1 - Funding Information:
Funding: This work is partially funded by a Defense Advanced Research Projects Agency Young Faculty Award, a U.S. Air Force Office of Scientific Research Young Investigator Award, a National Science Foundation CAREER Award, a Google Faculty Award, and a Sloan Fellowship.
Publisher Copyright:
Copyright: © 2019 INFORMS

PY - 2019

Y1 - 2019

N2 - In recent years, techniques based on convex optimization and real algebra that produce converging hierarchies of lower bounds for polynomial minimization problems have gained much popularity. At their heart, these hierarchies rely crucially on Positivstellensätze from the late 20th century (e.g., due to Stengle, Putinar, or Schmüdgen) that certify positivity of a polynomial on an arbitrary closed basic semialgebraic set. In this paper, we show that such hierarchies could in fact be designed from much more limited Positivstellensätze 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 of lower bounds for general polynomial minimization 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 from Pólya on global positivity of even forms to construct an “optimization-free” converging hierarchy for general polynomial minimization problems with compact feasible sets. This hierarchy requires only polynomial multiplication and checking nonnegativity of coefficients of certain fixed polynomials. As a corollary, we obtain new linear programming–based and second-order cone programming–based hierarchies for polynomial minimization problems that rely on the recently introduced concepts of diagonally dominant sum of squares and scaled diagonally dominant sum of squares polynomials. We remark that the scope of this paper is theoretical at this stage, as our hierarchies—though they involve at most two sum of squares constraints or only elementary arithmetic at each level—require the use of bisection and increase the number of variables (respectively, the degree) of the problem by the number of inequality constraints plus three (respectively, by a factor of two).

AB - In recent years, techniques based on convex optimization and real algebra that produce converging hierarchies of lower bounds for polynomial minimization problems have gained much popularity. At their heart, these hierarchies rely crucially on Positivstellensätze from the late 20th century (e.g., due to Stengle, Putinar, or Schmüdgen) that certify positivity of a polynomial on an arbitrary closed basic semialgebraic set. In this paper, we show that such hierarchies could in fact be designed from much more limited Positivstellensätze 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 of lower bounds for general polynomial minimization 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 from Pólya on global positivity of even forms to construct an “optimization-free” converging hierarchy for general polynomial minimization problems with compact feasible sets. This hierarchy requires only polynomial multiplication and checking nonnegativity of coefficients of certain fixed polynomials. As a corollary, we obtain new linear programming–based and second-order cone programming–based hierarchies for polynomial minimization problems that rely on the recently introduced concepts of diagonally dominant sum of squares and scaled diagonally dominant sum of squares polynomials. We remark that the scope of this paper is theoretical at this stage, as our hierarchies—though they involve at most two sum of squares constraints or only elementary arithmetic at each level—require the use of bisection and increase the number of variables (respectively, the degree) of the problem by the number of inequality constraints plus three (respectively, by a factor of two).

KW - Convex optimization

KW - Polynomial optimization

KW - Positivstellensätze

UR - http://www.scopus.com/inward/record.url?scp=85074014343&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85074014343&partnerID=8YFLogxK

U2 - 10.1287/moor.2018.0962

DO - 10.1287/moor.2018.0962

M3 - Article

AN - SCOPUS:85074014343

SN - 0364-765X

VL - 44

SP - 1192

EP - 1207

JO - Mathematics of Operations Research

JF - Mathematics of Operations Research

IS - 4

ER -