IJPAM: Volume 114, No. 3 (2017)

Title

CONVERGENCE ANALYSIS OF SAA METHOD FOR
A STOCHASTIC EXTENDED VERTICAL LINEAR
COMPLEMENTARITY PROBLEM

Authors

Jie Zhang$^1$, Wen-Bai Shan$^2$, Hong-Yang Chi$^3$
$^{1}$School of Mathematics
Liaoning Normal University
Dalian 116029, P.R. CHINA

Abstract

In this paper, we investigate convergence properties of sample average approximation (SAA) method for a stochastic extended vertical linear complementarity problem, where the underlying function is the expected value of stochastic function. In particular, using the implicit function theorem, we develop sufficient conditions for the convergence of SAA method, namely if the solution of the true problem exists, then so does the SAA problem with probability one when the sample size is large enough and a sequence of SAA solutions converges to a solution of the true problem with probability one with the sample size tends to infinity. At last, an example is illustrated to show the application of the analysis.

History

Received: February 15, 2017
Revised: April 27, 2017
Published: May 23, 2017

AMS Classification, Key Words

AMS Subject Classification: 90C30
Key Words and Phrases: sample average approximation, stochastic extended vertical linear complementarity problem, convergence analysis

Download Section

Download paper from here.
You will need Adobe Acrobat reader. For more information and free download of the reader, see the Adobe Acrobat website.

Bibliography

1
F. H. Clarke, Optimization and nonsmoothanalysis, John Wiley and Sons, New York, 1983.

2
G. G$\ddot{u}$rkan, A.Y. $\ddot{O}$zge, and S. M. Robinson, Sample-pathsolution of stochastic variational inequalities, MathematicalProgramming, 84 (1999), 313-333.

3
H. Jiang and H. Xu, Stochastic Approximation approaches to the stochasticvariational inequality problem, IEEE Transactions on AutomaticControl, 53 (2008), 1462-1475.

4
A. Shapiro, D. Dentcheva, and A. Ruszczynski, Lectures on StochasticProgramming: Modeling and Theory, SIAM,Philadelphia, 2009.

5
H. Xu, An implicitprogramming approach for a class of stochastic mathematical programswith equilibrium constraints, SIAM J. Optim., 16 (2006), 670-696.

6
H. Xu, and D. Zhang, Smooth sample average approximation ofstationary points in nonsmooth stochastic optimization andapplications, Mathematical Programming, 119 (2009), 371-401.

7
J. Zhang, L. Zhang, L. Pang, On the convergence of coderivative of SAA solution mapping for a parametric stochastic variational inequality problem, Set-Valued and Variational Analysis, 20 (2012), 75-109.

8
J. Zhang, L. Zhang, S. Lin, A class of smoothing SAA methods for a stochastic mathematical program with complementarity constraints, J. Math. Anal. Appl., 387 (2012), 201-220.

9
L. Zhang, J. Zhang, Y. Wu, On the convergence of coderivative of SAA solution mapping for a parametric stochastic generalized equation, Set-Valued and Variational Analysis, 19 (2011), 107-134.

10
M.S. Gowda, R. Sznajder, The generalized order linear complementarity problem, SIAM J. Matrix Anal.Appl., 15 (1994), 779-795.

11
M.S. Gowda, R. Sznajder, A generalization of the Nash equilibrium theorem on bimatrix games, Internat. J. Game Theory, 25 (1996), 1-12.

12
J. Peng, Z. Lin, ANon-interior Continuation Method for Generalized LinearComplementarity Problems, Math. Program. 86 (1999),533-563.

13
H. Qi, L. Liao, A smoothing Newton method for extended verticallinear complementarity problems, SIAM J. Matrix Anal. Appl.,21 (1999), 45-66.

14
B. S. He, A class of projection and contraction methods for monotonevariational inequalities. Applied Mathematics andOptimization, 35 (1997), 69-76.

How to Cite?

DOI: 10.12732/ijpam.v114i3.15 How to cite this paper?

Source: International Journal of Pure and Applied Mathematics
ISSN printed version: 1311-8080
ISSN on-line version: 1314-3395
Year: 2017
Volume: 114
Issue: 3
Pages: 603 - 609


Google Scholar; DOI (International DOI Foundation); WorldCAT.

CC BY This work is licensed under the Creative Commons Attribution International License (CC BY).