On exact Reznick, Hilbert-Artin and Putinar's representations
From MaRDI portal
Publication:2029015
DOI10.1016/j.jsc.2021.03.005zbMath1476.14102arXiv1811.10062MaRDI QIDQ2029015
Mohab Safey El Din, Victor Magron
Publication date: 3 June 2021
Published in: Journal of Symbolic Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.10062
semidefinite programming; real algebraic geometry; hybrid numeric-symbolic algorithm; Putinar's representation; Reznick's representation; sums of squares decomposition
68W30: Symbolic computation and algebraic computation
11E25: Sums of squares and representations by other particular quadratic forms
14Q30: Computational real algebraic geometry
Related Items
Dual Certificates and Efficient Rational Sum-of-Squares Decompositions for Polynomial Optimization over Compact Sets, Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients, On the effective Putinar's Positivstellensatz and moment approximation, Rational dual certificates for weighted sums-of-squares polynomials with boundable bit size, Pourchet’s theorem in action: decomposing univariate nonnegative polynomials as sums of five squares, SONC optimization and exact nonnegativity certificates via second-order cone programming
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Global optimization of polynomials restricted to a smooth variety using sums of squares
- Variant quantifier elimination
- Tight bounds for rational sums of squares over totally real fields
- Efficient and accurate computation of upper bounds of approximation errors
- Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients
- The algebraic degree of semidefinite programming
- On the complexity of Putinar's Positivstellensatz
- The Voronoi diagram of three lines
- Solving systems of polynomial inequalities in subexponential time
- Extremal psd forms with few terms
- Geometric algorithms and combinatorial optimization.
- Uniform denominators in Hilbert's seventeenth problem
- Moment matrices, border bases and real radical computation
- Intrinsic complexity estimates in polynomial optimization
- On the geometry of polar varieties
- On the minimum of a positive polynomial over the standard simplex
- Formalization of Bernstein polynomials and applications to global optimization
- Computing sum of squares decompositions with rational coefficients
- Generalized polar varieties: geometry and algorithms
- Testing sign conditions on a multivariate polynomial and applications
- There are significantly more nonnegative polynomials than sums of squares
- Global Optimization with Polynomials and the Problem of Moments
- Real Schubert Calculus: Polynomial Systems and a Conjecture of Shapiro and Shapiro
- On the Turing Model Complexity of Interior Point Methods for Semidefinite Programming
- Exact Algorithms for Linear Matrix Inequalities
- Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set
- Global optimization of polynomials using generalized critical values and sums of squares
- A proof of the monotone column permanent (MCP) conjecture for dimension 4 via sums-of-squares of rational functions
- Computing rational solutions of linear matrix inequalities
- Computing Rational Points in Convex Semialgebraic Sets and Sum of Squares Decompositions
- A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
- New upper bounds for kissing numbers from semidefinite programming
- Sums of squares over totally real fields are rational sums of squares
- The quickhull algorithm for convex hulls
- R <scp>eal</scp> c <scp>ertify</scp>
- An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert’s 17th problem
- On Exact Polya and Putinar's Representations
- Facial reduction for exact polynomial sum of squares decomposition
- Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions
- Exact certification of global optimality of approximate factorizations via rationalizing sums-of-squares with floating point scalars
- Algorithms in real algebraic geometry
- Finding at least one point in each connected component of a real algebraic set defined by a single equation
- Polar varieties and efficient real elimination
