A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
From MaRDI portal
Publication:464735
Symbolic computation and algebraic computation (68W30) Nonlinear programming (90C30) Abstract computational complexity for mathematical programming problems (90C60) Computational aspects in algebraic geometry (14Q99) Semialgebraic sets and related spaces (14P10) Software, source code, etc. for problems pertaining to algebraic geometry (14-04)
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
- 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?)
- 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 Using Gradient Tentacles 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
- Global optimization with polynomials and the problem of moments
- 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 DMM bound: multivariate (aggregate) separation bounds
- The complexity of partial derivatives
Cited in
(6)- Semi-algebraically connected components of minimum points of a polynomial function
- Computing critical points for invariant algebraic systems
- Homotopy techniques for solving sparse column support determinantal polynomial systems
- Solving determinantal systems using homotopy techniques
- Intrinsic complexity estimates in polynomial optimization
- Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
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)
