Tropical Geometry: Algorithmic Applications in Optimization, Phylogenetics, and Deep Learning

Tropical geometry is algebraic geometry over the tropical semiring, where addition is replaced by maximum (or minimum) and multiplication by ordinary addition. The name “tropical” honors the Brazilian mathematician Imre Simon, who pioneered the algebraic theory, and reflects the fact that the field’s early development happened in Brazil. But the ideas are universal: the max-plus semiring models the longest path in a DAG; the min-plus semiring models the shortest path in a weighted graph; and the tropicalization of a polynomial system transforms nonlinear algebraic equations into piecewise-linear combinatorial problems. This transformation—from polynomial to piecewise-linear, from continuous to discrete—is the core of tropical geometry and the reason for its deep connections to computer science.

This post develops tropical geometry from first principles: the tropical semiring, tropical curves as limits of amoebas, tropical linear algebra (the Kleene star and the all-pairs shortest path problem), tropical convexity, and the recent applications to deep neural networks (where ReLU activation is precisely a tropical rational function). Along the way, we’ll see that the simplex algorithm, the Viterbi algorithm, and the forward pass of a ReLU network are all instances of the same tropical algebraic structure.

1. The Tropical Semiring

Definition 1.1. The tropical semiring (min-plus algebra) is (\mathbb{T} = (\mathbb{R} \cup {\infty}, \oplus, \odot)) where:

[ a \oplus b = \min(a, b), \quad a \odot b = a + b ]

The additive identity is (\infty) (since (\min(a, \infty) = a)), and the multiplicative identity is (0) (since (a + 0 = a)). The max-plus version uses (\max) instead of (\min), with additive identity (-\infty). Both are isomorphic via negation.

The tropical semiring is indeed a semiring: addition is associative, commutative, and has an identity; multiplication is associative, commutative, and distributes over addition: (a \odot (b \oplus c) = a + \min(b, c) = \min(a+b, a+c) = (a \odot b) \oplus (a \odot c)). However, addition is not invertible (no additive inverses), so (\mathbb{T}) is a semiring, not a ring.

1.1 Tropical Polynomials

A tropical polynomial in (n) variables is a finite tropical sum of monomials:

[ f(x_1, \ldots, x_n) = \bigoplus_{(i_1, \ldots, i_n) \in A} c_{i_1,\ldots,i_n} \odot x_1^{\odot i_1} \odot \cdots \odot x_n^{\odot i_n} ]

where (A \subset \mathbb{N}^n) is a finite set of exponent vectors. In ordinary notation:

[ f(x_1, \ldots, x_n) = \min_{(i_1, \ldots, i_n) \in A} \left(c_{i_1,\ldots,i_n} + \sum_{j=1}^n i_j x_j\right) ]

Thus, every tropical polynomial is a minimum of affine functions—a concave, piecewise-linear function. The tropical hypersurface (V_{\text{trop}}(f)) is the set of points where the minimum is attained by at least two terms (the “crease” of the piecewise-linear function). These are the analogues of algebraic varieties in the tropical world.

Tropical polynomial: f(x) = min(2x + 1, x + 3, 0x + 7)

     |
  15 +          /
     |         /
  10 +   -----/-----
     |   /    |
   5 +  /     |
     | /      |
   0 +--------+--------
     0    1    2    3    x

Tropical hypersurface: {x = 2, x = 4} (the breakpoints)

2. Tropical Linear Algebra and the Shortest Path Problem

Tropical matrix multiplication is defined naturally:

[ (A \otimes B){ij} = \bigoplus_k A{ik} \odot B_{kj} = \min_k (A_{ik} + B_{kj}) ]

This is exactly the dynamic programming recurrence for shortest paths! Let (W) be the weighted adjacency matrix of a directed graph ((W_{ij} = \text{weight of edge } i \to j), with (\infty) for absent edges). Then:

[ W^{\otimes k}_{ij} = \text{length of the shortest path from } i \text{ to } j \text{ with at most } k \text{ edges} ]

2.1 The All-Pairs Shortest Path Problem

The Kleene star (tropical analogue of ((I - A)^{-1})) solves the all-pairs shortest path (APSP) problem:

[ W^* = I \oplus W \oplus W^{\otimes 2} \oplus \cdots = \bigoplus_{k=0}^\infty W^{\otimes k} ]

Theorem 2.1. If the graph has no negative cycles, (W^) converges after at most (n-1) terms (where (n) is the number of vertices), and (W^_{ij}) is the length of the shortest path from (i) to (j).

The Floyd-Warshall algorithm computes (W^*) in (O(n^3)) time, and it is essentially Gaussian elimination over the tropical semiring—but with the crucial difference that the absence of additive inverses means elimination must be pivoting-free (all operations are monotone). This is the mathematical reason why combinatorial algorithms like Floyd-Warshall and Bellman-Ford avoid the numerical instability of floating-point Gaussian elimination.

2.2 The Assignment Problem as a Tropical Determinant

The tropical determinant (or max-plus permanent) of an (n \times n) matrix (A) is:

[ \text{tdet}(A) = \bigoplus_{\sigma \in S_n} \bigodot_{i=1}^n A_{i, \sigma(i)} = \min_{\sigma \in S_n} \sum_{i=1}^n A_{i, \sigma(i)} ]

This is exactly the assignment problem (minimum weight perfect matching in a complete bipartite graph)! The Hungarian algorithm solves it in (O(n^3)) time. The tropical determinant is always well-defined (the minimum exists), unlike the classical determinant which is NP-hard to compute over certain semirings. The Egorychev-Falikman theorem (1981) states that for doubly stochastic matrices, the permanent is bounded below by (n!/n^n)—a result that, when tropicalized, gives the Birkhoff-von Neumann theorem: the set of doubly stochastic matrices is the convex hull of permutation matrices.

3. Tropical Curves and Phylogenetic Trees

A tropical curve in (\mathbb{R}^2) is a balanced, piecewise-linear graph: a collection of line segments and rays with rational slopes, meeting at vertices where the balancing condition holds (the sum of the primitive direction vectors at each vertex is zero, weighted by the number of coincident rays).

3.1 Phylogenetic Trees from Tropical Geometry

A phylogenetic tree on (n) species is a metric tree with labeled leaves. The space of all such trees—the Billera-Holmes-Vogtmann (BHV) tree space—is a non-positively curved geodesic metric space. Tropical geometry provides a simpler, piecewise-linear embedding of this space into (\mathbb{R}^{\binom{n}{2}}) via the tropical Grassmannian.

Theorem 3.1 (Speyer and Sturmfels, 2004). The tropical Grassmannian (\text{Trop}(Gr(2, n)))—the tropicalization of the Grassmannian of 2-planes in (\mathbb{R}^n)—is a polyhedral fan that parametrizes all metric trees on (n) taxa. The vectors of pairwise distances (d_{ij}) that arise from a tree metric are precisely the points in the Dressian (\text{Dr}(2, n)), which contains (\text{Trop}(Gr(2, n))) as the subfan of trees (as opposed to more general decomposable metrics).

The neighbor-joining algorithm for phylogenetic tree reconstruction can be interpreted as a greedy walk on the tropical Grassmannian, moving from the “star tree” (all leaves connected to a single center) toward the true tree by iteratively picking pairs that minimize the tropical determinant of the distance matrix. This tropical perspective has led to new, provably consistent algorithms for tree reconstruction from noisy distance data.

4. The Tropical Grassmannian and Matroids

The tropical Grassmannian (\text{Trop}(Gr(k, n))) parametrizes tropicalizations of (k)-planes in (\mathbb{R}^n). Its points correspond to valuated matroids—matroids equipped with a weight function satisfying the tropical Plücker relations.

Definition 4.1 (Tropical Plücker Relations). For a (k)-dimensional tropical linear space, the dressian coordinates (p_{i_1\ldots i_k}) satisfy, for any ((k-1))-subset (S) and ((k+1))-subset (T) with (S \subset T):

[ \min_{i \in T \setminus S} (p_{S \cup {i}} + p_{T \setminus {i}}) \text{ is attained at least twice} ]

