Paper Info
Title
On subspace decompositions of finite horizon dynamic programming problems
Abstract
We consider finite horizon dynamic programming problems where the dynamics are linear over a finite dimensional state-space and where the cost function depends only on the state. Starting from a decomposition of the state-space under the relevant linear transformation, we derive conditions under which the dynamic programming problem decomposes into a set of smaller problems that can be solved independently, with their combined solutions yielding the optimal solution of the original problem. For linear systems over finite fields, we show that the resulting reduction in complexity is exponential.
Year
DOI
Venue
2012
10.1109/CDC.2012.6427001
Decision and Control
Keywords
DocType
ISSN
computational complexity,dynamic programming,complexity reduction,cost function,finite dimensional state-space,finite horizon dynamic programming problems,linear transformation,subspace decompositions
Conference
0743-1546 E-ISBN : 978-1-4673-2064-1
ISBN
Citations 
PageRank 
978-1-4673-2064-1
2
0.39
References 
Authors
6
2
Name
Order
Citations
PageRank
Manolis C. Tsakiris1509.79
Danielle C. Tarraf217719.65