| 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:
|
http://hdl.handle.net/10338.dmlcz/142912 |
| . |
| 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.25.1.1.15213 |
| 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 |
| . |
