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

The algorithm FindingMinimum is elaborated in order to find at least one point of a closed semi-algebraic subset of \(\mathbb{R}^{n}\), in which a given polynomial function attains a minimum value. The set of all minimum points is supposed to have at least one compact connected component. The probabilistic symbolic algorithm FindingMinimum is based on the deformation techniques, overcoming the difficulties that arise in the Lagrange multipliers method and in other known techniques. The main subroutines of this algorithm are descriptively named as: GeometricResolution, MinimumInGeometricResolution, ComparingMinima. Their complexity bounds are estimated, which leads to results on the complexity bounds of the whole algorithm.