
HP Labs Technical Reports
Click here for full text:
Dynamics of MinMax Functions
CochetTerrasson, Jean; Gaubert, Stephane; Gunawardena, Jeremy
HPLBRIMS9713
Keyword(s): cycle time; discrete event system; fixed point; max plus semiring; nonexpansive map; PerronFrobenius; policy improvement; topical function
Abstract: Function F : Rn * Rn which are expansive in the l* norm and homogeneous, Fi (x1 + h,. . . ,x n + h) = FI((x1, . . . ,xn) +h, (socalled topical functions) have appeared recently in the work of several authors. They include (after suitable transformation) nonnegative matrices, Leontieff substitution systems, Bellman operators of games and of Markov decisions processes, examples arising from discrete event systems (digital circuits, computer networks, etc) and the minmax functions studied in this paper. Any topical function F can be approximated by minmax functions in a way which preserves some of the dynamics of F. We attempt, therefore, to clarify the dynamics of minmax functions, with a view to developing a generalised PerronFrobenius theory for topical functions. Our main concern is with the existence of generalised fixed points, where F(x1,. . . ,xn) = (x1+h,. . . ,xn+h) which correspond to nonlinear eigenvectors, and with the cycle time vector, c(F) = limk Fk (x)/ k Rn, which generalises the spectral radius. The Duality Conjecture for min max functions asserts that this limit always exists, shows how it can be calculated and implies the strong result that F has a fixed point if, and only if, c(F) = (h,. . .,h). We use an analogue of Howard's policy improvement scheme from optimal control to prove a fixed point theorem of equivalent strength, which is independent of the Duality Conjecture, and we give a proof of the Conjecture itself for n = 2.
37 Pages
Back to Index
