File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: A max-plus based randomized algorithm for solving a class of HJB PDEs

TitleA max-plus based randomized algorithm for solving a class of HJB PDEs
Authors
Issue Date2014
Citation
Proceedings of the IEEE Conference on Decision and Control, 2014, v. 2015-February, n. February, p. 1575-1580 How to Cite?
Abstract© 2014 IEEE. McEneaney introduced the curse of dimensionality free method for the special class of infinite horizon optimal control problems where the Hamiltonian is represented as a maximum of quadratic affine functions. This method is featured by its cubic complexity with respect to the state space dimension, but the number of basis functions is multiplied by the number of switches at each iteration, referred to as the 'curse of complexity'. In previous works, an SDP-based pruning technique was incorporated into the method in order to reduce the curse of complexity. Its efficiency was proved on many examples. In this paper we develop a new max-plus based randomized algorithm to solve the same class of infinite horizon optimal control problems. The major difference between the new algorithm and the previous SDP-based curse of dimensionality free method is that, instead of adding a large number of functions and then pruning the less useful ones, the new algorithm finds in cheap computation time (linear in the current number of basis functions), by a randomized procedure, useful quadratic functions and adds only those functions to the set of basis functions. Experimental results show that the max-plus randomized algorithm can reach the same precision order obtained by the SDP-based method with a speedup varying from 10 up to 100 and that the maximal precision order attainable by the new algorithm is much better than what can be done by the SDP-based algorithm in reasonable computation time. Besides, with the randomized algorithm we are now able to tackle switched problems with more number of switches, which will allow us to extend the algorithm to more general classes of optimal control problems.
Persistent Identifierhttp://hdl.handle.net/10722/219789
ISSN

 

DC FieldValueLanguage
dc.contributor.authorQu, Zheng-
dc.date.accessioned2015-09-23T02:57:57Z-
dc.date.available2015-09-23T02:57:57Z-
dc.date.issued2014-
dc.identifier.citationProceedings of the IEEE Conference on Decision and Control, 2014, v. 2015-February, n. February, p. 1575-1580-
dc.identifier.issn0743-1546-
dc.identifier.urihttp://hdl.handle.net/10722/219789-
dc.description.abstract© 2014 IEEE. McEneaney introduced the curse of dimensionality free method for the special class of infinite horizon optimal control problems where the Hamiltonian is represented as a maximum of quadratic affine functions. This method is featured by its cubic complexity with respect to the state space dimension, but the number of basis functions is multiplied by the number of switches at each iteration, referred to as the 'curse of complexity'. In previous works, an SDP-based pruning technique was incorporated into the method in order to reduce the curse of complexity. Its efficiency was proved on many examples. In this paper we develop a new max-plus based randomized algorithm to solve the same class of infinite horizon optimal control problems. The major difference between the new algorithm and the previous SDP-based curse of dimensionality free method is that, instead of adding a large number of functions and then pruning the less useful ones, the new algorithm finds in cheap computation time (linear in the current number of basis functions), by a randomized procedure, useful quadratic functions and adds only those functions to the set of basis functions. Experimental results show that the max-plus randomized algorithm can reach the same precision order obtained by the SDP-based method with a speedup varying from 10 up to 100 and that the maximal precision order attainable by the new algorithm is much better than what can be done by the SDP-based algorithm in reasonable computation time. Besides, with the randomized algorithm we are now able to tackle switched problems with more number of switches, which will allow us to extend the algorithm to more general classes of optimal control problems.-
dc.languageeng-
dc.relation.ispartofProceedings of the IEEE Conference on Decision and Control-
dc.titleA max-plus based randomized algorithm for solving a class of HJB PDEs-
dc.typeConference_Paper-
dc.description.natureLink_to_subscribed_fulltext-
dc.identifier.doi10.1109/CDC.2014.7039624-
dc.identifier.scopuseid_2-s2.0-84931829364-
dc.identifier.volume2015-February-
dc.identifier.issueFebruary-
dc.identifier.spage1575-
dc.identifier.epage1580-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats