A symbolic approach to polynomial optimization over basic closed semialgebraic sets

GABRIELA JERONIMO; DANIEL PERRUCCI; ELIAS TSIGARIDAS

Los Angeles

Workshop; Tools from Algebraic Geometry; 2014

Institute for Pure and Applied Mathematics

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.