Fast Dynamic Programming

Fast Dynamic Programming: A Numerical Method for Solving Dynamic Programming Problems

Max, Gyula (TU Delft Electrical Engineering, Mathematics and Computer Science)

Keviczky, Tamas (mentor)
Mohajerin Esfahani, Peyman (mentor)
Sharifi Kolarijani, Amin (graduation committee)
van der Veen, Alle-Jan (graduation committee)

Delft University of Technology

Electrical Engineering

2019-11-27

A well-established method for finding the optimal control policy for a given dynamical system is to solve the problem iteratively going from its terminal state "backwards" in time, known as Dynamic Programming Algorithm. For a generic problem with discrete state/action space, the algorithm has computational complexity of O(NM) for N states and M actions. In this thesis, we propose a novel numerical algorithm that approaches this problem in the conjugate domain, using the so-called Legendre-Fenchel Transform. In essence, the proposed approach is analogous to, and was inspired by Fast Fourier Transform, and how it can be beneficial to do computations/analysis in the frequency domain. In particular, this approach allows us to exploit the structure of the problem (e.g., in LQ control) to drastically reduce the computational complexity to O(N+M). Of course, this computational gain comes with a cost of introducing error.

Dynamic Programming
optimal control
Legendre-Fenchel Transform
convex conjugate
optimization
convex optimization
Fast Fourier Transformation
numerical method

http://resolver.tudelft.nl/uuid:424dc384-92b5-4cb6-8392-1f9739d5075d

Student theses

master thesis

© 2019 Gyula Max