Algebraic decompositions of DP problems with linear dynamics

DOI10.1016/J.SYSCONLE.2015.09.001MaRDI QIDQ888809zbMATH OpenOpenAlexFDO

Authors D. C. Tarraf, Manolis C. Tsakiris

Publication date 2 November 2015

Published in Systems \& Control Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.5086

zbMATH Keywords

decompositiondynamic programmingrational canonical form

Mathematics Subject Classification ID

Dynamic programming in optimal control and differential games (49L20) Canonical structure (93B10)

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.

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

• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• <formula formulatype="inline"><tex Notation="TeX">$ {\cal H}_{2}$</tex></formula>-Optimal Decentralized Control Over Posets: A State-Space Solution for State-Feedback
• A Characterization of Convex Problems in Decentralized Control$^ast$
• A Control-Oriented Notion of Finite State Approximation
• An Input-Output Construction of Finite State <inline-formula> <tex-math notation="TeX">$\rho/\mu$</tex-math></inline-formula> Approximations for Control Design
• Approximate dynamic programming. Solving the curses of dimensionality
• Distributed Control Design for Systems Interconnected Over an Arbitrary Graph
• Distributed Control of Systems Over Discrete Groups
• Distributed Design Methods for Linear Quadratic Control and Their Limitations
• Distributed control of spatially invariant systems
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Dynamic programming and decomposition approaches for the single machine total tardiness problem
• Equivalence notions and model minimization in Markov decision processes
• Finite Approximations of Switched Homogeneous Systems for Controller Synthesis
• Optimal Control of Spatially Distributed Systems
• Separable Dynamic Programming and Approximate Decomposition Methods
• Stochastic dynamic programming with factored representations

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)