Semidefinite characterization and computation of zero-dimensional real radical ideals

DOI10.1007/S10208-007-9004-YzbMATH Open1176.14010arXivmath/0609528OpenAlexW2156811188MaRDI QIDQ1029543FDOQ1029543

Philipp Rostalski, Jean B. Lasserre, Monique Laurent

Publication date: 13 July 2009

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Abstract: For an ideal $IsubseteqmathbbR[x]$ given by a set of generators, a new semidefinite characterization of its real radical $I(V_{m}athbbR(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_{m}athbbR(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"obner 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.

Full work available at URL: https://arxiv.org/abs/math/0609528

zbMATH Keywords

momentssemidefinite programming[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Gr%EF%BF%BD%EF%BF%BDbner+bases&go=Go Gr��bner bases]eigenvalue methodreal radical idealmoment matricesborder baseszero dimensional ideal

Mathematics Subject Classification ID

Semidefinite programming (90C22) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Numerical computation of solutions to systems of equations (65H10) Real algebraic sets (14P05) Real algebra (13J30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Implementation of interior point methods for mixed semidefinite and second order cone optimization problems
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Algorithm 795
• Detecting Global Optimality and Extracting Solutions in GloptiPoly
• Semidefinite Programming
• Direct methods for primary decomposition
• Global optimization with polynomials and the problem of moments
• Handbook of semidefinite programming. Theory, algorithms, and applications
• Semidefinite representations for finite varieties
• Solving zero-dimensional systems through the rational univariate representation
• Gröbner bases and primary decomposition of polynomial ideals
• Solution of the truncated complex moment problem for flat data
• The truncated complex $K$-moment problem
• Revisiting two theorems of Curto and Fialkow on moment matrices
• The Numerical Solution of Systems of Polynomials Arising in Engineering and Science
• Aspects of semidefinite programming. Interior point algorithms and selected applications
• Solving polynomial equations. Foundations, algorithms, and applications
• Constructions in Algebra
• Motivations for an arbitrary precision interval arithmetic and the MPFI library
• Radical computations of zero-dimensional ideals and real root counting.
• Interior Point Trajectories in Semidefinite Programming
• Symmetric Newton polytopes for solving sparse polynomial systems
• A moment approach to analyze zeros of triangular polynomial sets

Cited In (52)

• The multivariate eigenvalues of symmetric tensors
• Computing real radicals by moment optimization
• Semidefinite Relaxation Methods for Tensor Absolute Value Equations
• The maximum tensor complementarity eigenvalues
• Stochastic polynomial optimization
• Higher-degree tensor eigenvalue complementarity problems
• Tensor complementarity problems. II: Solution methods
• An SDP relaxation method for Perron pairs of a nonnegative tensor
• Rational Generalized Nash Equilibrium Problems
• Algebraic criteria of global observability of polynomial systems
• Tensor eigenvalue complementarity problems
• Local saddle points for unconstrained polynomial optimization
• Homogenization for polynomial optimization with unbounded sets
• Optimization over trace polynomials
• Test of copositive tensors
• Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization
• State polynomials: positivity, optimization and nonlinear Bell inequalities
• A generalized flat extension theorem for moment matrices
• Convex Hulls of Algebraic Sets
• The truncated moment problem via homogenization and flat extensions
• Software for the Gale transform of fewnomial systems and a Descartes rule for fewnomials
• Positivity certificates and polynomial optimization on non-compact semialgebraic sets
• Deciding Polyhedrality of Spectrahedra
• Linear optimization with cones of moments and nonnegative polynomials
• A semidefinite programming approach for solving multiobjective linear programming
• Certifying convergence of Lasserre's hierarchy via flat truncation
• Finite convergence of moment-SOS relaxations with nonreal radical ideals
• Khovanskii-Rolle continuation for real solutions
• Design of Marx generators as a structured eigenvalue assignment
• Certifying the global optimality of quartic minimization over the sphere
• Moment matrices, border bases and real radical computation
• Generators for the \(C^m\)-closures of ideals
• A hierarchy of spectral relaxations for polynomial optimization
• Title not available (Why is that?)
• VerifyRealRoots: a Matlab package for computing verified real solutions of polynomials systems of equations and inequalities
• Distance to a constitutive tensor isotropy stratum by the Lasserre polynomial optimization method
• Border basis relaxation for polynomial optimization
• Computing real radicals and \(S\)-radicals of polynomial systems
• Moments and sums of squares for polynomial optimization and related problems
• Numerically computing real points on algebraic sets
• Real ideal and the duality of semidefinite programming for polynomial optimization
• A semidefinite approach for truncated \(K\)-moment problems
• A certificate for semidefinite relaxations in computing positive-dimensional real radical ideals
• On the computation of matrices of traces and radicals of ideals
• Lasserre Hierarchy for Large Scale Polynomial Optimization in Real and Complex Variables
• Quadratic tensor eigenvalue complementarity problems
• Convex generalized Nash equilibrium problems and polynomial optimization
• A prolongation-projection algorithm for computing the finite real variety of an ideal
• Semidefinite programming for min-max problems and games
• Tight relaxations for polynomial optimization and Lagrange multiplier expressions
• The Approach of Moments for Polynomial Equations
• A semidefinite method for tensor complementarity problems

Uses Software

• MPFI
• PHCpack
• SINGULAR
• SeDuMi
• GloptiPoly
• YALMIP
• PoSSo
• ISOLATE

This page was built for publication: Semidefinite characterization and computation of zero-dimensional real radical ideals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1029543)