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

DOI10.1007/S00454-014-9619-0zbMATH Open1328.90138arXiv1304.5558OpenAlexW1973602807MaRDI QIDQ464735FDOQ464735

Authors: Gabriela Jeronimo, Daniel Perrucci 

Publication date: 29 October 2014

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

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.

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

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

zbMATH Keywords

polynomial optimizationcomplexitydeformation techniques

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• Global optimization with polynomials and the problem of moments
• The complexity of partial derivatives
• Semidefinite programming relaxations for semialgebraic problems
• Minimizing polynomials via sum of squares over the gradient ideal
• Title not available (Why is that?)
• Algorithms in real algebraic geometry
• Global Optimization of Polynomials Using Gradient Tentacles and Sums of Squares
• A Gröbner free alternative for polynomial system solving
• On computing the determinant in small parallel time using a small number of processors
• Title not available (Why is that?)
• Modern computer algebra
• Title not available (Why is that?)
• Global optimization of polynomials using generalized critical values and sums of squares
• Computing the global optimum of a multivariate polynomial over the reals
• Global optimization of polynomials restricted to a smooth variety using sums of squares
• Deformation techniques for sparse systems
• Deformation techniques for efficient polynomial equation solving.
• The DMM bound: multivariate (aggregate) separation bounds
• Title not available (Why is that?)
• On the minimum of a positive polynomial over the standard simplex
• 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
• Linear solving for sign determination
• On sign conditions over real multivariate polynomials

Cited In (6)

• Solving determinantal systems using homotopy techniques
• Bit complexity for multi-homogeneous polynomial system solving -- application to polynomial minimization
• Computing critical points for invariant algebraic systems
• Semi-algebraically connected components of minimum points of a polynomial function
• Intrinsic complexity estimates in polynomial optimization
• Homotopy techniques for solving sparse column support determinantal polynomial systems

Uses Software

• Kronecker
• RAGlib

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)