Duality and separation theorems in idempotent semimodules

Abstract

We consider subsemimodules and convex subsets of semimodules over semirings with an idempotent addition. We introduce a nonlinear projection on subsemimodules: the projection of a point is the maximal approximation from below of the point in the subsemimodule. We use this projection to separate a point from a convex set. We also show that the projection minimizes the analogue of Hilbert's projective metric. We develop more generally a theory of dual pairs for idempotent semimodules. We obtain as a corollary duality results between the row and column spaces of matrices with entries in idempotent semirings. We illustrate the results by showing polyhedra and half-spaces over the max-plus semiring.

24 pages, 5 Postscript figures, revised (v2)

References in corpus (2)

• Linear functionals on idempotent spaces: an algebraic approach
• Nuclear semimodules and kernel theorems in idempotent analysis. An algebraic approach

Cited by in corpus (70)

• The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis
• Tropical polyhedra are equivalent to mean payoff games
• The Minkowski Theorem for Max-plus Convex Sets
• Log-barrier interior point methods are not strongly polynomial
• Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms
• Tropicalizing the simplex algorithm
• Tropical linear-fractional programming and parametric mean payoff games
• Computing the vertices of tropical polyhedra using directed hypergraphs
• Minimal half-spaces and external representation of tropical polyhedra
• The Maslov dequantization, idempotent and tropical mathematics: A brief introduction
• Duality between invariant spaces for max-plus linear discrete event systems
• Best approximation in max-plus semimodules
• Convexity in Tree Spaces
• The number of extreme points of tropical polyhedra
• Tropical Fermat-Weber points
• Weighted digraphs and tropical cones
• Tropical matrix duality and Green's D relation
• The tropical analogue of polar cones
• Pure Dimension and Projectivity of Tropical Polytopes
• The max-plus Martin boundary
• Max-plus definite matrix closures and their eigenspaces
• The tropical double description method
• Semiring and semimodule issues in MV-algebras
• Tropical polar cones, hypergraph transversals, and mean payoff games
• Exact rings and semirings
• Dynamical Systems On Weighted Lattices: General Theory
• Understanding and monitoring the evolution of the Covid-19 epidemic from medical emergency calls: the example of the Paris area
• Duality and interval analysis over idempotent semirings
• Tropical implementation of the Analytical Hierarchy Process decision method
• Rational semimodules over the max-plus semiring and geometric approach of discrete event systems
• A max-plus finite element method for solving finite horizon deterministic optimal control problems
• On tropical Kleene star matrices and alcoved polytopes
• Cyclic projectors and separation theorems in idempotent convex geometry
• Minimal external representations of tropical polyhedra
• Tropical Geometric Variation of Phylogenetic Tree Shapes
• Tropicalization of group representations
• The max-plus finite element method for optimal control problems: further approximation results
• The Legendre-Fenchel transform from a category theoretic perspective
• Characterization of tropical hemispaces by (P,R)-decompositions
• Tropical Polynomial Division and Neural Networks
• Idempotent and tropical mathematics and problems of mathematical physics (Volume II)
• A tropical isoperimetric inequality
• Approximating the Volume of Tropical Polytopes is Difficult
• The tropical analogue of the Helton-Nie conjecture is true
• Quasi--Euclidean classification of Alcoved Convex Polyhedra
• A new fundamental solution for a class of differential Riccati equations
• Tropical convexity in location problems
• Max-Plus Matching Pursuit for Deterministic Markov Decision Processes
• Orders and Polytropes: Matrix Algebras from Valuations
• Tropical Gaussians: A Brief Survey
• An Invitation to Tropical Alexandrov Curvature
• Solutions of max-plus linear equations and large deviations
• Tropical Geometry and Piecewise-Linear Approximation of Curves and Surfaces on Weighted Lattices
• Tropical principal component analysis on the space of ultrametrics
• Completeness and injectivity
• Idempotent tropical matrices and finite metric spaces
• Asymmetric tropical distances and power diagrams
• Enriched categories and tropical mathematics
• Tropical Data Science
• Submodule codes as spherical codes in buildings
• Tropical convex hulls of polyhedral sets
• Convex geometry over ordered hyperfields
• Idempotent and tropical mathematics. Complexity of algorithms and interval analysis
• Condition numbers of stochastic mean payoff games and what they say about nonarchimedean semidefinite programming
• Tropical Hurwitz Spaces
• Homological Algebra of Heyting modules
• Tropical mathematics, classical mechanics and geometry
• Kernel theorems and nuclearity in idempotent mathematics. An algebraic approach
• Tropical linear maps on the plane
• Tree Topologies along a Tropical Line Segment