Skip to Content

Dynamic Programming

Foundations and Principles, Second Edition

By Moshe Sniedovich

Series Editor: Zuhair Nashed, Earl Taft

CRC Press – 2010 – 624 pages

Series: Chapman & Hall/CRC Pure and Applied Mathematics

Purchasing Options:

  • Add to CartHardback: $199.95
    978-0-8247-4099-3
    September 9th 2010

Description

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.

Contents

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

Author Bio

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.

Name: Dynamic Programming: Foundations and Principles, Second Edition (eBook)CRC Press 
Description: By Moshe SniedovichSeries Editor: Zuhair Nashed, Earl Taft. 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...
Categories: Operations Research, Operations Research