Program of the lecture
Max-plus Algebra: an algebra for optimization
in the Master Oficial de Postgrado en Multimedia y Comunicaciones, at the Departamento de Teoría de Señal y Comunicaciones, Universidad Carlos III de Madrid

Stéphane Gaubert*

February 11-15, 2008

Abstract: The goal of this lecture is to present basic results of maxplus or tropical algebra, and to illustrate them by applications from Discrete Event Systems, Optimization, Markov decision, and Game Theory. Some advanced topics (research level) will be discussed.

The lecture is organized in 10 slots of 2 hours each. These slots will include exercises.

The symbol below indicates advanced topics, which may be further developed in the final lecture.

Online materials concerning this lecture can be found on
http://www.cmap.polytechnique.fr/~gaubert/MADRIDCOURSE

Dpto. Teoría de Señal y Comunicaciones, Univ. Carlos III de Madrid, Avda. de la Universidad, 30. Leganés 28911.

Schedule: 15:00-16:50, break, 17:10-19:00


Figure : Two max-plus convex sets and their separating half-spaces, illustration from [GS07]

Lesson 1: Introduction to maxplus algebra

Several problems in which maxplus linearity appears: deterministic optimal control, performance evaluation (manufacturing systems, transportation networks), asymptotic analysis. The maxplus semiring and other tropical semirings. Exercises: first computations. Numerical polynomials versus formal polynomials, and their relation with the Legendre-Fenchel transform.

References of the lesson:  [GP97], [ABG06], [BCOQ92], [RGST05], [CGQ99].

Lesson 2: Matrices and semirings

Correspondence between graphs and matrices: the “transfer matrix theorem”. Max-plus permanents, their relation with the optimal assignment problem. Proving automatically combinatorial identities in semirings, like the Cayley-Hamilton theorem. Complete semirings. The fixed point equation x=Ax+b and the Kleene star.

Lesson 3: The maxplus eigenproblem

Definition: algebraic eigenvalues (roots of the max-plus characteristic polynomials) versus geometric eigenvalues (solutions of the eigenproblem). Irreducible matrices. Looking at Perron-Frobenius theory with logarithmic glasses to interpret max-plus spectral theory. The maximal circuit mean formula for the maximal eigenvalue. Minimal generating family of the eigenspace. Illustration: performance analysis of max-plus linear dynamical system (timed event graphs, heaps of pieces), deterministic decision processes.

References of the lesson: [ABG06], [BCOQ92], [Gau99, Chap. 4], [AGW05].

Lesson 4: The maxplus eigenproblem (continued)

Cyclicity theorem for powers of matrices. Turnpike theorem. Case of reducible matrices. Karp's formula for the cycle time vector. Inequalities relating classical eigenvalues and max-plus eigenvalues (Kingman, Friedland,…). An overview of infinite dimensional extensions (denumerable case, Lax-Oleinik semigroups).

References of the lesson [ABG06], [BCOQ92], [Gau99, Chap. 4], [AGW05].

Lesson 5: Max-plus linear spaces

The equation Ax=b. Some elements of residuation theory (lattice theoretical Galois connection). Vorobyev-Zimmermann's combinatorial characterization of the existence and uniqueness of the solution in terms of coverings. Max-plus non-linear projectors on linear-spaces. Examples of infinite dimensional max-plus linear spaces: Lipschitz functions, convex functions, semiconvex functions.

References of the lesson:  [But03],  [LMS01],  [CGQ04].

Lesson 6: Max-plus convexity

Separating maxplus convex sets. Geometry of separating half-spaces and Hilbert's projective metric. Max-plus analogues of the theorems of Caratéodory, Minkowski, Helly. Cyclic projection algorithm. Max-plus polyedra. From equations to generators and vice versa. Duality between linear spaces and congruences.

References of the lesson:  [CGQ04],  [DS04], [GK06], [GS07].

Lesson 7: Duality between probability and optimization

Measures over idempotent semirings. The formalism of “decision variables”. Duality between probability and optimization. Essentially all the idempotent measures have a density (Kolokoltsov, Akian). Algebra of quadratic forms. A limit theorem for sum of decision variables (Quadrat).