This “minimum attained twice” condition is the tropicalization of the classical quadratic Plücker relations that define the Grassmannian. The set of valid tropical Plücker vectors forms a tropical prevariety (the Dressian), and those that arise from actual tropical linear spaces form a subset—the tropical Grassmannian—whose explicit description for general (k, n) is a major open problem.

5. Tropical Geometry in Optimization

5.1 Auction Algorithms and Market Equilibria

Bertsekas’ auction algorithm for the assignment problem is a primal-dual method where prices correspond to tropical eigenvalues. In the tropical interpretation: the complementary slackness conditions for the assignment problem are the tropical Cramer’s rule, and the auction update (\text{price}_j \leftarrow \text{price}_j + \varepsilon) is a tropical gradient ascent step.

5.2 Scheduling and Critical Path Analysis

The critical path method (CPM) for project scheduling computes the longest path in a directed acyclic graph. In the max-plus semiring, if (A_{ij}) is the duration of task (i \to j), then (A^{\otimes *}_{ij}) (the Kleene star) gives the earliest start time of (j) given the completion of (i). The floats (slack times) are the differences between the max-plus and min-plus Kleene stars—a duality that captures the entire scheduling flexibility.

6. Tropical Convexity and Tropical Linear Programming

Definition 6.1 (Tropical Convex Set). A set (S \subseteq \mathbb{R}^n) is tropically convex if for any (x, y \in S) and (a, b \in \mathbb{T}) with (a \oplus b = 0) (i.e., (\min(a, b) = 0)), the tropical segment ({(a \odot x) \oplus (b \odot y)} \subseteq S).

Every tropically convex set is an ordinary convex set (intersection of halfspaces) in the max-plus semiring, but the tropical convex hull of finitely many points is a tropical polytope—a union of ordinary polytopes arranged in a tree-like hierarchical structure.

Theorem 6.1 (Allamigeon, Benchimol, Gaubert, Joswig, 2018). The tropical simplex algorithm solves tropical linear programs (optimize a max-plus linear function over a tropical polytope) in polynomial time, while classical simplex methods for the same problems may require exponential time on worst-case instances. The tropical simplex pivots correspond to moves in the tree structure of the tropical polytope, and the diameter of the tropical simplex graph is (O(n^2))—compared to the Hirsch-bound exponential behavior of classical LP polytopes.

6.1 Tropical Eigenvalue Problems and the Kleene Star

The tropical eigenvalue problem (A \otimes v = \lambda \odot v) (i.e., (\min_j (A_{ij} + v_j) = \lambda + v_i)) has a unique solution (\lambda) given by the maximum cycle mean of the graph:

[ \lambda_{\max}(A) = \max_{C \text{ cycle}} \frac{\sum_{(i,j)\in C} A_{ij}}{\text{length}(C)} ]

This is Karp’s algorithm for the minimum cycle mean, central to rate analysis of discrete event systems and the design of clockless digital circuits.

7. Tropical Algebra and the Max-Plus Eigenvector of Timed Discrete Event Systems

Timed Discrete Event Systems (TDES), such as manufacturing assembly lines, traffic light networks, and packet-switched fabrics, are models where events occur at discrete times and the system state evolves according to max-plus recurrences. The state vector (x(t)) satisfies:

[ x(k+1) = A \otimes x(k) \oplus B \otimes u(k) ]

where (A) encodes the internal dependencies (e.g., a machine can’t start the next job until the previous one finishes), and (B) encodes external inputs. The max-plus eigenvalue (\lambda) of (A) is the throughput rate of the system (e.g., jobs per hour), and the corresponding eigenvector gives the steady-state timing. The cyclicity theorem (Cohen, Dubois, Quadrat, Viot, 1985) states that every irreducible max-plus matrix has a periodic regime after a finite transient: (A^{\otimes(k+c)} = \lambda^{\odot c} \odot A^{\otimes k}) for sufficiently large (k), where (c) is the cyclicity.

8. Tropical Geometry of Deep Neural Networks

A ReLU (Rectified Linear Unit) layer with weights (W) and biases (b) computes:

