The duality theorem for min-max functions |
| |
| Affiliation: | 1. INRIA, domaine de Voluceau, B.P. 105, 78153 Le Chesnay cedex, France;2. BRIMS, Hewlett-Packard Labs, Filton Road, Stoke Gifford, Bristol BS12 6QZ, UK;1. National Research University Higher School of Economics, Myasnitskaya 20, 101000 Moscow, Russia;2. JSC “Research and Design Institute for Information Technology, Signalling and Telecommunications on Railway Transport”, Orlikov per. 5, building 1, 107996 Moscow, Russia;1. Department of Electrical Engineering, National Institute of Technology Agartala, India;2. Gandhi Institute for Technological Advancement (GITA), Bhubaneswar, Odisha 752054, India;1. Sao Paulo School of Economics–FGV, Brazil;2. CNRS and Ceremade, Université Paris-Dauphine, France;3. University of Glasgow, Adam Smith Business School, Scotland, United Kingdom |
| |
| 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: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
