A symbolic approach to polynomial optimization over basic closed semialgebraic sets

Daniel Perrucci
University of Buenos Aires

We consider the problem of computing the minimum of a polynomial function g on a basic closed semialgebraic subset S of R^n, provided that g attains a minimum value over S. Assuming that the function and the constraints are given by integer data, we will present bounds for the algebraic degree and the absolute value of the minimum of g on S under certain compactness assumptions on the subset where the minimum is attained. We will also describe a probabilistic symbolic algorithm to compute a finite set of sample points of the compact connected components of the minimizers set.

Back to Workshop II: Tools from Algebraic Geometry