HP Labs Technical Reports



Click here for full text: PDF

The Duality Theorem for Min-Max Functions

Gaubert, Stephanie; Gunawardena, Jeremy

HPL-BRIMS-97-16

Keyword(s): cycle time; generalized eigenvector; nonexpansive map; policy improvement

Abstract: The set of min-max functions F : Rn Rn is the least set containing coordinate substitutions and translations and closed under pointwise max, min, and function composition. The Duality Conjecture asserts that the trajectories of a min-max function, considered as a dynamical system, have a linear growth rate (cycle time) and shows how this can be calculated through a representation of F as an infimum of max- plus linear functions. We prove the conjecture using an analogue of Howard's policy improvement scheme, carried out in a lattice ordered group of germs of affine functions at infinity. The methods yield an efficient algorithm for computing cycle times.

6 Pages

Back to Index

[Research] [News] [Tech Reports] [Palo Alto] [Bristol] [Japan] [Israel] [Site Map][Home] [Hewlett-Packard]