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

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.
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 : mercredi 14 novembre 2018 - 15:20:11

Lien texte intégral

Identifiants

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

Collections

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〉

Partager

Métriques

Consultations de la notice

443