A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set

DOI10.1007/s00454-014-9619-0zbMath1328.90138arXiv1304.5558OpenAlexW1973602807MaRDI QIDQ464735

Gabriela Jeronimo, Daniel Perrucci

Publication date: 29 October 2014

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

complexitypolynomial optimizationdeformation techniques

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Abstract computational complexity for mathematical programming problems (90C60) Nonlinear programming (90C30) Semialgebraic sets and related spaces (14P10) Software, source code, etc. for problems pertaining to algebraic geometry (14-04) Computational aspects in algebraic geometry (14Q99)

Related Items (5)

Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization ⋮ Solving determinantal systems using homotopy techniques ⋮ Homotopy techniques for solving sparse column support determinantal polynomial systems ⋮ Intrinsic complexity estimates in polynomial optimization ⋮ Computing critical points for invariant algebraic systems

Uses Software

• Kronecker
• RAGlib

Cites Work

• 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
• Linear solving for sign determination
• On computing the determinant in small parallel time using a small number of processors
• On sign conditions over real multivariate polynomials
• Deformation techniques for sparse systems
• The complexity of partial derivatives
• Semidefinite programming relaxations for semialgebraic problems
• Deformation techniques for efficient polynomial equation solving.
• On the minimum of a positive polynomial over the standard simplex
• Minimizing polynomials via sum of squares over the gradient ideal
• Global Optimization with Polynomials and the Problem of Moments
• Global optimization of polynomials using generalized critical values and sums of squares
• The DMM bound
• Improved Algorithms for Sign Determination and Existential Quantifier Elimination
• Deciding reachability of the infimum of a multivariate polynomial
• On the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set and Applications
• Computing the global optimum of a multivariate polynomial over the reals
• Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares
• Algorithms in real algebraic geometry
• A Gröbner free alternative for polynomial system solving

This page was built for publication: A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set