You are here

Dynamic Programming: Foundations and Principles

Moshe Sniedovich
Publisher: 
Chapman & Hall/CRC
Publication Date: 
2010
Number of Pages: 
604
Format: 
Hardcover
Edition: 
2
Series: 
Pure and Applied Mathematics
Price: 
169.95
ISBN: 
9780824740993
Category: 
Textbook
We do not plan to review this book.

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