Movatterモバイル変換

[0]ホーム
URL:

Skip to main content
Springer Nature Link
Log in

Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications

  • FULL LENGTH PAPER
  • Published:
Mathematical Programming Submit manuscript

Abstract

Inspired by a recent work by Alexander et al. (J Bank Finance 30:583–605, 2006) which proposes a smoothing method to deal with nonsmoothness in a conditional value-at-risk problem, we consider a smoothing scheme for a general class of nonsmooth stochastic problems. Assuming that a smoothed problem is solved by a sample average approximation method, we investigate the convergence of stationary points of the smoothed sample average approximation problem as sample size increases and show that w.p.1 accumulation points of the stationary points of the approximation problem are weak stationary points of their counterparts of the true problem. Moreover, under some metric regularity conditions, we obtain an error bound on approximate stationary points. The convergence result is applied to a conditional value-at-risk problem and an inventory control problem.

This is a preview of subscription content,log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Similar content being viewed by others

Explore related subjects

Discover the latest articles and news from researchers in related subjects, suggested using machine learning.

References

  1. Alexander, S., Coleman, T.F., Li, Y.: Minimizing CVaR and VaR for a portfolio of derivatives. J. Bank. Finance30, 583–605 (2006)

    Article  Google Scholar 

  2. Artstein, Z., Vitale, R.A.: A strong law of large numbers for random compact sets. Ann. Probab.3, 879–882 (1975)

    Article MATH MathSciNet  Google Scholar 

  3. Artstein, Z., J-B Wets, R.: Consistency of minimizers and the SLLN for stochastic programs. J. Convex Anal2, 1–17 (1995)

    MATH MathSciNet  Google Scholar 

  4. Aumann, R.J.: Integrals of set-valued function. J. Math. Anal. Appl.12, 1–12 (1965)

    Article MATH MathSciNet  Google Scholar 

  5. Aubin, J.-P., Frankowska, H.: Set-Valued Analysis. Birkhäuser, Boston (1990)

    MATH  Google Scholar 

  6. Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems, Springer Series in Operations Research, Springer, Heidelberg (2000)

  7. Chen, H., Chen, J., Chen, Y.: A coordination mechanism for a supply chain with demand information updating. Int. J. Prod. Econ.103, 347–361 (2006)

    Article  Google Scholar 

  8. Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)

    MATH  Google Scholar 

  9. Dontchev, A.L., Lewis, A.S., Rockafellar, R.T.: The radius of metric regularity. Trans. Am. Math. Soc.355, 493–517 (2004)

    Article MathSciNet  Google Scholar 

  10. Ermoliev, Y.M.: Stochastic Programming Methods. Nauka, Moscow (1976)

    Google Scholar 

  11. Ermoliev, Y.M., Norkin, V.I.: Solution of nonconvex nonsmooth stochastic optimization problems. Cybern. Syst. Anal.39, 701–715 (2003)

    Article MATH  Google Scholar 

  12. Facchinei, F., Pang, J.-S.: Finite-dimensional Variational Inequalities and Complementarity Problems, Springer, Heidelberg (2003)

  13. Hess, C.: Set-Valued integration and set-valued probability theory: an overview. In: Handbook of Measure Theory, vol. I, II, pp 617–673. North-Holland, Amsterdam (2002)

  14. Hogan, W.W.: Point-to-set maps in mathematical programming. SIAM Rev.15, 591–603 (1973)

    Article MATH MathSciNet  Google Scholar 

  15. Homen-De-Mello, T.: Estimation of derivatives of nonsmooth performance measures in regenerative systems. Math. Oper. Res.26, 741–768 (2001)

    Article MathSciNet  Google Scholar 

  16. King, A.J., Wets, R. J.-B.: Epi-consistency of convex stochastic programs. Stochast. Stochast. Rep.34, 83–92 (1991)

    MATH MathSciNet  Google Scholar 

  17. Kiwiel, K.C.: An aggregate subgradient method for nonsmooth convex minimization. Math. Program.27, 320–341 (1983)

    Article MATH MathSciNet  Google Scholar 

  18. Lemaréchal, C.: Bundle methods in nonsmooth optimization. In: Lemaréchal, C., Mifflin, R. (eds) Nonsmooth Optimization, pp. 79–102. Pergamon Press, Oxford (1978)

    Google Scholar 

  19. Linderoth, J., Shapiro, A., Wright, S.: The empirical behavior of sampling methods for stochastic programming. Anna. Oper. Res.142, 215–241 (2006)

    Article MATH MathSciNet  Google Scholar 

  20. Luo, Z.-Q., Pang, J.-S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)

    Google Scholar 

  21. Meng, F., Xu, H.: A regularized sample average approximation method for stochastic mathematical programs with nonsmooth equality constraints. SIAM J. Optim.17, 891–919 (2006)

    Article MATH MathSciNet  Google Scholar 

  22. Peng, J.: A smoothing function and its applications. In: Fukushima, M., Qi, L. (eds) Reformulation: Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods, pp. 293–316. Kluwer, Dordrecht (1998)

    Google Scholar 

  23. Plambeck, E.L., Fu, B.R., Robinson, S.M., Suri, R.: Sample-path optimization of convex stochastic performances functions. Math. Program.75, 137–176 (1996)

    MathSciNet  Google Scholar 

  24. Ralph, D., Xu, H.: Implicit smoothing and its application to optimization with piecewise smooth equality constraints. J. Optim. Theory Appl.124, 673–699 (2005)

    Article MATH MathSciNet  Google Scholar 

  25. Robinson, S.M.: Generalized equations, Mathematical programming: the state of the art. Bonn, 1982, pp. 346–367. Springer, Berlin (1983)

  26. Robinson, S.M.: Analysis of sample-path optimization. Math. Oper. Res.21, 513–528 (1996)

    Article MATH MathSciNet  Google Scholar 

  27. Rockafellar, R.T., Uryasev, S.: Optimization of conditional value-of-risk. J. Risk2, 21–41 (2000)

    Google Scholar 

  28. Rockafellar, R.T., Uryasev, S.: Conditional value-at-risk for general loss distributions. J. Bank. Finance26, 1443–1471 (2002)

    Article  Google Scholar 

  29. Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998)

    MATH  Google Scholar 

  30. Römisch, W., Schultz, R.: Lipschitz stability for stochastic programs with complete recourse. SIAM J. Optim.6, 531–547 (1996)

    Article MATH MathSciNet  Google Scholar 

  31. Rubinstein, R.Y., Shapiro, A.: Discrete Events Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Methods. Wiley, New York (1993)

    Google Scholar 

  32. Rusczyński, A.: A linearization method for nonsmooth stochastic programming problems. Math. Oper. Res.12, 32–49 (1987)

    Article MathSciNet  Google Scholar 

  33. Rusczyński, A., Shapiro, A.: Stochastic Programming, Handbooks in OR & MS, vol. 10. North-Holland, Amsterdam (2003)

    Google Scholar 

  34. Shapiro, A.: Monte Carlo sampling methods. In: Rusczyński, A., Shapiro, A. (eds) Stochastic Programming, Handbooks in OR & MS, vol. 10, Amsterdam, North-Holland (2003)

    Google Scholar 

  35. Shapiro, A., Homem-de-Mello, T.: On rate of convergence of Monte Carlo approximations of stochastic programs. SIAM J. Optim.11, 70–86 (2000)

    Article MATH MathSciNet  Google Scholar 

  36. Shapiro, A., Xu, H.: Stochastic mathematical programs with equilibrium constraints, modeling and sample average approximation. Optimization (to appear) (2005). http://www.optimization-online.org/DB_HTML/2005/01/1046.html

  37. Shapiro, A., Xu, H.: Uniform laws of large numbers for set-valued mappings and subdifferentials of random functions. J. Math. Anal. Appl.325, 1390–1399 (2006)

    Article MathSciNet  Google Scholar 

  38. Wets, R.: Stochastic Programming. In: Nemhauser, G.L., et al. (eds.) Handbooks in OR & MS, vol. 1, pp. 573–629 (1989)

  39. Xu, H.: An implicit programming approach for a class of stochastic mathematical programs with complementarity constraints. SIAM J. Optim.16, 670–696 (2006)

    Article MATH MathSciNet  Google Scholar 

  40. 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, 648–669 (2007)

    Article MATH MathSciNet  Google Scholar 

  41. Zhang, J.: Transshipment and its impact on supply chain members’ performance. Manage. Sci.51, 1534–1539 (2005)

    Article  Google Scholar 

  42. Zimmer, K.: Supply chain coordination with uncertain just-in-time delivery. Int. J. Prod. Econ.77, 1–15 (2002)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematics, University of Southampton, Highfield Southampton, UK

    Huifu Xu & Dali Zhang

Authors
  1. Huifu Xu

    You can also search for this author inPubMed Google Scholar

  2. Dali Zhang

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence toHuifu Xu.

Rights and permissions

About this article

Cite this article

Xu, H., Zhang, D. Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications.Math. Program.119, 371–401 (2009). https://doi.org/10.1007/s10107-008-0214-0

Download citation

Keywords

Mathematics Subject Classification (2000)

Access this article

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Advertisement

[8]ページ先頭
©2009-2025 Movatter.jp