On the computation of asymptotic critical values of polynomial maps and applications

Let $\mathbf{f} = \left(f_1, \dots, f_p\right) $ be a polynomial tuple in $\mathbb{Q}[z_1, \dots, z_n]$ and let $d = \max_{1 \leq i \leq p} \deg f_i$. We consider the problem of computing the set of asymptotic critical values of the polynomial mapping, with the assumption that this mapping is dominant, $\mathbf{f}: z \in \mathbb{K}^n \to (f\_1(z), \dots, f\_p(z)) \in \mathbb{K}^p$ where $\mathbb{K}$ is either $\mathbb{R}$ or $\mathbb{C}$. This is the set of values $c$ in the target space of $\mathbf{f}$ such that there exists a sequence of points $(\mathbf{x}_i)_{i\in \mathbb{N}}$ for which $\mathbf{f}(\mathbf{x}_i)$ tends to $c$ and $\|\mathbf{x}_i\| \kappa {\rm d} \mathbf{f}(\mathbf{x}_i))$ tends to $0$ when $i$ tends to infinity where ${\rm d} \mathbf{f}$ is the differential of $\mathbf{f}$ and $\kappa$ is a function measuring the distance of a linear operator to the set of singular linear operators from $\mathbb{K}^n$ to $\mathbb{K}^p$. Computing the union of the classical and asymptotic critical values allows one to put into practice generalisations of Ehresmann's fibration theorem. This leads to natural and efficient applications in polynomial optimisation and computational real algebraic geometry. Going back to previous works by Kurdyka, Orro and Simon, we design new algorithms to compute asymptotic critical values. Through randomisation, we introduce new geometric characterisations of asymptotic critical values. This allows us to dramatically reduce the complexity of computing such values to a cost that is essentially $O(d^{2n(p+1)})$ arithmetic operations in $\mathbb{Q}$. We also obtain tighter degree bounds on a hypersurface containing the asymptotic critical values, showing that the degree is at most $p^{n-p+1}(d-1)^{n-p}(d+1)^{p}$. Next, we show how to apply these algorithms to unconstrained polynomial optimisation problems and the problem of computing sample points per connected component of a semi-algebraic set defined by a single inequality/inequation. We report on the practical capabilities of our implementation of this algorithm. It shows how the practical efficiency surpasses the current state-of-the-art algorithms for computing asymptotic critical values by tackling examples that were previously out of reach.