A smoothing SAA method for a stochastic mathematical program with complementarity constraints

Jie Zhang; Li-wei Zhang; Yue Wu

Applications of Mathematics (2012)

  • Volume: 57, Issue: 5, page 477-502
  • ISSN: 0862-7940

Abstract

top
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.

How to cite

top

Zhang, Jie, Zhang, Li-wei, and Wu, Yue. "A smoothing SAA method for a stochastic mathematical program with complementarity constraints." Applications of Mathematics 57.5 (2012): 477-502. <http://eudml.org/doc/246758>.

@article{Zhang2012,
abstract = {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.},
author = {Zhang, Jie, Zhang, Li-wei, Wu, Yue},
journal = {Applications of Mathematics},
keywords = {smoothing SAA method; log-exponential function; stochastic mathematical program with complementarity constraints; almost sure convergence; complementarity constraints; sample average approximation; stability analysis; complementarity constraints; sample average approximation; stability analysis; almost sure convergence},
language = {eng},
number = {5},
pages = {477-502},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A smoothing SAA method for a stochastic mathematical program with complementarity constraints},
url = {http://eudml.org/doc/246758},
volume = {57},
year = {2012},
}

TY - JOUR
AU - Zhang, Jie
AU - Zhang, Li-wei
AU - Wu, Yue
TI - A smoothing SAA method for a stochastic mathematical program with complementarity constraints
JO - Applications of Mathematics
PY - 2012
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 57
IS - 5
SP - 477
EP - 502
AB - 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.
LA - eng
KW - smoothing SAA method; log-exponential function; stochastic mathematical program with complementarity constraints; almost sure convergence; complementarity constraints; sample average approximation; stability analysis; complementarity constraints; sample average approximation; stability analysis; almost sure convergence
UR - http://eudml.org/doc/246758
ER -

References

