The Minkowski Theorem for Max-plus Convex Sets

Abstract

We establish the following max-plus analogue of Minkowski's theorem. Any point of a compact max-plus convex subset of $(R\cup \{-\infty \}{)}^n$ can be written as the max-plus convex combination of at most $n+1$ of the extreme points of this subset. We establish related results for closed max-plus convex cones and closed unbounded max-plus convex sets. In particular, we show that a closed max-plus convex set can be decomposed as a max-plus sum of its recession cone and of the max-plus convex hull of its extreme points.

13 pages, 4 figures (5 eps files)

References in corpus (4)

• Duality and separation theorems in idempotent semimodules
• The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis
• Generators, extremals and bases of max cones
• The max-plus finite element method for optimal control problems: further approximation results

Cited by in corpus (29)

• Tropical polyhedra are equivalent to mean payoff games
• Generators, extremals and bases of max cones
• On visualisation scaling, subeigenvectors and Kleene stars in max algebra
• Computing the vertices of tropical polyhedra using directed hypergraphs
• Minimal half-spaces and external representation of tropical polyhedra
• Duality between invariant spaces for max-plus linear discrete event systems
• The number of extreme points of tropical polyhedra
• Tropical matrix duality and Green's D relation
• The tropical analogue of polar cones
• Tropical polar cones, hypergraph transversals, and mean payoff games
• The tropical double description method
• Dynamical Systems On Weighted Lattices: General Theory
• Combinatorial simplex algorithms can solve mean payoff games
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• Tropical linear algebra with the Lukasiewicz T-norm
• Cyclic projectors and separation theorems in idempotent convex geometry
• Two cores of a nonnegative matrix
• Minimal external representations of tropical polyhedra
• Presentations of Transversal Valuated Matroids
• Idempotent and tropical mathematics and problems of mathematical physics (Volume II)
• Characterization of tropical hemispaces by (P,R)-decompositions
• Basic solutions of systems with two max-linear inequalities
• Minimizing maximum lateness in two-stage projects by tropical optimization
• Face posets of tropical polyhedra and monomial ideals
• On the max-algebraic core of a nonnegative matrix
• Tropical convex hulls of polyhedral sets
• Extreme rays of the ${\ell }^{\infty }$-nearest ultrametric tropical polytope
• L-Infinity optimization in tropical geometry and phylogenetics
• Extremals of the supereigenvector cone in max algebra: a combinatorial description