2023 journal article
Rational dual certificates for weighted sums-of-squares polynomials with boundable bit size
JOURNAL OF SYMBOLIC COMPUTATION, 121.
author keywords: Polynomial optimization; Nonnegativity certificates; Sums-of-squares decomposition; Computational real algebraic geometry; Conic programming
TL;DR:
This article analyzes the complexity of rational dual certificates of WSOS polynomials by bounding the bit sizes of integer dual certificates as a function of parameters such as the degree and the number of variables of the polynmials, or their distance from the boundary of the cone.
(via Semantic Scholar)
open access via arxiv.org (repository)
Source: Web Of Science
Added: January 2, 2024
In Davis and Papp (2022), the authors introduced the concept of dual certificates of (weighted) sum-of-squares polynomials, which are vectors from the dual cone of weighted sums of squares (WSOS) polynomials that can be interpreted as nonnegativity certificates. This initial theoretical work showed that for every polynomial in the interior of a WSOS cone, there exists a rational dual certificate proving that the polynomial is WSOS. In this article, we analyze the complexity of rational dual certificates of WSOS polynomials by bounding the bit sizes of integer dual certificates as a function of parameters such as the degree and the number of variables of the polynomials, or their distance from the boundary of the cone. After providing a general bound, we explore several special cases, such as univariate polynomials nonnegative over the real line or a bounded interval, represented in different commonly used bases. We also provide an algorithm which runs in rational arithmetic and computes a rational certificate with boundable bit size for a WSOS lower bound of the input polynomial.