4.6 Article

DUAL CERTIFICATES AND EFFICIENT RATIONAL SUM-OF-SQUARES DECOMPOSITIONS FOR POLYNOMIAL OPTIMIZATION OVER COMPACT SETS

Journal

SIAM JOURNAL ON OPTIMIZATION
Volume 32, Issue 4, Pages 2461-2492

Publisher

SIAM PUBLICATIONS
DOI: 10.1137/21M1422574

Keywords

Key words; polynomial optimization; nonnegativity certificates; sum-of-squares; nonsymmetric conic optimization

Funding

  1. National Science Foundation [DMS-1719828, DMS-1847865]

Ask authors/readers for more resources

In this paper, we study the problem of computing weighted sum-of-squares (WSOS) certificates for positive polynomials over a compact semialgebraic set. We introduce the concept of dual certificates and provide a new short proof of Powers's theorems on the existence of rational WSOS certificates. We also propose an algorithm for computing the optimal WSOS lower bound of a given polynomial along with a rational dual certificate.
We study the problem of computing weighted sum-of-squares (WSOS) certificates for positive polynomials over a compact semialgebraic set. Building on the theory of interior-point methods for convex optimization, we introduce the concept of dual certificates, which allows us to interpret vectors from the dual of the sum-of-squares cone as rigorous nonnegativity certificates of a WSOS polynomial. Whereas conventional WSOS certificates are alternative representations of the polynomials they certify, dual certificates are distinct from the certified polynomials; moreover, each dual certificate certifies a full-dimensional convex cone of WSOS polynomials. For a theoretical application, we give a short new proof of Powers's theorems on the existence of rational WSOS certificates of positive polynomials. For a computational application, we show that exact WSOS certificates can be constructed from numerically computed dual certificates at little additional cost, without any rounding or projection steps applied to the numerical certificates. We also present an algorithm for computing the optimal WSOS lower bound of a given polynomial along with a rational dual certificate, with a polynomial-time computational cost per iteration and linear rate of convergence.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.6
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available