On the convergence of critical points on real algebraic sets and applications to optimization

Abstract

Let $F\in \mathbb{R}[X_1,\dots ,X_n]$ and the zero set $V=\zero(\mathcal{P},\R^n)$, where $\mathcal{P}:=\{P_1,\dots ,P_s\}\subset \mathbb{R}[X_1,\dots ,X_n]$ is a finite set of polynomials. We investigate existence of critical points of $F$ on an infinitesimal perturbation $V_ξ = \zero(\{P_1-ξ_1,\ldots,P_s-ξ_s\},\R\la ξ\ra^n)$. Our main motivation is to understand the limiting behavior of local minimizers of the log-barrier function (and central paths) in polynomial optimization, whose existence plays a fundamental role, in theory and practice, for modern interior point methods. We establish different sets of conditions that ensure existence, finiteness, boundedness, and non-degeneracy of critical points of $F$ on $V_{\xi }$, respectively. These lead to new conditions for the existence, convergence, and smoothness of central paths of polynomial optimization and its extension to non-linear optimization problems involving definable sets and functions in an o-minimal structure. In particular, for non-linear programs defined by real globally analytic functions, our extension provides a stronger form of the convergence result obtained by Drummond and Peterzil.

52 Pages, 4 figures