Bundle-based pruning in the max-plus curse of dimensionality free method

Stéphane Gaubert 1, 2 Zheng Qu 3 Srinivas Sridharan 4
1 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
2 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique
3 School of Mathematics, University of Edinburgh, Edinburgh, United Kingdom
4 University of Sussex
Abstract : Recently a new class of techniques termed the max-plus curse of dimensionality-free methods have been de- veloped to solve nonlinear optimal control problems. In these methods the discretization in state space is avoided by using a max-plus basis expansion of the value function. This requires storing only the coefficients of the basis functions used for representation. However, the number of basis functions grows exponentially with respect to the number of time steps of propagation to the time horizon of the control problem. This so called “curse of complexity” can be managed by applying a pruning procedure which selects the subset of basis functions that contribute most to the approximation of the value function. The pruning procedures described thus far in the literature rely on the solution of a sequence of high dimensional optimization problems which can become computationally expensive. In this paper we show that if the max-plus basis functions are linear and the region of interest in state space is convex, the pruning problem can be efficiently solved by the bundle method. This approach combining the bundle method and semidefinite formulations is applied to the quantum gate synthesis problem, in which the state space is the special unitary group (which is non-convex). This is based on the observation that the convexification of the unitary group leads to an exact relaxation. The results are studied and validated via examples.
Keywords : quantum control Optimal control curse of dimensionality reduction semidefinite relaxation special unitary group
Type de document :
Communication dans un congrès
Proceedings of the 21st International Symposium on Mathematical Theory of Networks and Systems, Jul 2014, Groningen, Netherlands. 2014, 〈https://fwn06.housing.rug.nl/mtns2014/〉
Liste complète des métadonnées
https://hal.inria.fr/hal-01099175
Contributeur : Stephane Gaubert <>
Soumis le : mercredi 31 décembre 2014 - 17:40:45
Dernière modification le : jeudi 10 mai 2018 - 02:05:48

Lien texte intégral

arxiv

Identifiants

  • HAL Id : hal-01099175, version 1
  • ARXIV : 1402.1436

Collections

X | INRIA | INSMI | X-CMAP | CMAP | TDS-MACS | PARISTECH | X-DEP-MATHA

Citation

Stéphane Gaubert, Zheng Qu, Srinivas Sridharan. Bundle-based pruning in the max-plus curse of dimensionality free method. Proceedings of the 21st International Symposium on Mathematical Theory of Networks and Systems, Jul 2014, Groningen, Netherlands. 2014, 〈https://fwn06.housing.rug.nl/mtns2014/〉. 〈hal-01099175〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

426

Contact


archive-ouverte@inria.fr