FUNDAMENTALNAYA I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2007, VOLUME 13, NUMBER 4, PAGES 31-52

Cyclic projectors and separation theorems in idempotent convex geometry

S. Gaubert
S. N. Sergeev

Abstract

View as HTML     View as gif image

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. Here we establish a more general separation theorem, which applies to any finite collection of closed subsemimodules with a trivial intersection. The proof of this theorem involves specific nonlinear operators, called here cyclic projectors on idempotent semimodules. These are analogues of the cyclic nearest-point projections known in convex analysis. We obtain a theorem that characterizes the spectrum of cyclic projectors on idempotent semimodules in terms of a suitable extension of Hilbert's projective metric. We also deduce as a corollary of our main results the idempotent analogue of Helly's theorem.

Location: http://mech.math.msu.su/~fpm/eng/k07/k074/k07402h.htm
Last modified: November 28, 2007