A symbolic approach to polynomial optimization over basic closed semialgebraic sets

JERONIMO, GABRIELA

Workshop; Polyhedra, Lattices, Algebra, and Moments; 2014

Institute for Mathematics, National University of Singapore

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