Reading Seminar on Tropical Geometry and Optimization

Time: Wednesdays, 1:30 - 3:30pm during May and June

Organizers: Faye Pasley and Cynthia Vinzant

Description: Tropical geometry is the study of algebra over the max-plus semi-ring on the real numbers. This can be interpreted as the study of the behavior of exponents of an infinitesimal number added to the real numbers. Tropical geometry provides a powerful tool for constructing examples of real objects with extremal properties and interesting connections between discrete and continuous objects.

Recently there have been several important connections made between tropical versions of problems in optimization (especially linear and semi-definite programming) and combinatorial optimization problems in game theory. This will be an informal reading seminar working through some of this recent progress. We will start with a (very condensed) introduction to tropical geometry and convex optimization.

To be on the mailing list for this seminar, please contact Faye Pasley.

Schedule:
05/18 (SAS 2102) Seth Sullivant: Tropical linear programming and mean payoff games
05/22 (SAS 4102) Dan Bernstein: The tropical simplex method
06/01 (SAS 4102) Faye Pasley: Tropical semidefinite programming and stochastic mean payoff games (Part 1)
06/08 (SAS 4102) Georgy Scholten: Tropical semidefinite programming and stochastic mean payoff games (Part 2)
06/15 (SAS 4102) Mike Weselcouch: Tropical interior point methods for linear programming
06/22 (SAS 4102) Everyone: Open Problem Session
06/29 (SAS 4102) Cynthia Vinzant: Tropical hyperbolic polynomials
07/06 (SAS 4102) Faye Pasley: Tropicalization of convex duality

Potential Reading List:

  • Combinatorial simplex algorithms can solve mean payoff games, by Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig
  • Long and winding central paths, by Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, Michael Joswig
  • Solving generic nonarchimedean semidefinite programs using stochastic game algorithms, by Xavier Allamigeon, Stéphane Gaubert, Mateusz Skomra
  • Linear programs and convex hulls over fields of Puiseux fractions, by Michael Joswig, Georg Loho, Benjamin Lorenz, Benjamin Schröter
  • Tropical optimization problems, by Nikolai Krivulin
  • Horn's Problem, Vinnikov Curves and the Hive Cone, by David Speyer
  • Tropicalizing the positive semidefinite cone, by Josephine Yu
  • Other suggestions are welcome.