Paper Info
Title
Algebraic decompositions of DP problems with linear dynamics
Abstract
We consider Dynamic Programming (DP) problems in which the dynamics are linear, the cost is a function of the state, and the state-space is finite dimensional but defined over an arbitrary field. Starting from the natural decomposition of the state-space into a direct sum of invariant subspaces consistent with the rational canonical form, and assuming the cost functions exhibit an additive structure compatible with this decomposition, we extract from the original problem two distinct families of smaller DP problems associated with the invariant subspaces. Each family constitutes a decomposition of the original problem when the optimal policy and value function can be reconstructed from the optimal policies and value functions of the smaller problems. We derive necessary and sufficient conditions for these decompositions to exist, propose a readily verifiable sufficient condition for the first decomposition, and establish a hierarchy relating the two notions of decomposition.
Year
DOI
Venue
2015
10.1016/j.sysconle.2015.09.001
Systems & Control Letters
Keywords
Field
DocType
Dynamic programming,Decomposition,Rational canonical form
Dynamic programming,Mathematical optimization,Algebraic number,Direct sum,Canonical form,Linear subspace,Bellman equation,Verifiable secret sharing,Invariant (mathematics),Mathematics
Journal
Volume
ISSN
Citations 
85
0167-6911
0
PageRank 
References 
Authors
0.34
18
2
Name
Order
Citations
PageRank
Manolis C. Tsakiris1509.79
Danielle C. Tarraf217719.65