Sequential Convex Approximation Approach To Stochastic Linear Complementarity Problems

Decades have passed since Linear Complementarity Problem (LCP) was first proposed by Cottle and Dantzig in1968. However, it has been noticed that massive practical problems with random factors involved are beyond the scope of the conventional deterministic LCP model, and an extension to the Stochastic Linear Complementarity Problem (SLCP) is necessary. Recently, the Stochastic Linear Complementarity Problem has attracted a lot of interest, and theories ex-istence and uniqueness have been developed.Inspired by the equivalence of a SLCP and a DC optimization problem and the sequential convex approximation approach to the Joint Chance Constrained Optimization Problem, devel-oped by Jeff Hong et al.[1], a kind of sequential convex approximation approach to Stochastic Linear Complementarity Problems is developed.Firstly, we reformulate the SLCP to a DC optimization with a DC objective function and linear constraints, and then apply the SAA procedure to get a new problem with r samples. We proved that the solution set of the new SAA problem converges to that of the DC optimization problem when r tends to infinity. Secondly, notice that the SAA problem is also a DC problem, and then linearize the second convex part of its problem to get a series of convex optimization problems. Thirdly, we construct a sequential convex approximation algorithm and its conver-gence theorem. Finally, we provide some concrete problems and numerical results.