Fast Approximate Dynamic Programming for Input-Affine Dynamics

M.A. Sharifi Kolarijani*, P. M. Esfahani

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

4 Downloads (Pure)


We propose two novel numerical schemes for the approximate implementation of the dynamic programming (DP) operation concerned with finite-horizon optimal control of discrete-time systems with input-affine dynamics. The proposed algorithms involve discretization of the state and input spaces and are based on an alternative path that solves the dual problem corresponding to the DP operation. We provide error bounds for the proposed algorithms, along with a detailed analysis of their computational complexity. In particular, for a specific class of problems with separable data in the state and input variables, the proposed approach can reduce the typical time complexity of the DP operation from O(XU) to O(X+U) , where X and U denote the size of the discrete state and input spaces, respectively. This reduction in complexity is achieved by an algorithmic transformation of the minimization in DP operation to an addition via discrete conjugation.
Original languageEnglish
Pages (from-to)6315-6322
JournalIEEE Transactions on Automatic Control
Issue number10
Publication statusPublished - 2023

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.


Dive into the research topics of 'Fast Approximate Dynamic Programming for Input-Affine Dynamics'. Together they form a unique fingerprint.

Cite this