Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set

Let $f, f_1, \ldots, f_{s}$ be $n$-variate polynomials with rational coefficients of maximum degree $D$ and let $V$ be the set of common complex solutions of $\mathbf{F}=(f_1,\ldots, f_{s})$. We give an algorithm which, up to some regularity assumptions on $\mathbf{F}$, computes an exact representation of the global infimum $f^\star$ of the restriction of the map $x\to f(x)$ to ${V\cap\mathbb{R}^n}$, i.e., a univariate polynomial vanishing at $f^\star$ and an isolating interval for $f^\star$. Furthermore, it decides whether $f^\star$ is reached, and if so, it returns $x^\star\in V\cap\mathbb{R}^n$ such that $f(x^\star)=f^\star$. This algorithm is probabilistic. It makes use of the notion of polar varieties. Its complexity is essentially cubic in $(s D)^n$ and linear in the complexity of evaluating the input. This fits within the best known deterministic complexity class $D^{O(n)}$. We report on some practical experiments of a first implementation that is available as a Maple package. It appears that it ca...