Abstract
Critical point methods are at the core of the interplay between polynomial optimization and polynomial system solving over the reals. These methods are used in algorithms for solving various problems such as deciding the existence of real solutions of polynomial systems, performing one-block real quantifier elimination, answering connectivity queries in semi-algebraic sets, etc.
The input consists of $s$ polynomials in $n$ variables of degree at most $D$. Usually, the complexity of the algorithms is $(s\, D)^{O(n^\alpha)}$ where $\alpha$ is a constant. In the past decade, tremendous efforts have been deployed to improve the exponents in the complexity bounds. This led to efficient implementations and new geometric procedures for solving polynomial systems over the reals that exploit properties of critical points and the so-called polar varieties.
In the first part of this talk, we present an overview of these techniques and their impact on practical algorithms. In the second part, we show how we can exploit algebraic and geometric properties of polar varieties to improve roadmap algorithms for deciding connectivity queries. In particular, we present an algorithm, obtained with E. Schost, that computes roadmaps in smooth bounded real algebraic sets in time which is essentially $O( (s\, D)^{6(n\log(n))})$. This complexity is subquadratic in the output size and a first implementation shows that it can already solve problems that are out of reach of previous approaches.