Invariants, polytopes, and optimization

In this talk, I will give a gentle introduction to recent research to find efficient algorithms for natural problems in geometric invariant theory by drawing a connection to geodesically convex optimization. These algorithms minimize the norm of the moment map and test membership in moment polytopes for non-commutative group actions. As we will see, this setting captures a diverse set of problems in different areas of mathematics, computer science, and physics. Several of these were solved efficiently for the first time using optimization methods; the corresponding algorithms also lead to solutions of purely structural problems and to new connections between disparate fields.

In the spirit of standard convex optimization, we develop two general methods in the geodesic setting, a first and a second order method, which receive first and second order information, respectively, on the derivatives of the function to be optimized. We will discuss the key parameters of the underlying group actions which control the efficiency of these methods, and see how to bound these parameters in several general cases. We will end by discussing some intriguing open problems and further research directions.

Peter Bürgisser will give a follow-up talk on Tuesday on the same line of work (arXiv:1910.12375).