抽象动态规划

1. Introduction

1.1 Structurc of Dynamic Programming Problems

1.2. Abstract Dynamic Programming Moclels

1.2.1. Problem Formulation

1.2.2. Monotonicity and Contraction Assumptions

1.2.3. Some Examples

1.2.4. Approximation-Related Mappings

1.3. Organization of the Book

1.4. Notes. Sources. and Exercises

2. Contractive Models

2.1. Fixed Point Equation and Optimality Conditions

2.2. Limited Lookahead Policies

2.3. Value Iteration.

2.3.1. Approximate Value Iteration

2.4. Policy Iteration

2.4.1. Approximate Policy Iteration

2.5. Optimistic Policy Iteration

2.5.1. Convergence of Optimistic Policy Iteration

2.5.2. Approximate Optimistic Policy Iteration

2.6. Asynchronous Algorithms

2.6.1. Asynchronous Value Iteration

2.6.2. Asynchronous Policy Iteration

2.6.3. Policy Iteration with a Uniform Fixed Point

2.7. Notes. Sources， and Excrcises

3. Semicontractive Models

3.1. Semicontractive Models and Regular Policies

3.1.1. Fixed Points， Optimality Conditions， and Algorithmic Results

3.1.2. Illustrative Example： Deterministic Shortest Path Problems

3.2. Irregular Policies and a Perturbation Approach

3.2.1. The Casc Where Irregular Policies Have Infinite Cost

3.2.2. The Case Where Irregular Policies Have Finite Cost Perturbations

3.3. Algorithms

3.3.1. Asynchronous Value Iteration.

3.3.2. Asynchronous Policy Iteration.

3.3.3. Policy Iteration with Perturbations

3.4. Notes. Sources. and Exercises

4. Noncontractive Models

4.1. Noncontractive Models

4.2. Finite Horizon Problems

4.3. Infinite Horizon Problems

4.3.1. Fixed Point Properties and Optimality Conditions

4.3.2. Value Iteration

4.3.3. Policy Iteration

4.4. Semicontractive-Monotone Increasing Models

4.4.1. Value and Policy Iteration Algorithms

4.4.2. Some Applications

4.4.3. Linear-Quadratic Problems

4.5. Affine Monotonic Models

4.5.1. Increasing Affine Monotonic Models

4.5.2. Nonincreasing Affine Monotonic Models

4.5.3. Exponential Cost Stochastic Shortest PathProblems

4.6. An Overview of Semicontractive Models and Results

4.7. Notes. Sources. and Exercises

5. Models with Restricted Policies

5.1. A Framework for Restricted Policies

5.1.1. General Assumptions

5.2. Finite Horizon Problems

5.3. Contractive Models

5.4. Borel Space Models

5.5. Notes. Sources. and Exercises

Appendix A： Notation and Mathematical Conventions

Appendix B： Contraction Mappings

Appendix C： Measure Theoretic Issues

Appendix D： Solutions of Exercises

References

Index

《抽象动态规划/国际知名大学原版教材·信息技术学科与电气工程学科系列》采用一种简洁的方式介绍动态规划的理论和方法。作者首先把动态规划的核心问题表述为一类抽象映射的不动点问题；然后将决定不动点问题求解难度的主要因素概括为上述抽象映射的两个性质：单调性和压缩性；接着在假设单调性始终成立的前提下．围绕压缩性是否成立，顺序讨论了各种典型情况下相应不动点问题的主要性质和求解方法。其中第2章介绍压缩性成立时的结果．第3章介绍压缩性部分成立时的结果，第4章介绍压缩性不成立时的结果．最后在第5章介绍了策略受限情况的一些结果。这些内容涉及不动点的存在性、值迭代方法和策略迭代方法的收敛性以及多种常用近似方法的误差上界等动态规划的基本问题。 　　《抽象动态规划/国际知名大学原版教材·信息技术学科与电气工程学科系列》作者是美国麻省理工学院电气工程和计算机科学系的资深教授，在线性规划、非线性规划、动态规划、网络优化、凸分析与优化等众多优化领域著有十余部专著或教科书。如同作者其他著作一样．《抽象动态规划/国际知名大学原版教材·信息技术学科与电气工程学科系列》在描述问题、定义概念和证明定理时力求清晰、严谨和完整。尽管《抽象动态规划/国际知名大学原版教材·信息技术学科与电气工程学科系列》始终以不动点问题为讨论对象．但每部分内容都给出了相应的动态规划实例。结合这些例子．很容易理解所获得的结果和动态规划问题的关系。因此，对于具有一定数学基础的读者，既可以把《抽象动态规划/国际知名大学原版教材·信息技术学科与电气工程学科系列》作为深入了解动态规划理论的专著．也可以将其作为自学动态规划知识的教材。 　　动态规划是解决复杂优化问题的一种基本方法。同线性规划、非线性规划、网络优化等其他优化领域的基本理论相比，应用动态规划方法解决优化问题的原理相对而言比较简单。但对同样的问题，采用不同的建模和求解策略，所产生的实际效果可能存在很大差异。因此，采用动态规划方法解决具体问题时具有很大的灵活性。通过阅读《抽象动态规划/国际知名大学原版教材·信息技术学科与电气工程学科系列》，系统掌握动态规划的核心理论和方法，对于更好地应用动态规划思想和方法解决实际问题，一定大有裨益。