Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares
From MaRDI portal
Publication:5757356
Abstract: In this work, the combine the theory of generalized critical values with the theory of iterated rings of bounded elements (real holomorphy rings). We consider the problem of computing the global infimum of a real polynomial in several variables. Every global minimizer lies on the gradient variety. If the polynomial attains a minimum, it is therefore equivalent to look for the greatest lower bound on its gradient variety. Nie, Demmel and Sturmfels proved recently a theorem about the existence of sums of squares certificates for such lower bounds. Based on these certificates, they find arbitrarily tight relaxations of the original problem that can be formulated as semidefinite programs and thus be solved efficiently. We deal here with the more general case when the polynomial is bounded from belo w but does not necessarily attain a minimum. In this case, the method of Nie, Demmel and Sturmfels might yield completely wrong results. In order to overcome this problem, we replace the gradient variety by larger semialgebraic sets which we call gradient tentacles. It now gets substantially harder to prove the existence of the necessary sums of squares certificates.
Recommendations
- Minimizing polynomials via sum of squares over the gradient ideal
- Global Optimization of Polynomials Using the Truncated Tangency Variety and Sums of Squares
- Solving polynomial optimization problems via the truncated tangency variety and sums of squares
- Global optimization of polynomials restricted to a smooth variety using sums of squares
- Global optimization of polynomials using generalized critical values and sums of squares
Cited in
(44)- New approach to global minimization of normal multivariate polynomial based on tensor
- Solving polynomial optimization problems via the truncated tangency variety and sums of squares
- Convergence of the Lasserre hierarchy of SDP relaxations for convex polynomial programs without compactness
- Univariate polynomial optimization with sum-of-squares interpolants
- Positive polynomials on nondegenerate basic semi-algebraic sets
- Global optimization of polynomials over real algebraic sets
- An exact Jacobian SDP relaxation for polynomial optimization
- A note on nondegenerate matrix polynomials
- An approach to constrained polynomial optimization via nonnegative circuit polynomials and geometric programming
- Solving the equality-constrained minimization problem of polynomial functions
- Positivstellensätze for polynomial matrices
- Positivity certificates and polynomial optimization on non-compact semialgebraic sets
- Complements of unbounded convex polyhedra as polynomial images of \({{\mathbb{R}}}^n\)
- Tight relaxations for polynomial optimization and Lagrange multiplier expressions
- Curves testing boundedness of polynomials on subsets of the real plane
- New approximations for the cone of copositive matrices and its dual
- Minimizing polynomials via sum of squares over the gradient ideal
- A tensor analogy of Yuan's theorem of the alternative and polynomial optimization with sign structure
- Semidefinite programming relaxation methods for global optimization problems with sparse polynomials and unbounded semialgebraic feasible sets
- Stability and genericity for semi-algebraic compact programs
- Sum of squares and the Łojasiewicz exponent at infinity
- Global optimization of polynomials using generalized critical values and sums of squares
- Practical and Theoretical Issues for the Computation of Generalized Critical Values of a Polynomial Mapping
- Global Optimization of Polynomials Using the Truncated Tangency Variety and Sums of Squares
- An effective implementation of symbolic-numeric cylindrical algebraic decomposition for quantifier elimination
- Algebra of bounded polynomials on a set Zariski closed at infinity cannot be finitely generated
- Global optimization of polynomials restricted to a smooth variety using sums of squares
- Minimizer Extraction in Polynomial Optimization Is Robust
- A note on optimization with Morse polynomials
- Sampling algebraic varieties for sum of squares programs
- Polynomial, regular and Nash images of Euclidean spaces
- A Frank-Wolfe type theorem for nondegenerate polynomial programs
- A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
- On polynomial optimization over non-compact semi-algebraic sets
- Some positivstellensätze for polynomial matrices
- Systems of polynomials with at least one positive real zero
- On stability and the Łojasiewicz exponent at infinity of coercive polynomials.
- Generic properties for semialgebraic programs
- Coercive Polynomials and Their Newton Polytopes
- Well-posedness in unconstrained polynomial optimization problems
- Homogenization for polynomial optimization with unbounded sets
- Representation of positive polynomials on a generalized strip and its application to polynomial optimization
- Sparse polynomial optimization with unbounded sets
- Minimizing rational functions by exact Jacobian SDP relaxation applicable to finite singularities
This page was built for publication: Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5757356)
