Minimizing polynomials via sum of squares over the gradient ideal
From MaRDI portal
Publication:2492680
DOI10.1007/S10107-005-0672-6zbMath1134.90032arXivmath/0411342OpenAlexW2094995801MaRDI QIDQ2492680
Bernd Sturmfels, James W. Demmel, Jia-Wang Nie
Publication date: 14 June 2006
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/0411342
global optimizationpolynomialsvarietyalgebraic geometryradical idealsemidefinite programming (SDP)sum of squares (SOS)gradient ideal
Semidefinite programming (90C22) Optimality conditions and duality in mathematical programming (90C46) Semialgebraic sets and related spaces (14P10)
Related Items (74)
Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients ⋮ A tensor analogy of Yuan's theorem of the alternative and polynomial optimization with sign structure ⋮ Local saddle points for unconstrained polynomial optimization ⋮ Homogeneous polynomials and spurious local minima on the unit sphere ⋮ Stability and genericity for semi-algebraic compact programs ⋮ Nonnegative Morse polynomial functions and polynomial optimization ⋮ Sum of squares method for sensor network localization ⋮ Global uniqueness and solvability of tensor variational inequalities ⋮ Positivity certificates and polynomial optimization on non-compact semialgebraic sets ⋮ Certifying the global optimality of quartic minimization over the sphere ⋮ Minimizer Extraction in Polynomial Optimization Is Robust ⋮ Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals ⋮ On the complexity of Putinar's Positivstellensatz ⋮ Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness ⋮ Qualification Conditions in Semialgebraic Programming ⋮ An approximation bound analysis for Lasserre's relaxation in multivariate polynomial optimization ⋮ Tangencies and polynomial optimization ⋮ Homogenization for polynomial optimization with unbounded sets ⋮ A new approximation hierarchy for polynomial conic optimization ⋮ Equality-constrained minimization of polynomial functions ⋮ Sampling Algebraic Varieties for Sum of Squares Programs ⋮ Necessary global optimality conditions for nonlinear programming problems with polynomial constraints ⋮ Optimality Conditions for Minimizers at Infinity in Polynomial Programming ⋮ (Global) optimization: historical notes and recent developments ⋮ Global optimization of polynomials restricted to a smooth variety using sums of squares ⋮ Border basis relaxation for polynomial optimization ⋮ A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization ⋮ An exact Jacobian SDP relaxation for polynomial optimization ⋮ Algorithms for computing the global infimum and minimum of a polynomial function ⋮ Generic Properties for Semialgebraic Programs ⋮ Global optimality conditions for cubic minimization problems with cubic constraints ⋮ Certifying convergence of Lasserre's hierarchy via flat truncation ⋮ On the complexity of testing attainment of the optimal value in nonlinear optimization ⋮ Global minimization of multivariate polynomials using nonstandard methods ⋮ Lower bounds on the global minimum of a polynomial ⋮ A Frank-Wolfe type theorem for nondegenerate polynomial programs ⋮ DSOS and SDSOS Optimization: More Tractable Alternatives to Sum of Squares and Semidefinite Optimization ⋮ Systems of polynomials with at least one positive real zero ⋮ A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set ⋮ Discriminants and nonnegative polynomials ⋮ Semidefinite relaxations for semi-infinite polynomial programming ⋮ Global optimization of polynomials over real algebraic sets ⋮ On polynomial optimization over non-compact semi-algebraic sets ⋮ Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017 ⋮ Exploiting equalities in polynomial programming ⋮ Solving determinantal systems using homotopy techniques ⋮ Polynomial, regular and Nash images of Euclidean spaces ⋮ Proving inequalities and solving global optimization problems via simplified CAD projection ⋮ Homotopy techniques for solving sparse column support determinantal polynomial systems ⋮ Global optimality conditions and optimization methods for polynomial programming problems ⋮ An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming ⋮ Positive definiteness of paired symmetric tensors and elasticity tensors ⋮ Norm bounds and underestimators for unconstrained polynomial integer minimization ⋮ An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming ⋮ Tensor maximal correlation problems ⋮ Global minimization of rational functions and the nearest GCDs ⋮ Well-Posedness in Unconstrained Polynomial Optimization Problems ⋮ Parametric optimization and optimal control using algebraic geometry methods ⋮ A note on optimization with Morse polynomials ⋮ Complete solutions and extremality criteria to polynomial optimization problems ⋮ Symmetric ideals, Specht polynomials and solutions to symmetric systems of equations ⋮ Best Nonnegative Rank-One Approximations of Tensors ⋮ On stability and the Łojasiewicz exponent at infinity of coercive polynomials ⋮ Semi-algebraically connected components of minimum points of a polynomial function ⋮ Minimizing rational functions by exact Jacobian SDP relaxation applicable to finite singularities ⋮ Space tensor conic programming ⋮ Solving polynomial optimization problems via the truncated tangency variety and sums of squares ⋮ Complements of unbounded convex polyhedra as polynomial images of \({{\mathbb{R}}}^n\) ⋮ Tight relaxations for polynomial optimization and Lagrange multiplier expressions ⋮ Coercive Polynomials and Their Newton Polytopes ⋮ Computing critical points for invariant algebraic systems ⋮ Univariate parameterization for global optimization of mixed-integer polynomial problems ⋮ On the Catlin multitype of sums of squares domains ⋮ A dynamic inequality generation scheme for polynomial 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
- Derivations and radicals of polynomial ideals over fields of arbitrary characteristic
- Representations of positive polynomials on noncompact semialgebraic sets via KKT ideals
- Semidefinite representations for finite varieties
- Solving systems of polynomial inequalities in subexponential time
- On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
- Computation of real radicals of polynomial ideals. II
- Global minimization of a multivariate polynomial using matrix methods
- Semidefinite programming relaxations for semialgebraic problems
- There are significantly more nonnegative polynomials than sums of squares
- Global Optimization with Polynomials and the Problem of Moments
- Numerical Optimization
- Optimization of Polynomial Functions
- SOSTOOLS and Its Control Applications
- Detecting Global Optimality and Extracting Solutions in GloptiPoly
- Semidefinite Programming
- The truncated complex $K$-moment problem
- GloptiPoly
- Semidefinite Approximations for Global Unconstrained Polynomial Optimization
- Algorithms in real algebraic geometry
This page was built for publication: Minimizing polynomials via sum of squares over the gradient ideal
