STOCHASTIC APPROXIMATION METHODS FOR THE TWO-STAGE STOCHASTIC LINEAR COMPLEMENTARITY PROBLEM

Chen，Lin1,2; Liu，Yongchao3; Yang，Xinmin1,4; Zhang，Jin5

2022

10.1137/20M1375796

SIAM JOURNAL ON OPTIMIZATION   Impact Factor & Quartile

1052-6234

1095-7189

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 subalgorithm 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.

convergence analysis dynamic sampling projection method stochastic approximation two-stage stochastic linear complementarity problem

SCI

English

Others

National Science Foundation of China["11971090","11971220","11991023","11991024","12171063","12101097","12222106"] ; Natural Science Foundation of Chongqing["cstc2019jcyj-zdxmX0016","cstc2021jcyj-msxmX0047"] ; Project for Creative Research Groups in Chongqing[CXQT20014] ; Project for Chongqing Talent Plan[CQYC20210302270] ; Guangdong Basic and Applied Basic Research Foundation[2022B1515020082] ; Shenzhen Science and Technology Program[RCYX20200714114700072]

Mathematics

Mathematics, Applied

WOS:000877314900018

SIAM PUBLICATIONS

MATHEMATICS

2-s2.0-85140017877

Scopus

1.School of Mathematical Sciences,Chongqing Normal University,Chongqing,China
2.School of Mathematical Sciences,University of Electronic Science and Technology of China,Chengdu,Sichuan,China
3.School of Mathematical Sciences,Dalian University of Technology,Dalian,Liaoning,China
4.National Center for Applied Mathematics Chongqing,Chongqing Normal University,Chongqing,China
5.Department of Mathematics,SUSTech International Center for Mathematics,Southern University of Science and Technology,National Center for Applied Mathematics Shenzhen,Guangdong,China

Chen，Lin,Liu，Yongchao,Yang，Xinmin,et al. STOCHASTIC APPROXIMATION METHODS FOR THE TWO-STAGE STOCHASTIC LINEAR COMPLEMENTARITY PROBLEM[J]. SIAM JOURNAL ON OPTIMIZATION,2022,32(3):2129-2155.

Chen，Lin,Liu，Yongchao,Yang，Xinmin,&Zhang，Jin.(2022).STOCHASTIC APPROXIMATION METHODS FOR THE TWO-STAGE STOCHASTIC LINEAR COMPLEMENTARITY PROBLEM.SIAM JOURNAL ON OPTIMIZATION,32(3),2129-2155.

Chen，Lin,et al."STOCHASTIC APPROXIMATION METHODS FOR THE TWO-STAGE STOCHASTIC LINEAR COMPLEMENTARITY PROBLEM".SIAM JOURNAL ON OPTIMIZATION 32.3(2022):2129-2155.