Global Optimization of Analytic Functions over Compact Domains

Algebra Seminar
Monday, September 18, 2023 - 1:00pm for 1 hour (actually 50 minutes)
Skiles 006
Georgy Scholten РSorbonne Université
Changxin Ding

Please Note: There will be a pre-seminar (aimed toward grad students and postdocs) from 11:00 am-11:30 am in Skiles 006.

In this talk, 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 in L-infty norm. The critical points of the polynomial approximant are computed exactly, using methods from computer algebra. 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 the lowest degree possible least-squares polynomial approximants of $f$ which attains a desired precision over the domain. We then compute the critical points of the approximant and 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.