Cyclic projectors and separation theorems in idempotent convex geometry

Abstract

Semimodules over idempotent semirings like the max-plus or tropical semiring have much in common with convex cones. This analogy is particularly apparent in the case of subsemimodules of the n-fold cartesian product of the max-plus semiring it is known that one can separate a vector from a closed subsemimodule that does not contain it. We establish here a more general separation theorem, which applies to any finite collection of closed semimodules with a trivial intersection. In order to prove this theorem, we investigate the spectral properties of certain nonlinear operators called here idempotent cyclic projectors. These are idempotent analogues of the cyclic nearest-point projections known in convex analysis. The spectrum of idempotent cyclic projectors is characterized in terms of a suitable extension of Hilbert's projective metric. We deduce as a corollary of our main results the idempotent analogue of Helly's theorem.

20 pages, 1 figure

References in corpus (3)

• Duality and separation theorems in idempotent semimodules
• The Minkowski Theorem for Max-plus Convex Sets
• Generators, extremals and bases of max cones

Cited by in corpus (7)

• Tropicalizing the simplex algorithm
• Minimal half-spaces and external representation of tropical polyhedra
• The number of extreme points of tropical polyhedra
• The level set method for the two-sided eigenproblem
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• Characterization of tropical hemispaces by (P,R)-decompositions
• An interval version of separation by semispaces in max-min convexity