The Minkowski theorem for max-plus convex sets

DOI10.1016/J.LAA.2006.09.019zbMATH Open1110.52002arXivmath/0605078OpenAlexW2020145866MaRDI QIDQ869905FDOQ869905

Authors: Stéphane Gaubert, Ricardo D. Katz 

Publication date: 9 March 2007

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Abstract: We establish the following max-plus analogue of Minkowski's theorem. Any point of a compact max-plus convex subset of $(Rcup-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.

Full work available at URL: https://arxiv.org/abs/math/0605078

Recommendations

• Representation of max-plus convex sets in terms of extreme points and extreme generators
• Max-Plus Convex Geometry
• Max-plus convex sets and max-plus semispaces. I
• Minkowski's theorem for arbitrary convex sets
• Max-plus convex sets and max-plus semispaces. II

zbMATH Keywords

polyhedraextreme pointspolytopesconvex setstropical algebraconvex conesabstract convexityMax-plus algebraKrein-Milman theoremCaratheodory theorem

Mathematics Subject Classification ID

Semirings (16Y60) Convex sets in topological linear spaces; Choquet theory (46A55) Axiomatic and generalized convexity (52A01)

Cites Work

• Tropical convexity
• The max-plus Martin boundary
• Linear and combinatorial optimization in ordered algebraic structures
• Disjunctive optimization, \(\max\)-separable problems and extremal algebras
• Title not available (Why is that?)
• Max-Plus $(A,B)$-Invariant Spaces and Control of Timed Discrete-Event Systems
• Moduloïds and pseudomodules. I: Dimension theory
• Duality and separation theorems in idempotent semimodules.
• The tropical Grassmannian
• Tropical halfspaces
• Idempotent functional analysis: An algebraic approach
• Methods and applications of \((\max,+)\) linear algebra
• Title not available (Why is that?)
• The Max-Plus Finite Element Method for Solving Deterministic Optimal Control Problems: Basic Properties and Convergence Analysis
• A Max-Plus-Based Algorithm for a Hamilton--Jacobi--Bellman Equation of Nonlinear Filtering
• Bases in max-algebra
• Downward sets and their separation and approximation properties
• Title not available (Why is that?)
• Topologies on lattice ordered groups, separation from closed downward sets and conjugations of type Lau
• Title not available (Why is that?)
• Max-Plus Convex Geometry
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (47)

• Presentations of transversal valuated matroids
• Tropical polar cones, hypergraph transversals, and mean payoff games
• Tropical reproducing kernels and optimization
• On the largest convex subsets in Minkowski sums
• Basic solutions of systems with two max-linear inequalities
• Minkowski type theorems for convex sets in cones
• Steady states in the scheduling of discrete-time systems
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• Max-Plus Convex Geometry
• The tropical analogue of polar cones
• The Whitney embedding theorem for tropical torsion modules. Classification of tropical modules
• Barabanov norms, Lipschitz continuity and monotonicity for the max algebraic joint spectral radius
• Minimal half-spaces and external representation of tropical polyhedra
• L-infinity optimization to Bergman fans of matroids with an application to phylogenetics
• Monomial Tropical Cones for Multicriteria Optimization
• Minimizing maximum lateness in two-stage projects by tropical optimization
• On visualization scaling, subeigenvectors and Kleene stars in max algebra
• The number of extreme points of tropical polyhedra
• Reachability analysis for timed automata using max-plus algebra
• Z-matrix equations in max-algebra, nonnegative linear algebra and other semirings
• Hyperspace of max-plus convex compact sets
• Closed convex sets of Minkowski type
• Max-algebraic attraction cones of nonnegative irreducible matrices
• Static analysis of ReLU neural networks with tropical polyhedra
• Computing the vertices of tropical polyhedra using directed hypergraphs
• Tropical Ehrhart theory and tropical volume
• Computational techniques for reachability analysis of Max-Plus-Linear systems
• Face posets of tropical polyhedra and monomial ideals
• Tropical linear algebra with the Łukasiewicz t-norm
• Representation of max-plus convex sets in terms of extreme points and extreme generators
• Extremals of the supereigenvector cone in max algebra: a combinatorial description
• Tropicalization of facets of polytopes
• Cyclic projectors and separation theorems in idempotent convex geometry
• Tropical polyhedra are equivalent to mean payoff games
• Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria
• On the set-estimation of uncertain max-plus linear systems
• Extreme rays of the \(\ell^\infty\)-nearest ultrametric tropical polytope
• Idempotent version of the Fréchet contingency array problem
• Convexly independent subsets of the Minkowski sum of planar point sets
• Geometrical aspects of possibility measures on finite domain MV-clans
• The minimizing vector theorem in symmetrized max-plus algebra
• Two cores of a nonnegative matrix
• Characterization of tropical hemispaces by \((P, R)\)-decompositions
• Tropical planar networks
• Michael selection theorem for max-plus compact convex sets
• Inferring Min and Max Invariants Using Max-Plus Polyhedra
• Dynamical systems on weighted lattices: general theory

This page was built for publication: The Minkowski theorem for max-plus convex sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q869905)