HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Contributor : Stephane Gaubert Connect in order to contact the contributor
Submitted on : Wednesday, December 31, 2014 - 5:40:45 PM
Last modification on : Thursday, January 20, 2022 - 5:28:50 PM

Links full text


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



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. ⟨hal-01099175⟩



Record views