情景树生成与约简的实用有效算法

Due to its flexibility and manipuility, scenario tree has become a powerful tool for describing uncertain parameters in uncertain decision-making problems. Since they did not coordinate key issues such as the fitting accuracy, the scenario tree’s structure and the speed of scenario tree generation, current scenario tree generation or reduction algorithms cannot realistically describe the stochastic parameter process in multi-stage stochastic programming problems in practice because of the “curse of dimensionality”. This problem has become a crucial problem to be solved urgently and has attracted scholars in fields such as operations research. This project introduces several new scenario tree generation or reduction algorithms by properly dealing with issues like the time series model selection to describe the stochastic parameter process, the estimate of distributional properties and process parameters and the new measure of the distance between two scenario trees. The proposed new algorithms are easy to implement, efficient in computational amount, and have high approximation accuracy, they overcome the fatal weakness of existing methods which only satisfy one of above desirable properties. By sufficiently utilizing modern optimization techniques such as cone programming, non-convex optimization, we skillfully break through several technical bottlenecks restricting the efficient solution of complex optimization problems encountered during the scenario tree generation or reduction. This project will provide efficient strategies to transfer multi-stage uncertain programs into deterministic optimization problems, solve the real solvability problem of the original complex decision-making problem, and eliminate the gap between the theoretical research and practical application. Our research will enhance the algorithm development for stochastic optimization and its application in many fields such as the medium and long term optimal investment strategy selection.

情景树因其灵活性与可操作性，现已成为描述不确定决策问题中不确定参数的强有力工具。因未能协调解决拟合精度、情景树结构、情景树生成速度等关键问题，现有情景树生成与约减算法因“维度灾难”无法真正用于描述实际中多阶段随机规划问题中的随机系数过程，这已成为亟待解决的难题而倍受运筹学和众多应用领域学者的关注。本项目将通过探讨描述随机系数过程的模型选择、分布特征与参数估计、情景树之间距离的新度量等新途径来设计数个易于实现、计算量小、逼近精度高的情景树生成或约减算法，克服现有方法仅满足某单一要求的弱点；综合运用锥规划、非凸优化等现代优化技术，巧妙突破制约有效求解情景树构造过程中所遇到复杂优化问题的多个技术瓶颈。项目研究将给出多阶段不确定规划的有效确定化策略，解决原复杂决策问题的现实可解性问题，消除理论研究与实际应用的差距，并带动随机优化求解算法设计及其在寻求中长期最优投资策略等领域中的应用的发展。

能按研究计划开展工作，较好地完成了预期研究任务。所取得的主要研究成果如下：在探讨如何更好地刻画随机参数过程特性的基础上，设计了两类情景树生成的新算法；通过引入易于计算的距离函数来度量两个情景树之间的距离以及对应随机过程收敛的新判据，设计出了两类有理论支撑的情景树约减算法，进而对其进行改进，确保其应用于多阶段投资策略选择时可保证无套利机会；充分利用所研发的新型情景树生成或约减算法，构造了满足不同类型金融投资问题特性的情景树，再结合近代优化方法，设计了求解相应多期金融优化问题的实用有效算法；对更一般的多阶段随机规划问题、新型随机优化问题开展了定量稳定性等理论研究，为设计更好的情景树生成算法、约减算法提供了有力支撑；最后，我们还就超效率评价方法、基金绩效评价的多期网络DEA模型等复杂决策问题,以及随机优化方法在制定养老金计划、保险与再保险策略等领域的应用开展了研究。