[ y = \max(0, Wx + b) = (Wx + b) \oplus 0 ]

where (\oplus) denotes element-wise (\max) in the max-plus (tropical) semiring. A feedforward ReLU network with (L) layers is a composition of such tropical operations, making the entire network a tropical rational function—a ratio of tropical polynomials.

Theorem 8.1 (Zhang, Naitzat, and Lim, 2018: Arora, Basu, Mianjy, Mukherjee, 2018). The function computed by a ReLU neural network with integer weights is a tropical rational function. Specifically:

[ f(x) = \max_{i \in I} (a_i^\top x + c_i) - \max_{j \in J} (b_j^\top x + d_j) ]

where (I) and (J) are index sets whose cardinality is at most exponential in the depth (L). Each pair ((I, J)) defines a linear region—a maximal connected subset of (\mathbb{R}^n) on which (f) is affine. The number of linear regions is at most (O(N^L)) for a network with (N) neurons per layer, but in practice, the tropical degree (number of monomial terms) governs the expressiveness.

9. Tropical Curves, Amoebas, and the Logarithmic Limit

The amoeba of a complex algebraic variety (V \subseteq (\mathbb{C}^*)^n) is its image under the map (\text{Log}: (z_1, \ldots, z_n) \mapsto (\log|z_1|, \ldots, \log|z_n|)). The tropicalization of (V) is the limit of amoebas as the logarithm base tends to infinity—replacing complex numbers with tropical semiring via Maslov dequantization.

Theorem 9.1 (Mikhalkin, 2004; Viro, 2001). The tropicalization of a complex algebraic curve of degree (d) is a balanced, piecewise-linear graph (a tropical curve) with exactly (d) infinite rays in each coordinate direction. Mikhalkin’s correspondence theorem states that the number of complex curves of degree (d) and genus (g) through (3d - 1 + g) generic points equals the number of tropical curves of the same degree and genus, counted with multiplicities. This reduces Gromov-Witten invariants to combinatorial enumeration of lattice paths, solvable via dynamic programming.

10. Tropical Algebraic Statistics and the EM Algorithm

A surprising application of tropical geometry is to algebraic statistics. Many latent variable models have a tropical structure governing their maximum likelihood geometry.

Theorem 10.1 (Pachter and Sturmfels, 2004). The maximum likelihood estimate (MLE) for a statistical model with hidden variables corresponds to finding the tropical intersection of the model manifold with the observed data sufficient statistics. The tropical EM algorithm replaces the sum in the E-step with a max, transforming the problem into piecewise-linear optimization solvable via linear programming.

For a Hidden Markov Model with hidden states (h_t) and observations (x_t), the forward-backward algorithm’s E-step computes (\alpha_t(i) = \sum_j \alpha_{t-1}(j) a_{ji} b_i(x_t)). The tropicalized version replaces sums with max: (\alpha_t^{\text{trop}}(i) = \max_j (\alpha_{t-1}^{\text{trop}}(j) + \log a_{ji} + \log b_i(x_t))). This is exactly the Viterbi algorithm—the standard dynamic programming solution for the most likely hidden state sequence. The tropical EM algorithm (max-product belief propagation) thus unifies dynamic programming and statistical inference under a single algebraic framework.

10.1 Tropical Principal Component Analysis

Classical PCA minimizes squared distances to a linear subspace. Tropical PCA (Yoshida, Zhang, and Zhang, 2019) replaces the Euclidean norm with the tropical metric: (d_{\text{trop}}(x, y) = \max_i (x_i - y_i) - \min_i (x_i - y_i)). The tropical principal components are tropical polytopes that best approximate the data. Unlike classical PCA, tropical PCA is robust to outliers in the max-plus sense and naturally captures hierarchical structure—making it well-suited for phylogenetic data and tree-structured metrics.

11. Tropical Cryptography: Stickel’s Protocol and the Tropical Discrete Logarithm

The hardness of tropical linear algebra suggests cryptographic applications.

Definition 11.1 (Tropical Semigroup Action Problem). Given matrices (A, X, B \in \mathbb{T}^{n \times n}) in the tropical semiring, find (S) such that (A \otimes S = S \otimes B). This is the tropical version of the conjugacy search problem underlying group-based key exchange.

