# Dynamic Programming

## Foundations and Principles, Second Edition

#### By **Moshe Sniedovich**

#### Series Editor: **Zuhair Nashed**, **Earl Taft**

CRC Press – 2010 – 624 pages

CRC Press – 2010 – 624 pages

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.

**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**

**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