[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Stochastic Approximation Methods for the Two-Stage Stochastic Linear Complementarity Problem

Published: 01 January 2022 Publication History

Abstract

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.

References

[1]
X. Chen and M. Fukushima, Expected residual minimization method for stochastic linear complementarity problems, Math. Oper. Res., 30 (2005), pp. 1022--1038.
[2]
X. Chen, T. K. Pong, and R. J. Wets, Two-stage stochastic variational inequalities: An ERM-solution procedure, Math. Program., 165 (2017), pp. 71--111.
[3]
X. Chen, H. Sun, and H. Xu, Discrete approximation of two-stage stochastic and distributionally robust linear complementarity problems, Math. Program., 177 (2019), pp. 255--289.
[4]
X. Chen, R. J.-B. Wets, and Y. Zhang, Stochastic variational inequalities: Residual minimization smoothing sample average approximations, SIAM J. Optim., 22 (2012), pp. 649--673.
[5]
X. Chen and S. Xiang, Computation of error bounds for P-matrix linear complementarity problems, Math. Program., 106 (2006), pp. 513--525.
[6]
X. Chen and S. Xiang, Newton iterations in implicit time-stepping scheme for differential linear complementarity systems, Math. Program., 138 (2013), pp. 579--606.
[7]
Y. Chen, G. Lan, and Y. Ouyang, Accelerated schemes for a class of variational inequalities, Math. Program., 165 (2017), pp. 113--149.
[8]
F. H. Clarke, Optimization and Nonsmooth Analysis, SIAM, Philadelphia, 1990.
[9]
S. Cui and U. V. Shanbhag, On the analysis of reflected gradient and splitting methods for monotone stochastic variational inequality problems, in Proceedings of the IEEE 55th Conference on Decision and Control, IEEE, 2016, pp. 4510--4515.
[10]
F. Facchinei and J.-S. Pang, Finite-dimensional Variational Inequalities and Complementarity Problems, Springer, New York, 2007.
[11]
S. Ghadimi, G. Lan, and H. Zhang, Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization, Math. Program., 155 (2016), pp. 267--305.
[12]
G. Gürkan, A. Yonca Özge, and S. M. Robinson, Sample-path solution of stochastic variational inequalities., Math. Program., 84 (1999), pp. 313--333.
[13]
A. N. Iusem, A. Jofré, R. I. Oliveira, and P. Thompson, Extragradient method with variance reduction for stochastic variational inequalities, SIAM J. Optim., 27 (2017), pp. 686--724.
[14]
H. Jiang and H. Xu, Stochastic approximation approaches to the stochastic variational inequality problem, IEEE Trans. Automat. Control, 53 (2008), pp. 1462--1475.
[15]
A. Jofré and P. Thompson, On variance reduction for stochastic smooth convex optimization with multiplicative noise, Math. Program., 174 (2019), pp. 253--292.
[16]
R. Johnson and T. Zhang, Accelerating stochastic gradient descent using predictive variance reduction, in Advances in Neural Information Processing Systems 26 (NIPS 2013), Curran Associates, Red Hook, NY, 2013, pp. 315--323.
[17]
H. Robbins and S. Monro, A stochastic approximation method, Ann. Math. Statist., 22 (1951), pp. 400--407.
[18]
H. Robbins and D. Siegmund, A convergence theorem for nonnegative almost supermartingales and some applications, in Optimizing Methods in Statistics, J. S. Rustagi, ed., Elsevier, New York, 1971, pp. 233--257.
[19]
R. T. Rockafellar and J. Sun, Solving monotone stochastic variational inequalities and complementarity problems by progressive hedging, Math. Program., 174 (2019), pp. 453--471.
[20]
R. T. Rockafellar and R. J.-B. Wets, Scenarios and policy aggregation in optimization under uncertainty, Math. Oper. Res., 16 (1991), pp. 119--147.
[21]
R. T. Rockafellar and R. J.-B. Wets, Stochastic variational inequalities: Single-stage to multistage, Math. Program., 165 (2017), pp. 331--360.
[22]
A. Shapiro, D. Dentcheva, and A. Ruszczyński, Lectures on Stochastic Programming: Modeling and Theory, SIAM, Philadelphia, 2014.
[23]
F. Yousefian, A. Nedić, and U. V. Shanbhag, On stochastic mirror-prox algorithms for stochastic cartesian variational inequalities: Randomized block coordinate and optimal averaging schemes, Set-Valued Var. Anal., 26 (2018), pp. 789--819.
[24]
M. Zhang, J. Sun, and H. Xu, Two-stage quadratic games under uncertainty and their solution by progressive hedging algorithms, SIAM J. Optim., 29 (2019), pp. 1799--1818.

Cited By

View all
  • (2024)Dynamic stochastic projection method for multistage stochastic variational inequalitiesComputational Optimization and Applications10.1007/s10589-024-00594-489:2(485-516)Online publication date: 1-Nov-2024

Index Terms

  1. Stochastic Approximation Methods for the Two-Stage Stochastic Linear Complementarity Problem
        Index terms have been assigned to the content through auto-classification.

        Recommendations

        Comments

        Please enable JavaScript to view thecomments powered by Disqus.

        Information & Contributors

        Information

        Published In

        cover image SIAM Journal on Optimization
        SIAM Journal on Optimization  Volume 32, Issue 3
        Sep 2022
        791 pages
        ISSN:1052-6234
        DOI:10.1137/sjope8.32.3
        Issue’s Table of Contents

        Publisher

        Society for Industrial and Applied Mathematics

        United States

        Publication History

        Published: 01 January 2022

        Author Tags

        1. two-stage stochastic linear complementarity problem
        2. stochastic approximation
        3. projection method
        4. dynamic sampling
        5. convergence analysis

        Author Tags

        1. 90C15
        2. 90C33

        Qualifiers

        • Research-article

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • Downloads (Last 12 months)0
        • Downloads (Last 6 weeks)0
        Reflects downloads up to 14 Dec 2024

        Other Metrics

        Citations

        Cited By

        View all
        • (2024)Dynamic stochastic projection method for multistage stochastic variational inequalitiesComputational Optimization and Applications10.1007/s10589-024-00594-489:2(485-516)Online publication date: 1-Nov-2024

        View Options

        View options

        Media

        Figures

        Other

        Tables

        Share

        Share

        Share this Publication link

        Share on social media