| HAL-Inria | Publications, software ... of Inria's scientists |
Reports
Duality and Separation Theorems in Idempotent Semimodules
Abstract : We consider subsemimodules and convex subsets of semimodules over semirings with an idempotent addition. We introduce nonlinear projection on subsemimod- ules: 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.
https://hal.inria.fr/inria-00071917
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 7:14:32 PM
Last modification on : Friday, February 4, 2022 - 3:10:13 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:44:26 PM
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 7:14:32 PM
Last modification on : Friday, February 4, 2022 - 3:10:13 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:44:26 PM