top
  1. Birbil, S. I., Fang, S.-C., Han, J., 10.1016/S0305-0548(03)00176-X, Comput. Oper. Res. 31 (2004), 2249-2262. (2004) Zbl1074.90048MR2079391DOI10.1016/S0305-0548(03)00176-X
  2. Birbil, S. I., Gürkan, G., Listes, O., 10.1287/moor.1060.0215, Math. Oper. Res. 31 (2006), 739-760. (2006) Zbl1278.90278MR2281227DOI10.1287/moor.1060.0215
  3. Clarke, F. H., Optimization and Nonsmooth Analysis, John Wiley & Sons New York (1983). (1983) Zbl0582.49001MR0709590
  4. Fischer, A., 10.1080/02331939208843795, Optimization 24 (1992), 269-284. (1992) Zbl0814.65063MR1247636DOI10.1080/02331939208843795
  5. King, A. J., Rockafellar, R. T., 10.1007/BF01581199, Math. Program. 55 (1992), 193-212. (1992) Zbl0766.90075MR1167597DOI10.1007/BF01581199
  6. Linderoth, J., Shapiro, A., Wright, S., 10.1007/s10479-006-6169-8, Ann. Oper. Res. 142 (2006), 215-241. (2006) Zbl1122.90391MR2222918DOI10.1007/s10479-006-6169-8
  7. Li, X. S., An aggregate function method for nonlinear programming, Sci. China (Ser. A) 34 (1991), 1467-1473. (1991) Zbl0752.90069MR1167796
  8. Li, X. S., 10.1080/03052159208941026, J. Eng. Optim. 18 (1992), 277-185. (1992) DOI10.1080/03052159208941026
  9. Lin, G.-H., Chen, X., Fukushima, M., 10.1007/s10107-007-0119-3, Math. Program. 116 (2009), 343-368. (2009) Zbl1168.90008MR2421285DOI10.1007/s10107-007-0119-3
  10. Luo, Z.-Q., Pang, J.-S., Ralph, D., Mathematical Programs with Equilibrium Constraints, Cambridge University Press Cambridge (1997). (1997) Zbl0898.90006MR1419501
  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. (2006) 
  12. Patriksson, M., Wynter, L., 10.1016/S0167-6377(99)00052-8, Oper. Res. Lett. 25 (1999), 159-167. (1999) Zbl0937.90076MR1725965DOI10.1016/S0167-6377(99)00052-8
  13. Pang, J., Fukushima, M., 10.1023/A:1008656806889, Comput. Optim. Appl. 13 (1999), 111-136. (1999) Zbl1040.90560MR1704116DOI10.1023/A:1008656806889
  14. Peng, J., Lin, Z., 10.1007/s101070050104, Math. Program. 86 (1999), 533-563. (1999) Zbl0987.90081MR1733744DOI10.1007/s101070050104
  15. Plambeck, E. L., Fu, B.-R., Robinson, S. M., Suri, R., 10.1007/BF02592150, Math. Program. 75 (1996), 137-176. (1996) MR1426636DOI10.1007/BF02592150
  16. Qi, H., Liao, L., 10.1137/S0895479897329837, SIAM J. Matrix Anal. Appl. 21 (1999), 45-66. (1999) Zbl1017.90114MR1709725DOI10.1137/S0895479897329837
  17. Robinson, S. M., 10.1287/moor.5.1.43, Math. Oper. Res. 5 (1980), 43-62. (1980) Zbl0437.90094MR0561153DOI10.1287/moor.5.1.43
  18. Robinson, S. M., 10.1287/moor.21.3.513, Math. Oper. Res. 21 (1996), 513-528. (1996) Zbl0868.90087MR1403302DOI10.1287/moor.21.3.513
  19. Rockafellar, R. T., Convex Analysis, Princeton University Press Princeton (1970). (1970) Zbl0193.18401MR0274683
  20. Rockafellar, R. T., Wets, R. J. B., Variational Analysis, Springer Berlin (1998). (1998) Zbl0888.49001MR1491362
  21. Scheel, H., Scholtes, S., 10.1287/moor.25.1.1.15213, Math. Oper. Res. 25 (2000), 1-22. (2000) MR1854317DOI10.1287/moor.25.1.1.15213
  22. Shapiro, A., Xu, H., 10.1080/02331930801954177, Optimization 57 (2008), 395-418. (2008) Zbl1145.90047MR2412074DOI10.1080/02331930801954177
  23. Shapiro, A., Homem-de-Mello, T., 10.1137/S1052623498349541, SIAM J. Optim. 11 (2000), 70-86. (2000) Zbl0999.90023MR1785640DOI10.1137/S1052623498349541
  24. Shapiro, A., Dentcheva, D., Ruszczyński, A., Lectures on Stochastic Programming. Modeling and Theory, SIAM Philadelphia (2009). (2009) Zbl1183.90005MR2562798
  25. Vaart, A. van der, Wellner, J. A., Weak Convergence and Empirical Processes, Springer New York (1996). (1996) MR1385671
  26. Xu, H., 10.1137/040608544, SIAM J. Optim. 16 (2006), 670-696. (2006) MR2197552DOI10.1137/040608544
  27. Xu, H., Meng, F., 10.1287/moor.1070.0260, Math. Oper. Res. 32 (2007), 648-668. (2007) MR2348240DOI10.1287/moor.1070.0260
  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. (1997) Zbl0873.49018MR1443630
  29. Ye, J. J., 10.1016/j.jmaa.2004.10.032, J. Math. Anal. Appl. 307 (2005), 350-369. (2005) Zbl1112.90062MR2138995DOI10.1016/j.jmaa.2004.10.032
  30. Yin, H., Zhang, J., 10.1007/s00186-006-0076-2, Math. Methods Oper. Res. 64 (2006), 255-269. (2006) Zbl1132.90370MR2264784DOI10.1007/s00186-006-0076-2

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.