Dual certificates and efficient rational sum-of-squares decompositions for polynomial optimization over compact sets
From MaRDI portal
Publication:5043282
DOI10.1137/21M1422574zbMATH Open1504.90091arXiv2105.11369OpenAlexW3164934243MaRDI QIDQ5043282FDOQ5043282
Authors: Maria M. Davis, Dávid Papp 
Publication date: 21 October 2022
Published in: SIAM Journal on Optimization (Search for Journal in Brave)
Abstract: 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 cone 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. As a result, rational 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. As an additional algorithmic application, we present an almost entirely numerical hybrid 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.
Full work available at URL: https://arxiv.org/abs/2105.11369
Recommendations
- Positivity certificates and polynomial optimization on non-compact semialgebraic sets
- Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients
- Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients
- Computation of sum of squares polynomials from data points
- On exact Polya and Putinar's representations
Convex programming (90C25) Interior-point methods (90C51) Numerical methods involving duality (49M29) Computational real algebraic geometry (14Q30) Polynomial optimization (90C23)
Cites Work
- Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials
- {\textsc{RealCertify}}: a Maple package for certifying non-negativity
- Title not available (Why is that?)
- Title not available (Why is that?)
- Global optimization with polynomials and the problem of moments
- GloptiPoly
- A mathematical view of interior-point methods in convex optimization
- Sums of squares, moment matrices and optimization over polynomials
- Title not available (Why is that?)
- Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
- Convergent SDP‐Relaxations in Polynomial Optimization with Sparsity
- Title not available (Why is that?)
- Certificates of positivity in the Bernstein basis
- Title not available (Why is that?)
- Formalization of Bernstein polynomials and applications to global optimization
- The algebraic degree of semidefinite programming
- Efficient and accurate computation of upper bounds of approximation errors
- Title not available (Why is that?)
- Computing sum of squares decompositions with rational coefficients
- Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients
- Sparsity in sums of squares of polynomials
- Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars
- Sums of squares of polynomials with rational coefficients
- An efficient algorithm for range computation of polynomials using the Bernstein form
- Rational certificates of positivity on compact semialgebraic sets
- Signomial and polynomial optimization via relative entropy and partial dualization
- Computing rational solutions of linear matrix inequalities
- Validating the completeness of the real solution set of a system of polynomial equations
- Conic programming: infeasibility certificates and projective geometry
- On exact Polya and Putinar's representations
- On exact Reznick, Hilbert-Artin and Putinar's representations
- TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity
- Exact Semidefinite Programming Bounds for Packing Problems
- Sum-of-squares optimization without semidefinite programming
- Alfonso: Matlab Package for Nonsymmetric Conic Optimization
- SONC optimization and exact nonnegativity certificates via second-order cone programming
Cited In (1)
Uses Software
This page was built for publication: Dual certificates and efficient rational sum-of-squares decompositions for polynomial optimization over compact sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5043282)
