E-Book, Englisch, 624 Seiten
Sniedovich Dynamic Programming
2. Auflage 2010
ISBN: 978-1-4200-1463-1
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
Foundations and Principles, Second Edition
E-Book, Englisch, 624 Seiten
Reihe: Chapman & Hall/CRC Pure and Applied Mathematics
ISBN: 978-1-4200-1463-1
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
Incorporating a number of the author’s recent ideas and examples, Dynamic Programming: Foundations and Principles, Second Edition presents a comprehensive and rigorous treatment of dynamic programming. The author emphasizes the crucial role that modeling plays in understanding this area. He also shows how Dijkstra’s algorithm is an excellent example of a dynamic programming algorithm, despite the impression given by the computer science literature.
New to the Second Edition
- Expanded discussions of sequential decision models and the role of the state variable in modeling
- A new chapter on forward dynamic programming models
- A new chapter on the Push method that gives a dynamic programming perspective on Dijkstra’s algorithm for the shortest path problem
- A new appendix on the Corridor method
Taking into account recent developments in dynamic programming, this edition continues to provide a systematic, formal outline of Bellman’s approach to dynamic programming. It looks at dynamic programming as a problem-solving methodology, identifying its constituent components and explaining its theoretical basis for tackling problems.
Zielgruppe
Applied mathematicians; management science and operations researchers; electrical, electronic, systems, and industrial engineers; computer scientists; and advanced undergraduate and graduate students in dynamic programming.
Autoren/Hrsg.
Weitere Infos & Material
Introduction
Welcome to Dynamic Programming!
How to Read This Book
SCIENCE
Fundamentals
Introduction
Meta-Recipe Revisited
Problem Formulation
Decomposition of the Solution Set
Principle of Conditional Optimization
Conditional Problems
Optimality Equation
Solution Procedure
Time Out: Direct Enumeration!
Equivalent Conditional Problems
Modified Problems
The Role of a Decomposition Scheme
Dynamic Programming Problem — Revisited
Trivial Decomposition Scheme
Summary and a Look Ahead
Multistage Decision Model
Introduction
A Prototype Multistage Decision Model
Problem vs Problem Formulation
Policies
Markovian Policies
Remarks on the Notation
Summary
Bibliographic Notes
Dynamic Programming — An Outline
Introduction
Preliminary Analysis
Markovian Decomposition Scheme
Optimality Equation
Dynamic Programming Problems
The Final State Model
Principle of Optimality
Summary
Solution Methods
Introduction
Additive Functional Equations
Truncated Functional Equations
Nontruncated Functional Equations
Summary
Successive Approximation Methods
Introduction
Motivation
Preliminaries
Functional Equations of Type One
Functional Equations of Type Two
Truncation Method
Stationary Models
Truncation and Successive Approximation
Summary
Bibliographic Notes
Optimal Policies
Introduction
Preliminary Analysis
Truncated Functional Equations
Nontruncated Functional Equations
Successive Approximation in the Policy Space
Summary
Bibliographic Notes
The Curse of Dimensionality
Introduction
Motivation
Discrete Problems
Special Cases
Complete Enumeration
Conclusions
The Rest Is Mathematics and Experience
Introduction
Choice of Model
Dynamic Programming Models
Forward Decomposition Models
Practice What You Preach!
Computational Schemes
Applications
Dynamic Programming Software
Summary
ART
Refinements
Introduction
Weak-Markovian Condition
Markovian Formulations
Decomposition Schemes
Sequential Decision Models
Example
Shortest Path Model
The Art of Dynamic Programming Modeling
Summary
Bibliographic Notes
The State
Introduction
Preliminary Analysis
Mathematically Speaking
Decomposition Revisited
Infeasible States and Decisions
State Aggregation
Nodes as States
Multistage vs Sequential Models
Models vs Functional Equations
Easy Problems
Modeling Tips
Concluding Remarks
Summary
Parametric Schemes
Introduction
Background and Motivation
Fractional Programming Scheme
C-Programming Scheme
Lagrange Multiplier Scheme
Summary
Bibliographic Notes
The Principle of Optimality
Introduction
Bellman’s Principle of Optimality
Prevailing Interpretation
Variations on a Theme
Criticism
So What Is Amiss?
The Final State Model Revisited
Bellman’s Treatment of Dynamic Programming
Summary
Post Script: Pontryagin’s Maximum Principle
Forward Decomposition
Introduction
Function Decomposition
Initial Problem
Separable Objective Functions Revisited
Modified Problems Revisited
Backward Conditional Problems Revisited
Markovian Condition Revisited
Forward Functional Equation
Impact on the State Space
Anomaly
Pathologic Cases
Summary and Conclusions
Bibliographic Notes
Push!
Introduction
The Pull Method
The Push Method
Monotone Accumulated Return Processes
Dijkstra’s Algorithm
Summary
Bibliographic Notes
EPILOGUE
What Then Is Dynamic Programming?
Review
Non-Optimization Problems
An Abstract Dynamic Programming Model
Examples
The Towers of Hanoi Problem
Optimization-Free Dynamic Programming
Concluding Remarks
Appendix A: Contraction Mapping
Appendix B: Fractional Programming
Appendix C: Composite Concave Programming
Appendix D: The Principle of Optimality in Stochastic Processes
Appendix E: The Corridor Method
Bibliography
Index
