Peter Bürgisser April 1-3, 2025
TU-Berlin - https://en.wikipedia.org/wiki/Peter_B%C3%BCrgisser
"Optimization, Invariants, and Complexity"
In recent years, a theory of optimization for geodesically convex optimization problems on Riemannian manifolds has been developed that is adjusted to situations with high symmetries arising from the action of a typically non-commutative algebraic group. These algorithms minimize the moment map (a version of the gradient) and test membership to null cones and moment polytopes (a vast class of polytopes, typically of exponential vertex and facet complexity, which arise from this a priori non-convex, non-linear setting). If the acting groups is commutative (and connected), one retrieves the classical setting of geometric programming.
In the spirit of standard convex optimization, a general first order and a second order method has been developed. The main technical work goes into identifying the key parameters of the underlying group actions, which control convergence to the optimum in each of these methods. The analysis of these analogues of smoothness parameters relies on from tools from invariant theory.
The general setting captures a diverse set of problems in different areas of computer science, mathematics, and physics. Several of them were solved efficiently for the first time using such methods; the corresponding algorithms also led to solutions of purely structural problems and to many new connections between disparate fields. There are intriguing open problems that suggest further research directions.
The purpose of the course is to provide an introduction to this new body of work.