A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
From MaRDI portal
Publication:464735
Software, source code, etc. for problems pertaining to algebraic geometry (14-04) Semialgebraic sets and related spaces (14P10) Computational aspects in algebraic geometry (14Q99) Symbolic computation and algebraic computation (68W30) Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60)
Abstract: We consider the problem of computing the minimum of a polynomial function g on a basic closed semialgebraic set E in R^n. We present a probabilistic symbolic algorithm to find a finite set of sample points of the subset E^{min} of E where the minimum of g is attained, provided that E^{min} is non-empty and has at least one compact connected component.
Recommendations
- On the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set and Applications
- Semi-algebraically connected components of minimum points of a polynomial function
- Algorithms for computing the global infimum and minimum of a polynomial function
- Global minimization of a multivariate polynomial using matrix methods
- Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set
Cites work
- A Gröbner free alternative for polynomial system solving
- Algorithms in real algebraic geometry
- Computing the global optimum of a multivariate polynomial over the reals
- Deciding reachability of the infimum of a multivariate polynomial
- Deformation techniques for efficient polynomial equation solving.
- Deformation techniques for sparse systems
- 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
- Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares
- Global optimization with polynomials and the problem of moments
- scientific article; zbMATH DE number 3759547 (Why is no real title available?)
- scientific article; zbMATH DE number 51690 (Why is no real title available?)
- scientific article; zbMATH DE number 3563286 (Why is no real title available?)
- scientific article; zbMATH DE number 976329 (Why is no real title available?)
- scientific article; zbMATH DE number 1984325 (Why is no real title available?)
- Improved Algorithms for Sign Determination and Existential Quantifier Elimination
- Linear solving for sign determination
- Minimizing polynomials via sum of squares over the gradient ideal
- Modern computer algebra
- On computing the determinant in small parallel time using a small number of processors
- On sign conditions over real multivariate polynomials
- On the Minimum of a Polynomial Function on a Basic Closed Semialgebraic Set and Applications
- On the minimum of a positive polynomial over the standard simplex
- Semidefinite programming relaxations for semialgebraic problems
- The complexity of partial derivatives
- The DMM bound: multivariate (aggregate) separation bounds
Cited in
(6)- Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
- Homotopy techniques for solving sparse column support determinantal polynomial systems
- Computing critical points for invariant algebraic systems
- Solving determinantal systems using homotopy techniques
- Intrinsic complexity estimates in polynomial optimization
- Semi-algebraically connected components of minimum points of a polynomial function
This page was built for publication: A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q464735)
