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

Stéphane Gaubert 1, 2 W.M. Mceneaney 3
2 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, Polytechnique - X, CNRS - Centre National de la Recherche Scientifique : UMR
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.
Type de document :
Article dans une revue
Appl. Math. Optim., Springer, 2012, 65 (3), pp.315--348. 〈10.1007/s00245-011-9158-5〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00782746
Contributeur : Canimogy Cogoulane <>
Soumis le : mercredi 30 janvier 2013 - 15:12:58
Dernière modification le : jeudi 11 janvier 2018 - 06:22:34

Identifiants

Collections

Citation

Stéphane Gaubert, W.M. Mceneaney. Min-max spaces and complexity reduction in min-max expansions. Appl. Math. Optim., Springer, 2012, 65 (3), pp.315--348. 〈10.1007/s00245-011-9158-5〉. 〈hal-00782746〉

Partager

Métriques

Consultations de la notice

211