Theorem 11.1 (Grigoriev and Shpilrain, 2014). The tropical semigroup action problem is NP-hard for matrices over the tropical semiring. The best known algorithms run in exponential time in (n), even on quantum computers (since tropical linear algebra lacks the group structure that Shor’s algorithm exploits).

Stickel’s Tropical Key Exchange:

1. Public parameters: matrices (A, B \in \mathbb{T}^{n \times n}).
2. Alice chooses secret (m, n), computes (U = A^{\otimes m} \otimes B^{\otimes n}), sends (U).
3. Bob chooses secret (p, q), computes (V = A^{\otimes p} \otimes B^{\otimes q}), sends (V).
4. Shared secret: (A^{\otimes m} \otimes V \otimes B^{\otimes n} = A^{\otimes p} \otimes U \otimes B^{\otimes q} = A^{\otimes(m+p)} \otimes B^{\otimes(n+q)}).

Tropical Stickel Key Exchange:

     Alice                          Bob
  A^m B^n = U ──────────────────▶
               ◀────────────────── A^p B^q = V
               
  Secret: A^m V B^n              Secret: A^p U B^q
         = A^{m+p} B^{n+q}       = A^{p+m} B^{q+n}

13. Tropical Roots, the Fundamental Theorem, and the Patchworking Construction

While classical polynomials are defined over the ring (R, +, x), tropical polynomials are defined over the tropical semiring (R union {infinity}, min, +). The correspondence between classical and tropical algebraic geometry is made precise via valuation theory and the patchworking construction of Viro (1984), which constructs real algebraic curves with prescribed topology by gluing together pieces of tropical curves.

13.1 The Fundamental Theorem of Tropical Geometry

Definition 13.1 (Tropical Hypersurface). Let f(x) = min_{a in A} (c_a + a . x) be a tropical polynomial (written in min-plus notation). The tropical hypersurface T(f) is the set of points x in R^n where the minimum in f is achieved by at least two terms:

T(f) = { x in R^n : exists a != b in A, f(x) = c_a + a . x = c_b + b . x }

This is a piecewise-linear polyhedral complex of dimension n-1. For n=2, it is a planar graph with edges of rational slopes.

Theorem 13.1 (Kapranov’s Theorem, 2000). Let K be an algebraically closed field with a non-Archimedean valuation val : K -> R union {infinity}. Let F(x) = sum_{a in A} C_a x^a be a Laurent polynomial over K with coefficients C_a in K*. The tropicalization of the classical hypersurface V(F) in (K*)^n is precisely the tropical hypersurface T(f) defined by the tropical polynomial:

f(x) = min_{a in A} (val(C_a) + a . x)

That is, trop(V(F)) = T(f), where the tropicalization of a variety is the closure (in the Euclidean topology of R^n) of the image of the variety under the coordinate-wise valuation map (x_1, …, x_n) -> (val(x_1), …, val(x_n)).

13.2 The Patchworking Theorem and Real Tropical Geometry

Theorem 13.2 (Viro’s Patchworking Theorem, 1984). Given a tropical curve C_subdivision – a balanced planar graph dual to a regular subdivision of a lattice polygon Delta – there exists a nonsingular real algebraic curve of degree deg(Delta) in the projective plane whose topology (the arrangement of its connected components, the ovals) is determined by a choice of signs on the lattice points of Delta.

The patchworking construction is algorithmic: it “glues” together pieces of the tropical curve to produce the amoeba (logarithmic image) of a real algebraic curve, and the number of ovals (connected components) is determined by the combinatorics of the subdivision. This gives a complete classification of the possible topologies of plane curves of a given degree, resolving questions that go back to Hilbert’s 16th problem on the topology of real algebraic curves.

13.3 Algorithm: Computing the Tropical Prevaraety

Given a set of classical polynomials F_1, …, F_m over a valued field, computing their tropicalization involves:

