关于随机对称锥互补问题及其相关课题的研究

Stochastic complementarity problems have become an attractive topic in the optimization world. As an extension, stochastic symmetric cone complementarity problems have many important applications in practice. In this project, we will focus on this new topic. Main contributions can be summarized as follows: (1) Since the stochastic symmetric cone complementarity problems may not have a common solution in general, our first task is to present some deterministic models for them. In this project, we will study two deterministic models, that is, the expected valued model and the expected residual minimization model. We will investigate their properties that are useful in algorithm design. (2) We will develop some numerical algorithms such as interior point algorithms and semismooth Newton methods based on Monte Carlo approximation techniques, descent methods based on potential functions, etc., for solving the expected valued model. We will also develop some numerical algorithms based on smoothing and Monte Carlo approximation techniques for solving the expected residual minimization model. Convergence analysis and numerical experiments will be carried out as well. (3) We will study the stochastic programming problems with symmetric cone complementarity constraints, which can be regarded as generalizations of bilevel stochastic programming problems. This kind of problems is important in theory but very difficult to solve. In this project, we will apply the Monte Carlo approximation techniques together with some smoothing or relaxation techniques and penalty function methods to develop effective algorithms for this kind of stochastic problems. Furthermore, we will establish convergence theory and make numerical experiments for the algorithms.

随机互补问题是当前优化界的研究热点之一。作为其推广，随机对称锥互补问题也具有广泛应用背景和重要研究价值。本项目拟研究这一新课题，主要内容包括：（1）由于随机对称锥互补问题一般不存在公共解，需要首先按一定准则给出其确定性模型。本项目将研究基于期望值和期望残差极小化的两个确定性模型，讨论它们的各种性质，为设计数值算法打下理论基础。（2）对于期望值模型，将开发基于蒙特卡洛近似技术的内点法与半光滑牛顿法、基于势函数的下降算法等；对于期望残差极小化模型，将开发基于光滑化与蒙特卡洛近似技术的近似算法等。进一步，将对这些算法进行收敛性分析与数值实验。（3）研究带对称锥互补约束的随机规划，该问题可视为双层随机规划的推广，具有重要研究价值，但其求解非常困难。本项目将综合运用蒙特卡洛近似技术以及光滑化或松弛化技巧、罚函数方法等设计求解该随机模型的数值算法，建立相应的收敛性理论，并利用数值实验检验算法的有效性。

本项目主要聚焦于对称锥互补问题及其广义形式、与其密切相关的互补约束优化问题的算法与应用等课题，在Mathematical Programming、European Journal of Operational Research等顶级期刊在内的核心期刊上正式发表论文24篇。主要创新性成果包括：.（1）针对对称锥互补问题，首先提出了求解确定性线性情形的一种正则化并行矩阵分裂算法以及求解非光滑情形的一种光滑化牛顿算法，并研究了这些算法的收敛性与超线性收敛速度等。其次，研究了随机二阶锥互补问题的期望残差最小化模型与期望值模型，讨论了这些模型的水平集有界性、误差界条件、以及强制性与鲁棒性等性质。再次，研究了求解随机模型的并行矩阵分裂算法、基于蒙特卡洛技术的近似算法等，建立了相应的收敛性理论。.（2）针对一般形式的随机互补问题，提出了一种基于蒙特卡洛技术的内点算法, 该算法由内循环和外循环构成，在适当条件下该算法的内循环和外循环均具有全局收敛性。.（3）针对随机变分不等式问题，提出了一系列投影型随机近似算法（不可行投影算法、方差下降修正向前-向后算法、方差下降次梯度外梯度算法等），与同类算法相比，这些算法的共同特征是在保持每次迭代只做一次投影的前提下具有更弱的收敛性条件和类似的收敛速度和复杂度。.（4）针对互补约束优化问题，首先将单目标情形的十余种约束规范条件推广到了多目标情形，讨论了相互之间的强弱关系，并研究了Pareto意义下的最优性条件。然后，提出了光滑化部分精确罚函数方法、增广拉格朗日方法、光滑化样本平均逼近方法等，并建立了相应的收敛性理论。.（5）研究了上述几类问题在能源市场（最优潮流问题、天然气输送问题）、供应链管理（混合渠道供应链网络优化问题、闭环供应链回收渠道选择问题）、交通规划（城市交通流量分配问题、民航与高铁竞合博弈问题、海运航速优化和燃料补给问题）等领域的应用。