摄动马尔可夫决策与哈密尔顿圈

总序

前言

主要符号表

第一部分马氏决策过程与摄动

第1章绪论

1.1序列决策模型

1.2马氏决策过程的例子

1.3马氏决策过程的定义与记号

1.3.1决策时刻与周期

1.3.2状态与行动集

1.3.3转移概率和报酬

1.3.4历史、决策规则与策略

1.3.5诱导过程、效用准则与马氏策略优势

1.4马氏决策过程的起源和发展

第2章有限阶段模型

2.1最优准则

2.2有限阶段的策略迭代和最优方程

2.3最优策略的存在性和算法

2.4最优策略的结构

2.5单调策略的最优性

第3章无限阶段折扣模型

3.1最优准则

3.2最优方程

3.3最优策略的存在性

3.4策略迭代算法

3.5值迭代算法

3.6改进的策略迭代算法

3.7线性规划算法

3.8最优单调策略

3.9最优策略的结构

第4章无限阶段平均模型

4.1最优准则

4.2最优平稳策略的存在性

4.3平稳策略的一些特征

4.4最优方程与策略迭代算法

4.5单链的线性规划与相关问题

4.5.1极限平均频率

4.5.2带约束模型问题

4.5.3方差问题

4.6多链的线性规划与相关问题

4.6.1对偶可行解与随机平稳策略

4.6.2基本可行解与确定性决策规则

4.6.3最优解与最优策略

4.7平均准则下的Bellman最优原则

第5章摄动MDP

5.1预备知识

5.2一些基本记号和定义

5.3摄动平均问题的渐进性和极限控制原则

5.4折扣准则的摄动问题

5.5一般的摄动

5.6单摄动极限平均MDP的算法

5.6.1假设与渐进性质

5.6.2数学规划和极限马尔可夫决策问题

5.6.3聚合一分解算法

5.7进一步的研究进展

5.7.1折扣权重摄动模型

5.7.2折扣平均权重摄动问题

第二部分摄动MDP与哈密尔顿圈

第6章HC与MDP

6.1哈密尔顿圈问题

6.2有向图到MDP的嵌入

6.3平稳策略的分类

6.4约束折扣MDP与HC

6.5约束折扣MDP的求解

6.6HC与TSP

第7章HCP嵌入MDP的摄动

7.1转移概率的摄动

7.1.1转移概率的对称线性摄动

7.1.2转移概率的非对称线性摄动

7.1.3转移概率的非对称二次摄动

7.2摄动下子图的稳态分布

7.3非对称线性摄动下的几个例子

7.4非对称线性摄动下HC的性质

7.5更为精细的分析

7.6开问题和有关猜想

第8章频率空间上的分析

8.1长期平均MDP频率空间中的HCP

8.2二次非对称摄动与新目标函数

8.3启发式内点算法

8.3.1内点算法简介

8.3.2关于(QP)求解的启发式算法

8.3.3数值计算例子

8.4一些开问题及其他

第9章双随机摄动与HC

9.1基本矩阵

9.2再谈双随机摄动

9.3渐进表达式

9.4优化问题与HC的全局最优性

9.4.1非线性规划问题

9.4.2方向导数

9.4.3HC既是局部也是全局最小

9.5哈密尔顿间隙

9.6对称双随机矩阵的探讨

9.7混合时间及其变化的最小化

9.7.1从不可约链到一般的情形

9.7.2迹与对角线上的元素

9.7.3摄动带来的好处

9.7.4带有对称线性摄动的双随机矩阵

第10章将来的研究方向和结束语

10.1将来的研究方向

10.2结束语

参考文献

索引

　　本书主要介绍了两个方面的研究工作：一个是马氏决策过程的理论及其摄动问题。在介绍了一般的马氏决策过程理论模型之后，本书还介绍了一些最新的相关进展。特别的，本书专门介绍马氏决策过程的摄动问题。　　另一方面的工作就是将离散数学中的一类经典问题，诸如哈密尔顿圈问题、旅行商问题等等嵌入到凸域上的、可处理的分析问题中去，使得问题可能得到解决。很明显，这些经典问题的主要困难是来自于问题定义域的离散性。将原始的确定性问题的关键元素赋予概率解释之后，就可以获得扩展解域的凸化结构。以哈密尔顿圈问题或者旅行商问题为例，可以建立一种技术将其嵌入到单摄动的马氏决策过程中去。其主要思想就是将子图解释为由确定性策略(如果有，就包含哈密尔顿圈)为顶点所构成的凸多面体空间中的元素，即为随机平稳策略所对应。　　本书主要从理论和算法两个方面着手考虑哈密尔顿圈或者旅行商问题，揭示了图论的理论结构、概率代数和相应的马尔可夫链之间的一些关系，包括首次返回时间的矩、访问节点的极限频率、用于分析马尔可夫链的某些矩阵的谱等等。本书还列出了一些尚未解决的开问题，以供读者欣赏和研究。　　马氏决策过程是一个非常有用的决策分析工具，已经成功的用于解决很多实际问题。利用马氏决策过程的建模思想，可以将一些离散数学中的传统问题描述为特殊的马氏决策过程加以考虑。通过优化这些特殊的马氏决策过程，不仅可以为解决这些传统问题提供新的思路，而且还可以促进马氏决策过程本身理论的发展。但是，在研究这类特殊马氏决策过程时，只有引入摄动因素才能有效的处理问题，所以我们还介绍了马氏决策的摄动理论。本书的内容包括一些基本的马氏决策过程知识，主要集中在有限状态和有限行动的马氏决策过程上。然后介绍了有关马氏决策过程的摄动理论。最后，利用前面的内容，比较详细的介绍了摄动马氏决策与哈密尔顿圈之间的关系和近些年的最新研究成果，提出了一些这个领域里人们现在最为感兴趣的研究问题。　　本书适用于三种读者，一个是希望利用马氏决策过程建立有效的模型来分析决策行为的读者，通过前四章的阅读可以了解基本的分析工具，后面的阅读可以使读者获得建立具体模型并进行分析的一些技巧；二是为希望利用这个随机优化的工具研究离散数学或者其他相关科学里的问题的读者提供思路；最后，对于希望发展马氏决策过程理论的读者，可以了解这方面的动态，尽快介入这方面的前沿研究领域。