About DML-CZ | FAQ | Conditions of Use | Math Archives | Contact Us
  Previous |  Up |  Next

Article

Zhang, Jie ; Zhang, Li-wei ; Wu, Yue
A smoothing SAA method for a stochastic mathematical program with complementarity constraints. (English). Applications of Mathematics, vol. 57 (2012), issue 5, pp. 477-502
MSC: 90C15, 90C33 | MR 2984615 | Zbl 1265.90223 | DOI: 10.1007/s10492-012-0028-5
Keywords:
smoothing SAA method; log-exponential function; stochastic mathematical program with complementarity constraints; almost sure convergence; complementarity constraints; sample average approximation; stability analysis
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.
References:
[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. DOI 10.1016/S0305-0548(03)00176-X | MR 2079391 | Zbl 1074.90048
[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. DOI 10.1287/moor.1060.0215 | MR 2281227 | Zbl 1278.90278
[3] Clarke, F. H.: Optimization and Nonsmooth Analysis. John Wiley & Sons New York (1983). MR 0709590 | Zbl 0582.49001
[4] Fischer, A.: A special Newton-type optimization method. Optimization 24 (1992), 269-284. DOI 10.1080/02331939208843795 | MR 1247636 | Zbl 0814.65063
[5] King, A. J., Rockafellar, R. T.: Sensitivity analysis for nonsmooth generalized equations. Math. Program. 55 (1992), 193-212. DOI 10.1007/BF01581199 | MR 1167597 | Zbl 0766.90075
[6] Linderoth, J., Shapiro, A., Wright, S.: The empirical behavior of sampling methods for stochastic programming. Ann. Oper. Res. 142 (2006), 215-241. DOI 10.1007/s10479-006-6169-8 | MR 2222918 | Zbl 1122.90391
[7] Li, X. S.: An aggregate function method for nonlinear programming. Sci. China (Ser. A) 34 (1991), 1467-1473. MR 1167796 | Zbl 0752.90069
[8] Li, X. S.: An entropy-based aggregate method for minimax optimization. J. Eng. Optim. 18 (1992), 277-185. DOI 10.1080/03052159208941026
[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. DOI 10.1007/s10107-007-0119-3 | MR 2421285 | Zbl 1168.90008
[10] Luo, Z.-Q., Pang, J.-S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press Cambridge (1997). MR 1419501 | Zbl 0898.90006
[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.
[12] Patriksson, M., Wynter, L.: Stochastic mathematical programs with equilibrium constraints. Oper. Res. Lett. 25 (1999), 159-167. DOI 10.1016/S0167-6377(99)00052-8 | MR 1725965 | Zbl 0937.90076
[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. DOI 10.1023/A:1008656806889 | MR 1704116 | Zbl 1040.90560
[14] Peng, J., Lin, Z.: A non-interior continuation method for generalized linear complementarity problems. Math. Program. 86 (1999), 533-563. DOI 10.1007/s101070050104 | MR 1733744 | Zbl 0987.90081
[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. DOI 10.1007/BF02592150 | MR 1426636
[16] Qi, H., Liao, L.: A smoothing Newton method for extended vertical linear complementarity problems. SIAM J. Matrix Anal. Appl. 21 (1999), 45-66. DOI 10.1137/S0895479897329837 | MR 1709725 | Zbl 1017.90114
[17] Robinson, S. M.: Strongly regular generalized equations. Math. Oper. Res. 5 (1980), 43-62. DOI 10.1287/moor.5.1.43 | MR 0561153 | Zbl 0437.90094
[18] Robinson, S. M.: Analysis of sample-path optimization. Math. Oper. Res. 21 (1996), 513-528. DOI 10.1287/moor.21.3.513 | MR 1403302 | Zbl 0868.90087
[19] Rockafellar, R. T.: Convex Analysis. Princeton University Press Princeton (1970). MR 0274683 | Zbl 0193.18401
[20] Rockafellar, R. T., Wets, R. J. B.: Variational Analysis. Springer Berlin (1998). MR 1491362 | Zbl 0888.49001
[21] Scheel, H., Scholtes, S.: Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity. Math. Oper. Res. 25 (2000), 1-22. DOI 10.1287/moor.25.1.1.15213 | MR 1854317
[22] Shapiro, A., Xu, H.: Stochastic mathematical programs with equilibrium constraints, modelling and sample average approximation. Optimization 57 (2008), 395-418. DOI 10.1080/02331930801954177 | MR 2412074 | Zbl 1145.90047
[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. DOI 10.1137/S1052623498349541 | MR 1785640 | Zbl 0999.90023
[24] Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming. Modeling and Theory. SIAM Philadelphia (2009). MR 2562798 | Zbl 1183.90005
[25] Vaart, A. van der, Wellner, J. A.: Weak Convergence and Empirical Processes. Springer New York (1996). MR 1385671
[26] Xu, H.: An implicit programming approach for a class of stochastic mathematical programs with equilibrium constraints. SIAM J. Optim. 16 (2006), 670-696. DOI 10.1137/040608544 | MR 2197552
[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. DOI 10.1287/moor.1070.0260 | MR 2348240
[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. MR 1443630 | Zbl 0873.49018
[29] Ye, J. J.: Necessary and sufficient optimality conditions for mathematical programs with equilibrium constraints. J. Math. Anal. Appl. 307 (2005), 350-369. DOI 10.1016/j.jmaa.2004.10.032 | MR 2138995 | Zbl 1112.90062
[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. DOI 10.1007/s00186-006-0076-2 | MR 2264784 | Zbl 1132.90370
Partner of
EuDML logo