Skip to Main content Skip to Navigation
Journal articles

Min-max spaces and complexity reduction in min-max expansions

Abstract : Idempotent methods have been found to be extremely helpful in the numerical solution of certain classes of nonlinear control problems. In those methods, one uses the fact that the value function lies in the space of semiconvex functions (in the case of maximizing controllers), and approximates this value using a truncated max-plus basis expansion. In some classes, the value function is actually convex, and then one specifically approximates with suprema (i.e., max-plus sums) of affine functions. Note that the space of convex functions is a max-plus linear space, or moduloid. In extending those concepts to game problems, one finds a different function space, and different algebra, to be appropriate. Here we consider functions which may be represented using infima (i.e., min-max sums) of max-plus affine functions. It is natural to refer to the class of functions so represented as the min-max linear space (or moduloid) of max-plus hypo-convex functions. We examine this space, the associated notion of duality and min-max basis expansions. In using these methods for solution of control problems, and now games, a critical step is complexity-reduction. In particular, one needs to find reduced-complexity expansions which approximate the function as well as possible. We obtain a solution to this complexity-reduction problem in the case of min-max expansions.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/hal-00782746
Contributor : Canimogy Cogoulane <>
Submitted on : Wednesday, January 30, 2013 - 3:12:58 PM
Last modification on : Thursday, August 26, 2021 - 1:34:02 PM

Links full text

Identifiers

Collections

Citation

Stéphane Gaubert, W.M. Mceneaney. Min-max spaces and complexity reduction in min-max expansions. Applied Mathematics and Optimization, Springer Verlag (Germany), 2012, 65 (3), pp.315--348. ⟨10.1007/s00245-011-9158-5⟩. ⟨hal-00782746⟩

Share

Metrics

Record views

375