The Minkowski theorem for max-plus convex sets

DOI10.1016/J.LAA.2006.09.019MaRDI QIDQ869905zbMATH OpenOpenAlexFDO

Authors Stéphane Gaubert, Ricardo D. Katz

Publication date 9 March 2007

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

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

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)

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.

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

Cites work

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

Cited in

(47)

• Presentations of transversal valuated matroids
• Tropical polar cones, hypergraph transversals, and mean payoff games
• On the largest convex subsets in Minkowski sums
• Basic solutions of systems with two max-linear inequalities
• Tropical reproducing kernels and optimization
• 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
• The tropical analogue of polar cones
• The Whitney embedding theorem for tropical torsion modules. Classification of tropical modules
• Max-Plus Convex Geometry
• Minimal half-spaces and external representation of tropical polyhedra
• Barabanov norms, Lipschitz continuity and monotonicity for the max algebraic joint spectral radius
• L-infinity optimization to Bergman fans of matroids with an application to phylogenetics
• Monomial Tropical Cones for Multicriteria Optimization
• On visualization scaling, subeigenvectors and Kleene stars in max algebra
• Minimizing maximum lateness in two-stage projects by tropical optimization
• The number of extreme points of tropical polyhedra
• Reachability analysis for timed automata using max-plus algebra
• Hyperspace of max-plus convex compact sets
• Z-matrix equations in max-algebra, nonnegative linear algebra and other semirings
• 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
• Tropical linear algebra with the Łukasiewicz t-norm
• Face posets of tropical polyhedra and monomial ideals
• Extremals of the supereigenvector cone in max algebra: a combinatorial description
• Representation of max-plus convex sets in terms of extreme points and extreme generators
• Tropicalization of facets of polytopes
• Cyclic projectors and separation theorems in idempotent convex geometry
• Tropical polyhedra are equivalent to mean payoff games
• Idempotent version of the Fréchet contingency array problem
• Extreme rays of the ^-nearest ultrametric tropical polytope
• 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
• 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)