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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alexander, S., Coleman, T.F., Li, Y.: Minimizing CVaR and VaR for a portfolio of derivatives. J. Bank. Finance 30, 583–605 (2006)
Artstein, Z., Vitale, R.A.: A strong law of large numbers for random compact sets. Ann. Probab. 3, 879–882 (1975)
Artstein, Z., J-B Wets, R.: Consistency of minimizers and the SLLN for stochastic programs. J. Convex Anal 2, 1–17 (1995)
Aumann, R.J.: Integrals of set-valued function. J. Math. Anal. Appl. 12, 1–12 (1965)
Aubin, J.-P., Frankowska, H.: Set-Valued Analysis. Birkhäuser, Boston (1990)
Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems, Springer Series in Operations Research, Springer, Heidelberg (2000)
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)
Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983)
Dontchev, A.L., Lewis, A.S., Rockafellar, R.T.: The radius of metric regularity. Trans. Am. Math. Soc. 355, 493–517 (2004)
Ermoliev, Y.M.: Stochastic Programming Methods. Nauka, Moscow (1976)
Ermoliev, Y.M., Norkin, V.I.: Solution of nonconvex nonsmooth stochastic optimization problems. Cybern. Syst. Anal. 39, 701–715 (2003)
Facchinei, F., Pang, J.-S.: Finite-dimensional Variational Inequalities and Complementarity Problems, Springer, Heidelberg (2003)
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)
Hogan, W.W.: Point-to-set maps in mathematical programming. SIAM Rev. 15, 591–603 (1973)
Homen-De-Mello, T.: Estimation of derivatives of nonsmooth performance measures in regenerative systems. Math. Oper. Res. 26, 741–768 (2001)
King, A.J., Wets, R. J.-B.: Epi-consistency of convex stochastic programs. Stochast. Stochast. Rep. 34, 83–92 (1991)
Kiwiel, K.C.: An aggregate subgradient method for nonsmooth convex minimization. Math. Program. 27, 320–341 (1983)
Lemaréchal, C.: Bundle methods in nonsmooth optimization. In: Lemaréchal, C., Mifflin, R. (eds) Nonsmooth Optimization, pp. 79–102. Pergamon Press, Oxford (1978)
Linderoth, J., Shapiro, A., Wright, S.: The empirical behavior of sampling methods for stochastic programming. Anna. Oper. Res. 142, 215–241 (2006)
Luo, Z.-Q., Pang, J.-S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)
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)
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)
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)
Ralph, D., Xu, H.: Implicit smoothing and its application to optimization with piecewise smooth equality constraints. J. Optim. Theory Appl. 124, 673–699 (2005)
Robinson, S.M.: Generalized equations, Mathematical programming: the state of the art. Bonn, 1982, pp. 346–367. Springer, Berlin (1983)
Robinson, S.M.: Analysis of sample-path optimization. Math. Oper. Res. 21, 513–528 (1996)
Rockafellar, R.T., Uryasev, S.: Optimization of conditional value-of-risk. J. Risk 2, 21–41 (2000)
Rockafellar, R.T., Uryasev, S.: Conditional value-at-risk for general loss distributions. J. Bank. Finance 26, 1443–1471 (2002)
Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998)
Römisch, W., Schultz, R.: Lipschitz stability for stochastic programs with complete recourse. SIAM J. Optim. 6, 531–547 (1996)
Rubinstein, R.Y., Shapiro, A.: Discrete Events Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Methods. Wiley, New York (1993)
Rusczyński, A.: A linearization method for nonsmooth stochastic programming problems. Math. Oper. Res. 12, 32–49 (1987)
Rusczyński, A., Shapiro, A.: Stochastic Programming, Handbooks in OR & MS, vol. 10. North-Holland, Amsterdam (2003)
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)
Shapiro, A., Homem-de-Mello, T.: On rate of convergence of Monte Carlo approximations of stochastic programs. SIAM J. Optim. 11, 70–86 (2000)
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
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)
Wets, R.: Stochastic Programming. In: Nemhauser, G.L., et al. (eds.) Handbooks in OR & MS, vol. 1, pp. 573–629 (1989)
Xu, H.: An implicit programming approach for a class of stochastic mathematical programs with complementarity constraints. SIAM J. Optim. 16, 670–696 (2006)
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)
Zhang, J.: Transshipment and its impact on supply chain members’ performance. Manage. Sci. 51, 1534–1539 (2005)
Zimmer, K.: Supply chain coordination with uncertain just-in-time delivery. Int. J. Prod. Econ. 77, 1–15 (2002)
Author information
Authors and Affiliations
Corresponding author
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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-008-0214-0