1. Expanding each polynomial into a sum of monomials with coefficients.
2. Extracting the valuations of the coefficients.
3. Computing the tropical prevariety: the intersection of the tropical hypersurfaces T(f_1), …, T(f_m).

The tropical prevariety can be computed via polyhedral algorithms (essentially, computing common refinements of the normal fans of the Newton polytopes). The complexity is polynomial in the number of monomials for fixed dimension but exponential in n in general. Software packages: Gfan (Jensen), Polymake (Gawrilow and Joswig), and Tropical.m2 for Macaulay2.

14. Tropical Eigenvectors and the Policy Iteration Algorithm for Deterministic MDPs

The max-plus (or min-plus) eigenvector problem is central to the analysis of discrete event systems and deterministic Markov decision processes (MDPs). Remarkably, tropical linear algebra provides exact algorithms that are exponentially faster than their classical counterparts.

14.1 The Tropical Eigenvalue Problem

Definition 14.1 (Tropical Eigenvalue). For a matrix A in (R_max)^{n x n} (max-plus semiring), the tropical eigenvalue lambda(A) is the maximum cycle mean:

lambda(A) = max_{sigma cycle} (A_{i_1 i_2} + A_{i_2 i_3} + … + A_{i_k i_1}) / k

A vector v in R_max^n is a tropical eigenvector if A odot v = lambda odot v (componentwise: max_j (A_{i j} + v_j) = lambda + v_i for all i).

Theorem 14.1 (Cochet-Terrasson, Cohen, Gaubert, Quadrat, Singer). The tropical eigenvalue exists and is unique (if A is irreducible). The eigenspace is a finitely generated semimodule (a tropical convex cone). Computing lambda(A) reduces to finding the maximum cycle mean in the weighted directed graph with adjacency matrix A, solvable by Karp’s algorithm in O(VE) time.

14.2 Policy Iteration as a Tropical Newton Method

Theorem 14.2 (Policy Iteration = Tropical Newton, Akian, Gaubert, and Cochet-Terrasson, 2003). Consider a deterministic MDP with transition function T(s, a) and reward r(s, a). The optimal value function v*(s) satisfies the Bellman optimality equation:

v*(s) = max_a [ r(s, a) + gamma * v*(T(s, a)) ]

In the max-plus algebra, this is a tropical linear equation. The policy iteration algorithm – which alternates between policy evaluation (solving a system of tropical linear equations) and policy improvement (greedy maximization) – is exactly a tropical Newton method for finding the fixed point of the Bellman operator. The quadratic convergence of Newton in the classical setting translates to finite termination in at most n iterations for deterministic MDPs, explaining why policy iteration is exceptionally efficient in practice despite the theoretical possibility of exponential worst-case behavior (the Melekopoglou-Condon counterexample, which requires 2^n/2 iterations, requires pathological reward structures).

14.3 The Max-Plus Fundamental Matrix and the Perturbation Analysis

Given a max-plus linear system x = A odot x + b (a fixed-point equation in the max-plus semiring), define the Kleene star:

A* = I oplus A oplus A^{odot 2} oplus A^{odot 3} oplus …

where A^{odot k} = A odot A odot … odot A (k times). Then the least solution of x = A odot x oplus b is x = A* odot b if A* exists (i.e., if all cycles have weight <= 0, the max-plus spectral radius condition).

This is the max-plus analogue of the Neumann series (I - A)^{-1} = I + A + A^2 + … in classical linear algebra. The Kleene star can be computed by the Floyd-Warshall algorithm in O(n^3) or by repeated squaring in O(n^3 log n) for dense matrices. This is the algebraic foundation for computing the performance bounds (throughput, latency) of max-plus linear systems, including timed Petri nets, manufacturing systems, and traffic networks.

15. Tropical Differential Equations and the Ultra-Discretization Limit

A fascinating connection exists between classical differential equations and tropical (or ultra-discrete) dynamical systems. The ultra-discretization procedure (Tokihiro, Takahashi, Matsukidaira, Satsuma, 1996) transforms integrable PDEs into cellular automata via a limiting process equivalent to tropicalization.

15.1 From Soliton Equations to Box-Ball Systems

Consider the KdV equation u_t + 6 u u_x + u_{xxx} = 0, the paradigmatic integrable PDE describing shallow water waves. Its discrete analogue, the Lotka-Volterra equation, can be ultra-discretized to obtain the box-ball system (Takahashi and Satsuma, 1990): a cellular automaton where “balls” (particles) move along “boxes” (sites) according to a simple rule: each ball moves to the nearest empty box to its right.

The key transformation: define U_n^t such that u_n^t = exp(U_n^t / epsilon). Taking the limit epsilon -> 0 in the discrete KdV equation yields the max-plus equation:

U_n^{t+1} = max(0, U_{n-1}^t) + U_n^t - max(0, U_n^t)

which is precisely the update rule for the box-ball system in the max-plus algebra. The soliton solutions of KdV correspond to tropical solitons – coherent particle-like excitations that maintain their shape through collisions.

15.2 Tropical Discretization for Hamilton-Jacobi Equations

The Hamilton-Jacobi equation S_t + H(S_x) = 0 describes the evolution of the action function S(x, t) in classical mechanics. Its viscosity solution (Crandall and Lions, 1983) can be approximated by a tropical discretization:

S_i^{n+1} = min_j [ S_j^n + Delta t * L((x_i - x_j)/Delta t) ]

where L is the Legendre transform of H (the Lagrangian). This is exactly a min-plus convolution, and the resulting numerical scheme is the Lax-Oleinik formula for the entropy solution of scalar conservation laws. The convergence rate is O(sqrt{Delta t}) – the same as classical finite-difference schemes – but the tropical scheme has the advantage of being monotone (hence stable and convergent) by construction, a property that is difficult to guarantee for high-order classical schemes.

16. Tropical Geometry of the Auction Theory and Mechanism Design

One of the most surprising applications of tropical geometry is to auction theory and mechanism design in algorithmic game theory. The connection arises because the revenue of an auction can be expressed as a tropical polynomial in the bids, and the incentive compatibility constraint is a tropical convexity condition.

16.1 The Vickrey Auction as a Tropical Polynomial

In a sealed-bid second-price (Vickrey) auction with n bidders, the winner is the highest bidder, and they pay the second-highest bid. The auctioneer’s revenue is:

R(b_1, …, b_n) = max_{i != argmax_j b_j} b_i = “the maximum excluding the global maximum”

In max-plus algebra, this is:

R = (b_1 odot b_2 odot … odot b_n) odot (min_{i} b_i^{odot(-1)})

where b_i^{odot(-1)} = -b_i (the tropical inverse). The revenue is a tropical rational function of the bids.

More generally, for any dominant-strategy incentive-compatible (DSIC) mechanism, the allocation and payment rules satisfy a tropical monotonicity condition: the payment of a winner is the tropical minimum of bids that would also make them win. This is the Myerson lemma expressed in the tropical language.

16.2 The Tropical Cone of Feasible Mechanisms

Definition 16.1 (Tropical Feasibility Cone). An auction mechanism defined by allocation rule x_i(b) in {0, 1} and payment rule p_i(b) for each bidder i is DSIC if and only if the pair (x_i, p_i) satisfies:

x_i(b) = 1 implies b_i odot p_i(b_{-i}) >= p_{-i}(b) for all b

and p_i(b) = min{ b_i’ : x_i(b_i’, b_{-i}) = 1 }

This is precisely the condition that the set of winning-bid vectors forms a tropical convex set (a set closed under tropical linear combinations). The tropical convex hull of a set of extreme points (the tropical polytope) corresponds to the set of all DSIC mechanisms that are “randomizations” over deterministic mechanisms.

16.3 The Revenue-Maximizing Auction as a Tropical Optimization Problem

Myerson’s optimal auction problem – maximize expected revenue subject to DSIC and individual rationality – becomes a tropical linear program:

maximize E_b [ sum_i p_i(b) ] subject to: x_i(b_i, b_{-i}) - x_i(b_i’, b_{-i}) is tropically monotone

The solution – Myerson’s virtual value auction – can be derived as the optimal solution to a minimal tropical hypersurface interpolation problem: find the “simplest” tropical polynomial (in terms of the number of monomials) that interpolates the given revenue at the observed bid vectors while satisfying the DSIC constraints. This tropical perspective on optimal auction design unifies the classical Myerson theory with modern approaches based on regret minimization and differential privacy in mechanism design.

17. Tropical Implicitization and the Geometry of the EM Algorithm

The Expectation-Maximization (EM) algorithm, fundamental to latent variable models in machine learning, has a deep connection to tropical geometry via the tropicalization of maximum likelihood estimation.

17.1 The Tropical MLE and the Newton Polytope of the Likelihood

Consider a discrete latent variable model with observed variables X, latent variables Z, and parameters theta. The complete data likelihood L_c(theta; X, Z) is a polynomial in theta. The marginal likelihood L(theta; X) = sum_Z L_c(theta; X, Z) is a sum of polynomials, and its maximization over theta is the MLE problem.

As the sample size n -> infinity, the log-likelihood converges to an expected log-likelihood, and the MLE converges to the maximizer of:

theta* = argmax sum_x p(x) log ( sum_z L_c(theta; x, z) )

Taking the tropical limit (log -> min) transforms the sum over latent variables into a minimum over latent variables:

theta*_tropical = argmin sum_x p(x) min_z ( -log L_c(theta; x, z) )

This is a piecewise-linear optimization problem – a tropical linear program. The tropical MLE can be computed exactly via polyhedral methods, providing a rigorous lower bound on the classical MLE and giving insight into the landscape of the likelihood function (the number and location of its local maxima).

17.2 The Newton Polytope of the EM Fixed Point Equations

The EM algorithm iteratively maximizes the expected complete-data log-likelihood:

Q(theta | theta^{(t)}) = E_{Z|X, theta^{(t)}} [ log L_c(theta; X, Z) ]

The fixed points of EM satisfy the equation theta = argmax_theta Q(theta | theta’). Tropicalizing this equation yields a tropical fixed-point system whose solutions correspond to the tropical limits of the EM fixed points. The number of such fixed points is bounded by the number of vertices of the Newton polytope of the likelihood function, which is the convex hull of the exponent vectors of the monomials appearing in L_c.

This combinatorial bound gives a rigorous upper limit on the number of local maxima the EM algorithm can converge to, explaining both its susceptibility to local optima and the effectiveness of random restarts in practice. The study of the tropical geometry of the EM algorithm is an active area of research at the intersection of computational algebra and machine learning.

The tropical perspective reveals that the EM algorithm, far from being a heuristic, is a principled iterative method for navigating the combinatorial structure of the Newton polytope of the complete-data likelihood – an insight that bridges computational statistics and tropical algebraic geometry in a mathematically profound and practically useful way.

This unification of pure and applied mathematics – from the box-ball systems of integrable PDEs to the revenue-optimal auctions of mechanism design – makes tropical geometry one of the most exciting and rapidly evolving fields at the interface of mathematics and computer science.

Truly, the tropical lens transforms our understanding of computational phenomena across an astonishing range of domains.

18. Summary

Tropical geometry reveals that many classical combinatorial algorithms are algebraic geometry in disguise. The shortest path problem is matrix multiplication in the min-plus semiring. The assignment problem is the tropical determinant. Phylogenetic trees are points in the tropical Grassmannian. ReLU neural networks are tropical rational functions. The tropical EM algorithm unifies dynamic programming and statistical inference.

For the computer scientist, tropical geometry provides a unifying language for combinatorial optimization, revealing that apparently different problems (shortest paths, matching, scheduling, tree reconstruction, deep learning) share a common algebraic structure. This perspective has led to new algorithms (tropical Bezout bounds), new hardness results (tropical rank is NP-hard), new cryptographic schemes, and new connections between continuous optimization and discrete combinatorics.

To go deeper, Maclagan and Sturmfels’ Introduction to Tropical Geometry is the definitive text. Butković’s Max-linear Systems: Theory and Algorithms develops the linear algebra. And for the phylogenetics connection, the papers by Speyer and Sturmfels on the tropical Grassmannian are the essential references.