References of the lesson:  [Aki99],  [AQV98].

Lesson 8: Min-max functions and beyond

Beyond max-plus linear maps: order preserving maps arising as dynamic programming operators of stochastic control and game problems. The class of min-max functions (Olsder, Gunawardena). Elements of non-linear Perron-Frobenius theory. Existence of non-linear eigenvectors. Invariant half-lines and asymptotic behaviour. Collatz-Wielandt type formula.

Reference of the lesson: [GG04], [GG98].

Lesson 9: Policy iteration algorithms

Classical (one player) policy iteration algorithms. Bi-level policy iteration of two player discounted problems. Generalization to ergodic problems by means of max-plus spectral theory.

Reference of the lesson: [DG06], [CTG06].

Slides available on line: From max-plus algebra to non-linear Perron-Frobenius theory, plenary conference at CODE 2007, IHP, Paris, 18-20. (Correspond to Lessons 8 and 9).

Lesson 10: Some current topics of research

Max-plus finite element methods and the method of Fleming-McEneaney to solve Hamilton-Jacobi equations. Max-plus approximation of functions. Eigenvalue perturbation theory, problems in maxplus linear algebra (von Neumann regularity, rank, congruences). Max-plus spectral theory over a noncompact state space and horoboundary compactification.

References

[ABG06]
M. Akian, R. Bapat, and S. Gaubert. Max-plus algebras. In L. Hogben, editor, Handbook of Linear Algebra (Discrete Mathematics and Its Applications), volume 39. Chapman & Hall/CRC, 2006. Chapter 25, Electronic preprint available on the author's web page.
[AG03]
M. Akian and S. Gaubert. Spectral theorem for convex monotone homogeneous maps, and ergodic control. Nonlinear Analysis. Theory, Methods & Applications, 52(2):637–679, 2003. arXiv:math.SP/0110108.
[AGL06]
M. Akian, S. Gaubert, and A. Lakhoua. The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis. SIAM J. Control and Opt., 2006. To appear, arXiv:math.OC/0603619.
[AGW05]
M. Akian, S. Gaubert, and C. Walsh. Discrete max-plus spectral theory. In G. L. Litvinov and V. P. Maslov, editors, Idempotent Mathematics and Mathematical Physics, Contemporary Mathematics, pages 19–51. American Mathematical Society, 2005. arXiv:math/0405225.
[Aki99]
M. Akian. Densities of idempotent measures and large deviations. Transactions of the American Mathematical Society, 351(11):4515–4543, 1999. hal-inria.
[AQV98]
M. Akian, Jean-Pierre Quadrat, and M. Viot. Duality between probability and optimization. In J. Gunawardena, editor, Idempotency, Publications of the Isaac Newton Institute. Cambridge University Press, 1998. [pdf].
[BCOQ92]
F. Baccelli, G. Cohen, G.-J. Olsder, and Jean-Pierre Quadrat. Synchronization and linearity : an algebra for discrete events systems. Wiley, New-York, 1992. book on line.
[But03]
P. Butkovic. Max-algebra: the linear algebra of combinatorics? Linear Algebra and Its Applications, 367:313–335, 2003. Article available on the author's web page.
[CGQ99]
G. Cohen, S. Gaubert, and J.P. Quadrat. Max-plus algebra and system theory: where we are and where to go now. Annual Reviews in Control, 23:207–219, 1999. Preprint available on line, Eprint doi:10.1016/S1367-5788(99)90091-3.
[CGQ04]
Guy Cohen, Stéphane Gaubert, and Jean-Pierre Quadrat. Duality and separation theorems in idempotent semimodules. Linear Algebra and Appl., 379:395–422, 2004. arXiv:math/0212294.
[CT80]
M. G. Crandall and L. Tartar. Some relations between non expansive and order preserving maps. Proceedings of the AMS, 78(3):385–390, 1980.
[CTG06]
J. Cochet-Terrasson and S. Gaubert. A policy iteration algorithm for zero-sum stochastic games with mean payoff. C. R. Math. Acad. Sci. Paris, 343(5):377–382, 2006. Eprint hal/inria-inria-00144146, Eprint doi:10.1016/j.crma.2006.07.011.
[CTGG99]
J. Cochet-Terrasson, S. Gaubert, and J. Gunawardena. A constructive fixed point theorem for min-max functions. Dynamics and Stability of Systems, 14(4):407–433, 1999. Electronic preprint available on the author's web page.
[DG06]
Vishesh Dhingra and Stéphane Gaubert. How to solve large scale deterministic games with mean payoff by policy iteration. In Valuetools '06: Proceedings of the 1st international conference on Performance evaluation methodologies and tools, page 12, New York, NY, USA, 2006. ACM Press. Paper available on line, Eprint doi:10.1145/1190095.1190110.
[DS04]
M. Develin and B. Sturmfels. Tropical convexity. Doc. Math., 9:1–27 (electronic), 2004. On line journal article, arXiv:math.MG/0308254, Erratum.
[Gau99]
S. Gaubert. Introduction aux systèmes dynamiques à événements discrets. Notes de cours, ENSMP, Option Automatique et M2 ATSI, Université d'Orsay, 1999. Notes disponibles en ligne.
[GG98]
S. Gaubert and J. Gunawardena. A non-linear hierarchy for discrete event dynamical systems. In Proc. of the Fourth Workshop on Discrete Event Systems (WODES98), Cagliari, Italy, 1998. IEE.
[GG04]
S. Gaubert and J. Gunawardena. The Perron-Frobenius theorem for homogeneous, monotone functions. Trans. of AMS, 356(12):4931–4950, 2004. PII: S 0002-9947(04)03470-1, arXiv:math.FA/0105091.
[GK06]
S. Gaubert and R. Katz. The Minkowski theorem for max-plus convex sets. Linear Algebra and Appl., 421:356–369, 2006. arXiv:math.GM/0605078, Eprint doi:10.1016/j.laa.2006.09.019.
[GP97]
S. Gaubert and M. Plus. Methods and applications of (max,+) linear algebra. In R. Reischuk and M. Morvan, editors, STACS'97, number 1200 in LNCS, pages 261–282, Lübeck, March 1997. Springer. Eprint doi:10.1007/BFb0023465, INRIA RR-3088.
[GS07]
S. Gaubert and S. Sergeev. Cyclic projectors and separation theorems in idempotent convex geometry. Fundamentalnaya i prikladnaya matematika, 13(4):33–52, 2007. arXiv:0706.3347.
[KM97]
V. N. Kolokoltsov and V. P. Maslov. Idempotent analysis and applications. Kluwer Acad. Publisher, 1997.
[LMS01]
G.L. Litvinov, V.P. Maslov, and G.B. Shpiz. Idempotent functional analysis: an algebraical approach. Math. Notes, 69(5):696–729, 2001. arXiv:math.FA/0009128.
[MPN02]
J. Mallet-Paret and Roger Nussbaum. Eigenvalues for a class of homogeneous cone maps arising from max-plus operators. Discrete and Continuous Dynamical Systems, 8(3):519–562, July 2002.
[MS92]
V. P. Maslov and S. N. Samborskiĭ. Idempotent analysis, volume 13 of Advances In Soviet Mathematics. Amer. Math. Soc., Providence, 1992.
[Nus88]
Roger D. Nussbaum. Hilbert's projective metric and iterated nonlinear maps. Memoirs of the AMS, 75(391), 1988.
[RGST05]
Jürgen Richter-Gebert, Bernd Sturmfels, and Thorsten Theobald. First steps in tropical geometry. In G. L. Litvinov and V. P. Maslov, editors, Idempotent Mathematics and Mathematical Physics, Contemporary Mathematics. American Mathematical Society, 2005. arXiv:math/0306366.
[Vir01]
Oleg Viro. Dequantization of real algebraic geometry on logarithmic paper. In European Congress of Mathematics, Vol. I (Barcelona, 2000), volume 201 of Progr. Math., pages 135–146. Birkhäuser, Basel, 2001. arXiv:math/0005163.

*
INRIA and CMAP, École Polytechnique, 91128 Palaiseau Cédex, Stephane.Gaubert@inria.fr,
http://www.cmap.polytechnique.fr/~gaubert

This document was translated from LATEX by HEVEA.