Duality and separation theorems in idempotent semimodules

By G. Cohen, Stephane Gaubert, J. Quadrat. 2002

278 citations recorded by the source corpus.

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.

Subfields: Algebra and Number Theory, Computational Theory and Mathematics, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/75526270c3a4bf1d7203087bf9246e0065c39c2c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Algebra and Number Theory

1. Marianne Akian
2. Ricardo D. Katz
3. Stephane Gaubert
4. Grigori L. Litvinov

In Computational Theory and Mathematics

1. Stephane Gaubert
2. Ricardo D. Katz
3. Marianne Akian
4. Grigori L. Litvinov
5. Cormac Walsh
6. Peter Butkovic

In Management Science and Operations Research

1. Ricardo D. Katz
2. Marianne Akian
3. Stephane Gaubert

Citations in the corpus

• The max-plus Martin boundary (2004, background): “maximum and the addition of a constant (see [LMS01, CGQ04 ] for definitions and properties of semimodules).”
• Minimal half-spaces and external representation of tropical polyhedra (2009, methodology): “It was studied by Litvinov, Maslov, and Shpiz [29], in relation to problems of calculus of variations, and by Cohen, Gaubert, and Quadrat [12, 13], motivated by discrete event system problems (max-plus polyhedra represent invariant spaces of max-plus linear dynamical systems [11]).”
• Best approximation in max-plus semimodules☆ (2010, methodology): “Following [7, 8, 13], we define the Hilbert projective distance d on Rnmax by d(x, y) := δ(x, y)−, (2.”
• The Maslov dequantization, idempotent and tropical mathematics: A brief introduction (2005, background): “otent Hilbert spaces. Important results on idempotent functional analysis (duality and separation theorems) are MASLOV’S DEQUANTIZATION 9 recently published by G. Cohen, S. Gaubert, and J.-P. Quadrat [17]; see also a finite dimensional version of the separation theorem in [133]. Three papers on this ”