Stochastic Approximation Methods for the Two-Stage Stochastic Linear Complementarity Problem
针对大规模两阶段随机线性互补问题，提出两种随机逼近方法（SAP和DS-SAP），通过非精确求解子问题降低计算成本，并给出收敛性分析，数值实验验证了效率。
The two-stage stochastic linear complementarity problem (TSLCP), which can be regarded as a special and important reformulation of two-stage stochastic linear programming, has arisen in various fields, such as stochastic programming, game theory, traffic equilibrium, and theoretical economics. Considerable effort has been devoted to designing numerical methods for solving TSLCPs. A popular approach is to integrate the progressive hedging algorithm (PHA) as a sub-algorithm into a discretization framework. In this paper, aiming to solve large-scale TSLCPs, we propose two kinds of stochastic methods: the stochastic approximation method based on projection (SAP) and the dynamic sampling SAP (DS-SAP), both of which offering more direct and improved control of the computational costs of the involved subproblems, especially compared with the PHA. In particular, the linear complementarity subproblems are solved inexactly during each iteration, and the convergence analysis of both SAP and DS-SAP with an inexactness criterion is presented. Moreover, numerical implementations and practical applications demonstrate the efficiency of our proposed methods.