Semidefinite Characterization and Computation of Real Radical Ideals

Abstract

For an ideal $I\subseteq \mathbb{R}[x]$ given by a set of generators, a new semidefinite characterization of its real radical $I(V_{\mathbb{R}}(I))$ is presented, provided it is zero-dimensional (even if $I$ is not). Moreover we propose an algorithm using numerical linear algebra and semidefinite optimization techniques, to compute all (finitely many) points of the real variety $V_{\mathbb{R}}(I)$ as well as a set of generators of the real radical ideal. The latter is obtained in the form of a border or Gröbner basis. The algorithm is based on moment relaxations and, in contrast to other existing methods, it exploits the real algebraic nature of the problem right from the beginning and avoids the computation of complex components.

41 pages

References in corpus (1)

• First Steps in Algorithmic Fewnomial Theory

Cited by in corpus (32)

• Theta Bodies for Polynomial Ideals
• Optimization over trace polynomials
• Dualities in Convex Algebraic Geometry
• Homogenization for polynomial optimization with unbounded sets
• Computation with Polynomial Equations and Inequalities arising in Combinatorial Optimization
• State polynomials: positivity, optimization and nonlinear Bell inequalities
• Exact relaxation for polynomial optimization on semi-algebraic sets
• Numerically validating the completeness of the real solution set of a system of polynomial equations
• On the Computation of Matrices of Traces and Radicals of Ideals
• A Sparse Flat Extension Theorem for Moment Matrices
• Computing real radicals by moment optimization
• Exact Moment Representation in Polynomial Optimization
• Nash Equilibrium Problems of Polynomials
• Linear Optimization with Cones of Moments and Nonnegative Polynomials
• Polynomial Optimization with Real Varieties
• The Saddle Point Problem of Polynomials
• Distance to a constitutive tensor isotropy stratum by Lasserre polynomial optimization method
• Finite convergence of the Moment-SOS hierarchy for polynomial matrix optimization
• Unconstraint global polynomial optimization via Gradient Ideal
• A certificate for semidefinite relaxations in computing positive dimensional real varieties
• Algorithms and dimensionality reductions for continuous multifacility ordered median location problems
• The Hierarchy of Local Minimums in Polynomial Optimization
• A prolongation-projection algorithm for computing the finite real variety of an ideal
• Certifying Convergence of Lasserre's Hierarchy via Flat Truncation
• A Semidefinite Approach for Truncated K-Moment Problems
• Tight Relaxations for Polynomial Optimization and Lagrange Multiplier Expressions
• An Algorithm for Finding Positive Solutions to Polynomial Equations
• Tensor Eigenvalue Complementarity Problems
• Stochastic Polynomial Optimization
• Rational Generalized Nash Equilibrium Problems
• Software for the Gale transform of fewnomial systems and a Descartes rule for fewnomials
• Moment Matrices, Border Bases and Real Radical Computation