ERM Reformulation for Stochastic Horizontal Linear Complementarity Problems: Convergence Analysis and a Gradient Algorithm

This paper investigates the stochastic horizontal linear complementarity problem (S-HLCP). By employing a complementarity function, we reformulate the S-HLCP as an expected residual minimization (ERM) problem. We first establish sufficient conditions based on the R0-matrix property to ensure the coercivity of the ERM problem. The sample average approximation (SAA) method is then employed to handle the expected value in the ERM formulation. We prove that both optimal solutions and stationary points of the SAA problem converge to their true counterparts with probability one. Moreover, we demonstrate that the optimal solutions of the ERM problem possess a robustness property. Finally, we propose a globally convergent gradient method and present two numerical examples and a traffic equilibrium problem under uncertainty to illustrate its effectiveness.