基于鞅理论与统计信息的仿真优化

This research tends to improve the convergence rate as well as the quality of solution estimate in simulation optimization through martingale approach. Simulation optimization, as an integration of simulation and operations research, is an emerging branch of science with the objective of solving large scale complex problems encountered in real life. This research introduces the concept of supermartingale in simulation optimization in order to improve the transparency as well as the controllability in the search process. In addition, it aims to provide systematic and quantitative guarantee son algorithm convergence rate as well as the probability of backtracking. On the other hand, this research also targets at overcoming the weakness of the traditional estimation method which heavily depends on the sampling sequence, and improving the controllability and accuracy throughout the optimization process. This research is an integration of martingale theory and statistical estimation, and it may become a critical component that can be used to quantitatively evaluate the efficiency of optimization algorithm. This research will be conducted under the framework of nested partition with the objective of developing a novel simulation optimization approach using martingale and extreme value theory.

本课题通过鞅理论与统计分析的研究途径，对仿真优化的收敛速度及解质量估计方法进行改善。仿真优化是新近发展起来的由仿真、运筹学和优化理论等相结合而形成的以解决大规模复杂优化问题为目的的一门新兴学科。本课题拟通过在仿真优化的算法过程中引入上鞅，增加求解过程的可控性与透明度，并在收敛性、回溯概率以及收敛速率上提供系统的、定量的保证。另一方面，本课题拟结合极值理论，克服传统估计方法依赖于采样点排序的缺点，对优化过程中的解估计的可控性和准确度上进行改善。此方面研究可与鞅理论有机结合，成为量化算法效率的重要组成部分。本项目的研究将以"嵌套分割（Nested Partition）"方法为基础算法构架，结合鞅理论与极值理论，形成一整套新的仿真优化系统理论和方法。

本研究围绕仿真优化的收敛速度及解质量估计问题，结合鞅理论与统计分析，系统地研究了仿真优化取样分配的建模和分析方法，揭示了不同取样方法和仿真预算分配策略对仿真优化的收敛速度及解质量估计的影响，并提出了改善的理论和方法。针对有限资源下的仿真预算分配问题，建立了基于期望机会成本的分配模型，证明了该模型的凸优化性质，提出了最优的仿真预算分配方法，该方法不仅提供了更多的统计信息，而且由于设置了更大的惩罚系数而更加适合风险中立决策者；针对复杂系统的仿真取样问题，研究了基于多精度模型的仿真优化方法，利用高精度模型刻画实际问题，通过松弛建立相应的低精度模型，利用序优化的思想进行解空间转换，减少区间内解的方差，增大区间之间的距离，提高仿真优化的收敛速度；面向肿瘤放疗、航空维修等实际问题，建立了数学规划模型，在嵌套分割算法框架下设计了有效的求解策略，实证数据表明基于嵌套分割算法的求解策略能够提高解的质量。综上，本项目研究成果利用鞅理论与统计分析建立了有效的仿真优化取样分配策略，并结合数据进行了量化分析，在很大程度上提高了仿真优化的收敛速度和解的质量，推进和发展了仿真优化领域的研究工作，为解决不确定性环境下的优化问题提供了理论依据。