Section: Overall Objectives

Scientific context

Tropical algebra, geometry, and analysis have enjoyed spectacular development in recent years. Tropical structures initially arose to solve problems in performance evaluation of discrete event systems  [62], combinatorial optimization  [67], or automata theory  [117]. They also arose in mathematical physics and asymptotic analysis  [107], [104]. More recently, these structures have appeared in several areas of pure mathematics, in particular in the study of combinatorial aspects of algebraic geometry  [96], [131], [120], [101], in algebraic combinatorics  [88], and in arithmetics  [73]. Also, further applications of tropical methods have appeared, including optimal control  [111], program invariant computation  [57] and timed systems verification  [106], and zero-sum games [2].

The term `tropical' generally refers to algebraic structures in which the laws originate from optimization processes. The prototypical tropical structure is the max-plus semifield, consisting of the real numbers, equipped with the maximum, thought of as an additive law, and the addition, thought of as a multiplicative law. Tropical objects appear as limits of classical objects along certain deformations (“log-limits sets” of Bergman, “Maslov dequantization”, or “Viro deformation”). For this reason, the introduction of tropical tools often yields new insights into old familiar problems, leading either to counterexamples or to new methods and results; see for instance  [131], [113]. In some applications, like optimal control, discrete event systems, or static analysis of programs, tropical objects do not appear through a limit procedure, but more directly as a modelling or computation/analysis tool; see for instance  [127], [62], [99], [68].

Tropical methods are linked to the fields of positive systems and of metric geometry  [115], [11]. Indeed, tropically linear maps are monotone (a.k.a. order-preserving). They are also nonexpansive in certain natural metrics (sup-norm, Hopf oscillation, Hilbert's projective metric, ...). In this way, tropical dynamical systems appear to be special cases of nonexpansive, positive, or monotone dynamical systems, which are studied as part of linear and non-linear Perron-Frobenius theory  [105], [3]. Such dynamical systems are of fundamental importance in the study of repeated games  [112]. Monotonicity properties are also essential in the understanding of the fixed points problems which determine program invariants by abstract interpretation  [75]. The latter problems are actually somehow similar to the ones arising in the study of zero-sum games; see [7]. Moreover, positivity or monotonicity methods are useful in population dynamics, either in a discrete space setting  [129] or in a PDE setting  [63]. In such cases, solving tropical problems often leads to solutions or combinatorial insights on classical problems involving positivity conditions (e.g., finding equilibria of dynamical systems with nonnegative coordinates, understanding the qualitative and quantitative behavior of growth rates / Floquet eigenvalues [9], etc). Other applications of Perron-Frobenius theory originate from quantum information and control  [119], [125].