Global optimization of analytic functions over compact domain

Georgy Scholten, Sorbonne Université
-
CMU B-006

We introduce a new method for minimizing analytic Morse functions over compact domains through the use of polynomial approximations. This is, in essence, an effective application of the Stone-Weierstrass Theorem, as we seek to extend a local method to a global setting, through the construction of polynomial approximants satisfying an arbitrary set precision. Our main Theorem states probabilistic conditions for capturing all local minima of the objective function \$f\$ over the compact domain. We present a probabilistic method, iterative on the degree, to construct a lowest degree possible least-squares polynomial approximants of \$f\$ which attains a desired precision over the domain. The critical points of the polynomial approximant are computed exactly, using methods from computer algebra. We then initialize local minimization methods on the objective function \$f\$ at these points, in order to recover the totality of the local minima of \$f\$ over the domain.