Sniedovich Dynamic Programming

Foundations and Principles, Second Edition
2. Auflage 2010
ISBN: 978-1-4200-1463-1
Verlag: Taylor & Francis
Format: PDF
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)

E-Book, Englisch, 624 Seiten

Reihe: Chapman & Hall/CRC Pure and Applied Mathematics

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.

Sniedovich, Moshe

Fachgebiete

• Mathematik | Informatik Mathematik Operations Research

Inhaltsverzeichnis

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

Über Autor(innen)

Moshe Sniedovich is a Principal Fellow (Associate) in the Department of Mathematics and Statistics at the University of Melbourne in Australia. Dr. Sniedovich has worked at the Israel Ministry of Agriculture, University of Arizona, Princeton University, IBM TJ Watson Research Center, and South Africa National Research Institute for Mathematical Sciences. He earned his B.Sc. from Technion and his Ph.D. from the University of Arizona.