Algebraic decompositions of DP problems with linear dynamics
From MaRDI portal
Publication:888809
DOI10.1016/J.SYSCONLE.2015.09.001zbMATH Open1322.93026arXiv1404.5086OpenAlexW1856701599MaRDI QIDQ888809FDOQ888809
Authors: D. C. Tarraf, Manolis C. Tsakiris 
Publication date: 2 November 2015
Published in: Systems \& Control Letters (Search for Journal in Brave)
Abstract: Inspired by rational canonical forms, we introduce and analyze two decompositions of dynamic programming (DP) problems for systems with linear dynamics. Specifically, we consider both finite and infinite horizon DP problems in which the dynamics are linear, the cost function depends only on the state, and the state-space is finite dimensional but defined over an arbitrary algebraic field. Starting from the natural decomposition of the state-space into the direct sum of subspaces that are invariant under the system's linear transformation, and assuming that the cost functions exhibit an additive structure compatible with this decomposition, we extract from the original DP problem two distinct families of smaller DP problems, each associated with a system evolving on an invariant subspace of the original state-space. We propose that each of these families constitutes a decomposition of the original problem when the optimal policy and value function of the original problem can be reconstructed from the optimal policies and value functions of the individual subproblems in the family. We derive necessary and sufficient conditions for these decompositions to exist both in the finite and infinite horizon cases. We also propose a readily verifiable sufficient condition under which the first decomposition exists, and we show that the first notion of decomposition is generally stronger than the second.
Full work available at URL: https://arxiv.org/abs/1404.5086
Recommendations
- scientific article; zbMATH DE number 4025188
- scientific article; zbMATH DE number 53073
- An explicit linear solution for the quadratic dynamic programming problem
- Dynamic programming in the problem of decomposition optimization
- A Dynamic Programming Type Algorithm for Finite Decision Problems in Banach Spaces
Cites Work
- Title not available (Why is that?)
- Approximate dynamic programming. Solving the curses of dimensionality
- Optimal Control of Spatially Distributed Systems
- Distributed control of spatially invariant systems
- Distributed Control Design for Systems Interconnected Over an Arbitrary Graph
- Equivalence notions and model minimization in Markov decision processes
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- A Control-Oriented Notion of Finite State Approximation
- Distributed Control of Systems Over Discrete Groups
- A Characterization of Convex Problems in Decentralized Control$^ast$
- <formula formulatype="inline"><tex Notation="TeX">$ {\cal H}_{2}$</tex></formula>-Optimal Decentralized Control Over Posets: A State-Space Solution for State-Feedback
- Dynamic programming and decomposition approaches for the single machine total tardiness problem
- Separable Dynamic Programming and Approximate Decomposition Methods
- Stochastic dynamic programming with factored representations
- An Input-Output Construction of Finite State <inline-formula> <tex-math notation="TeX">$\rho/\mu$</tex-math></inline-formula> Approximations for Control Design
- Distributed Design Methods for Linear Quadratic Control and Their Limitations
- Finite Approximations of Switched Homogeneous Systems for Controller Synthesis
This page was built for publication: Algebraic decompositions of DP problems with linear dynamics
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q888809)
