非时齐Markov链的收敛性

摘要

求目标函数的最小值点的问题是计算数学中的一个重要问题。用确定算法计算往往只能求出局部极小值点,而用近来迅速发展起来的随机算法,则往往能求出最小值点。模拟退火算法是一种随机算法,这种算法在本质上是构造一个收敛的非时齐马氏链,因此判别一个非时齐Markov链是否收敛是模拟退火算法的基本理论问题。当前最常用的判别定理是Dobrushin-Isaacson-Madsen定理,它给出了有限状态空间上非时齐Markov链收敛的判准。 本文的主要结果(定理3.3),用耦合的方法,给出了一个一般状态空间非时齐马氏链收敛的判准,特别是所给条件只依赖于每步的转移概率,而不依赖于该转移概率所确定的平稳分布,因此更便于在实际中的应用。

目录

文摘

英文文摘

声明

1引言

2预备知识

2.1 Markov链的概念

2.2耦合与全变差距离

3非时齐Markov链的收敛性

3.1有限状态空间的情形

3.2一般状态空间的情形

4非时齐Markov链的模拟退火算法

4.1原始的模拟退火算法

4.2加入噪声函数的模拟退火算法

结果及展望

参考文献

致谢