Optimization, Complexity and Invariant Theory

Abstract: We will give a gentle introduction to geometric invariant theory, which provides geometric and analytic tools to study problems in invariant theory. We will explain the basic tools and concepts and give many motivating examples. In the first lecture, we will introduce moment maps and discuss the Hilbert-Mumford criterion and the Kempf-Ness theorem, which provide an intriguing extension of linear programming duality (or Farkas’ lemma) to non-commutative group actions. In the second lecture, we will continue our gentle introduction. We will discuss some of the underlying geometry and introduce the associated moment polytopes. These are a rich class of convex polytopes that arise naturally in a variety of applications, such as the Newton polytopes of polynomials, eigenvalue problems in linear algebra, and the study of entanglement in quantum information theory, giving rise to many interesting computational problems.