HP Labs Technical Reports

Dynamics of Min-Max Functions

Cochet-Terrasson, Jean; Gaubert, Stephane; Gunawardena, Jeremy

HPL-BRIMS-97-13

Keyword(s): cycle time; discrete event system; fixed point; max- plus semiring; nonexpansive map; Perron-Frobenius; 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, (so-called 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 min-max functions studied in this paper. Any topical function F can be approximated by min-max functions in a way which preserves some of the dynamics of F. We attempt, therefore, to clarify the dynamics of min-max functions, with a view to developing a generalised Perron-Frobenius 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