The duality theorem for min-max functions
1998
Abstract The set of min-max functions F : ℝ n → ℝ n 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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
12
References
87
Citations
NaN
KQI