Previous |  Up |  Next


Title: A smoothing SAA method for a stochastic mathematical program with complementarity constraints (English)
Author: Zhang, Jie
Author: Zhang, Li-wei
Author: Wu, Yue
Language: English
Journal: Applications of Mathematics
ISSN: 0862-7940 (print)
ISSN: 1572-9109 (online)
Volume: 57
Issue: 5
Year: 2012
Pages: 477-502
Summary lang: English
Category: math
Summary: A smoothing sample average approximation (SAA) method based on the log-exponential function is proposed for solving a stochastic mathematical program with complementarity constraints (SMPCC) considered by Birbil et al. (S. I. Birbil, G. Gürkan, O. Listes: Solving stochastic mathematical programs with complementarity constraints using simulation, Math. Oper. Res. 31 (2006), 739–760). It is demonstrated that, under suitable conditions, the optimal solution of the smoothed SAA problem converges almost surely to that of the true problem as the sample size tends to infinity. Moreover, under a strong second-order sufficient condition for SMPCC, the almost sure convergence of Karash-Kuhn-Tucker points of the smoothed SAA problem is established by Robinson's stability theory. Some preliminary numerical results are reported to show the efficiency of our method. (English)
Keyword: smoothing SAA method
Keyword: log-exponential function
Keyword: stochastic mathematical program with complementarity constraints
Keyword: almost sure convergence
Keyword: complementarity constraints
Keyword: sample average approximation
Keyword: stability analysis
MSC: 90C15
MSC: 90C33
idZBL: Zbl 1265.90223
idMR: MR2984615
DOI: 10.1007/s10492-012-0028-5
Date available: 2012-08-19T22:02:15Z
Last updated: 2020-07-02
Stable URL:
Reference: [1] Birbil, S. I., Fang, S.-C., Han, J.: An entropic regularization approach for mathematical programs with equilibrium constraints.Comput. Oper. Res. 31 (2004), 2249-2262. Zbl 1074.90048, MR 2079391, 10.1016/S0305-0548(03)00176-X
Reference: [2] Birbil, S. I., Gürkan, G., Listes, O.: Solving stochastic mathematical programs with complementarity constraints using simulation.Math. Oper. Res. 31 (2006), 739-760. Zbl 1278.90278, MR 2281227, 10.1287/moor.1060.0215
Reference: [3] Clarke, F. H.: Optimization and Nonsmooth Analysis.John Wiley & Sons New York (1983). Zbl 0582.49001, MR 0709590
Reference: [4] Fischer, A.: A special Newton-type optimization method.Optimization 24 (1992), 269-284. Zbl 0814.65063, MR 1247636, 10.1080/02331939208843795
Reference: [5] King, A. J., Rockafellar, R. T.: Sensitivity analysis for nonsmooth generalized equations.Math. Program. 55 (1992), 193-212. Zbl 0766.90075, MR 1167597, 10.1007/BF01581199
Reference: [6] Linderoth, J., Shapiro, A., Wright, S.: The empirical behavior of sampling methods for stochastic programming.Ann. Oper. Res. 142 (2006), 215-241. Zbl 1122.90391, MR 2222918, 10.1007/s10479-006-6169-8
Reference: [7] Li, X. S.: An aggregate function method for nonlinear programming.Sci. China (Ser. A) 34 (1991), 1467-1473. Zbl 0752.90069, MR 1167796
Reference: [8] Li, X. S.: An entropy-based aggregate method for minimax optimization.J. Eng. Optim. 18 (1992), 277-185. 10.1080/03052159208941026
Reference: [9] Lin, G.-H., Chen, X., Fukushima, M.: Solving stochastic mathematical programs with equilibrium constraints via approximation and smoothing implicit programming with penalization.Math. Program. 116 (2009), 343-368. Zbl 1168.90008, MR 2421285, 10.1007/s10107-007-0119-3
Reference: [10] Luo, Z.-Q., Pang, J.-S., Ralph, D.: Mathematical Programs with Equilibrium Constraints.Cambridge University Press Cambridge (1997). Zbl 0898.90006, MR 1419501
Reference: [11] Outrata, J. V.: Mathematical programs with equilibrium constraints: Theory and numerical methods.In: Nonsmooth Mechanics of Solids. CISM Courses and Lecture Notes, vol. 485 J. Haslinger, G. E. Stavroulakis Springer New York (2006), 221-274.
Reference: [12] Patriksson, M., Wynter, L.: Stochastic mathematical programs with equilibrium constraints.Oper. Res. Lett. 25 (1999), 159-167. Zbl 0937.90076, MR 1725965, 10.1016/S0167-6377(99)00052-8
Reference: [13] Pang, J., Fukushima, M.: Complementarity constraint qualifications and simplified $B$-stationary conditions for mathematical programs with equilibrium constraints.Comput. Optim. Appl. 13 (1999), 111-136. Zbl 1040.90560, MR 1704116, 10.1023/A:1008656806889
Reference: [14] Peng, J., Lin, Z.: A non-interior continuation method for generalized linear complementarity problems.Math. Program. 86 (1999), 533-563. Zbl 0987.90081, MR 1733744, 10.1007/s101070050104
Reference: [15] Plambeck, E. L., Fu, B.-R., Robinson, S. M., Suri, R.: Sample-path optimization of convex stochastic performances functions.Math. Program. 75 (1996), 137-176. MR 1426636, 10.1007/BF02592150
Reference: [16] Qi, H., Liao, L.: A smoothing Newton method for extended vertical linear complementarity problems.SIAM J. Matrix Anal. Appl. 21 (1999), 45-66. Zbl 1017.90114, MR 1709725, 10.1137/S0895479897329837
Reference: [17] Robinson, S. M.: Strongly regular generalized equations.Math. Oper. Res. 5 (1980), 43-62. Zbl 0437.90094, MR 0561153, 10.1287/moor.5.1.43
Reference: [18] Robinson, S. M.: Analysis of sample-path optimization.Math. Oper. Res. 21 (1996), 513-528. Zbl 0868.90087, MR 1403302, 10.1287/moor.21.3.513
Reference: [19] Rockafellar, R. T.: Convex Analysis.Princeton University Press Princeton (1970). Zbl 0193.18401, MR 0274683
Reference: [20] Rockafellar, R. T., Wets, R. J. B.: Variational Analysis.Springer Berlin (1998). Zbl 0888.49001, MR 1491362
Reference: [21] Scheel, H., Scholtes, S.: Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity.Math. Oper. Res. 25 (2000), 1-22. MR 1854317, 10.1287/moor.
Reference: [22] Shapiro, A., Xu, H.: Stochastic mathematical programs with equilibrium constraints, modelling and sample average approximation.Optimization 57 (2008), 395-418. Zbl 1145.90047, MR 2412074, 10.1080/02331930801954177
Reference: [23] Shapiro, A., Homem-de-Mello, T.: On the rate of convergence of optimal solutions of Monte Carlo approximations of stochastic programs.SIAM J. Optim. 11 (2000), 70-86. Zbl 0999.90023, MR 1785640, 10.1137/S1052623498349541
Reference: [24] Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming. Modeling and Theory.SIAM Philadelphia (2009). Zbl 1183.90005, MR 2562798
Reference: [25] Vaart, A. van der, Wellner, J. A.: Weak Convergence and Empirical Processes.Springer New York (1996). MR 1385671
Reference: [26] Xu, H.: An implicit programming approach for a class of stochastic mathematical programs with equilibrium constraints.SIAM J. Optim. 16 (2006), 670-696. MR 2197552, 10.1137/040608544
Reference: [27] Xu, H., Meng, F.: Convergence analysis of sample average approximation methods for a class of stochastic mathematical programs with equality constraints.Math. Oper. Res. 32 (2007), 648-668. MR 2348240, 10.1287/moor.1070.0260
Reference: [28] Ye, J. J., Zhu, D. L., Zhu, Q. J.: Exact penalization and necessary optimality conditions for generalized bilevel programming problems.SIAM J. Optim. 2 (1997), 481-507. Zbl 0873.49018, MR 1443630
Reference: [29] Ye, J. J.: Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints.J. Math. Anal. Appl. 307 (2005), 350-369. Zbl 1112.90062, MR 2138995, 10.1016/j.jmaa.2004.10.032
Reference: [30] Yin, H., Zhang, J.: Global convergence of a smooth approximation method for mathematical programs with complementarity constraints.Math. Methods Oper. Res. 64 (2006), 255-269. Zbl 1132.90370, MR 2264784, 10.1007/s00186-006-0076-2


Files Size Format View
AplMat_57-2012-5_4.pdf 355.4Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo