×

zbMATH — the first resource for mathematics

Smooth sample average approximation of stationary points in nonsmooth stochastic optimization and applications. (English) Zbl 1168.90009
The authors propose a smoothing SAA (sample average approximation) method for solving the following nonsmooth stochastic minimization problem \[ \min \mathbb{E}\left[ f\left( x,\xi \left( \omega \right) \right) \right] \text{ s.t. } x\in \mathcal{X}, \tag{1} \] where \(f:\mathbb{R}^{m}\times \mathbb{R}^{k}\rightarrow \mathbb{R}\) is locally Lipschitz continuous but not necessarily continuously differentiable, \(\xi :\Omega \rightarrow \Xi \subset \mathbb{R}^{k}\) is a random vector defined on the probability space \(\left( \Omega ,\mathcal{F} ,P\right)\), \(\mathbb{E}\) denotes the mathematical expectation, \(x\in \mathcal{X}\) is a decision vector with \(\mathcal{X}\) being a nonempty subset of \(\mathbb{R}^{m}\).
It is supposed that \(\mathbb{E}\left[ f\left( x,\xi \left( \omega \right) \right) \right] \) is well defined for every \(x\in \mathcal{X}\).
The authors generalize a convergence theorem established by A. Shapiro [in: Rusczyński, A., Shapiro A. (eds.), Stochastic Programming, Handbooks in OR & MS, vol. 10. North-Holland, Amsterdam (2003)] on a SSA method for a generalized stochastic equation and use it to show that under moderate conditions w.p.1 the stationary points of the smoothed sample average approximation problem converge to the weak stationary points of problem (1) and, when the underlying functions are convex, to optimal solutions. When the smoothing parameter is fixed, the authors obtain an error bound for the SAA stationary points under some metric regularity condition. Finally, they apply the convergence results to a CVaR problem and an inventory control problem in a supply chain.

MSC:
90C15 Stochastic programming
65K05 Numerical mathematical programming methods
91B28 Finance etc. (MSC2000)
Software:
SUTIL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alexander, S., Coleman, T.F., Li, Y.: Minimizing CVaR and VaR for a portfolio of derivatives. J. Bank. Finance 30, 583–605 (2006)
[2] Artstein, Z., Vitale, R.A.: A strong law of large numbers for random compact sets. Ann. Probab. 3, 879–882 (1975) · Zbl 0313.60012
[3] Artstein, Z., J-B Wets, R.: Consistency of minimizers and the SLLN for stochastic programs. J. Convex Anal 2, 1–17 (1995) · Zbl 0837.90093
[4] Aumann, R.J.: Integrals of set-valued function. J. Math. Anal. Appl. 12, 1–12 (1965) · Zbl 0163.06301
[5] Aubin, J.-P., Frankowska, H.: Set-Valued Analysis. Birkhäuser, Boston (1990) · Zbl 0713.49021
[6] Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems, Springer Series in Operations Research, Springer, Heidelberg (2000) · Zbl 0966.49001
[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)
[8] Clarke, F.H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983) · Zbl 0582.49001
[9] Dontchev, A.L., Lewis, A.S., Rockafellar, R.T.: The radius of metric regularity. Trans. Am. Math. Soc. 355, 493–517 (2004) · Zbl 1042.49026
[10] Ermoliev, Y.M.: Stochastic Programming Methods. Nauka, Moscow (1976)
[11] Ermoliev, Y.M., Norkin, V.I.: Solution of nonconvex nonsmooth stochastic optimization problems. Cybern. Syst. Anal. 39, 701–715 (2003) · Zbl 1066.90071
[12] Facchinei, F., Pang, J.-S.: Finite-dimensional Variational Inequalities and Complementarity Problems, Springer, Heidelberg (2003) · Zbl 1062.90002
[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) · Zbl 1022.60011
[14] Hogan, W.W.: Point-to-set maps in mathematical programming. SIAM Rev. 15, 591–603 (1973) · Zbl 0256.90042
[15] Homen-De-Mello, T.: Estimation of derivatives of nonsmooth performance measures in regenerative systems. Math. Oper. Res. 26, 741–768 (2001) · Zbl 1082.60519
[16] King, A.J., Wets, R. J.-B.: Epi-consistency of convex stochastic programs. Stochast. Stochast. Rep. 34, 83–92 (1991) · Zbl 0733.90049
[17] Kiwiel, K.C.: An aggregate subgradient method for nonsmooth convex minimization. Math. Program. 27, 320–341 (1983) · Zbl 0525.90074
[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)
[19] Linderoth, J., Shapiro, A., Wright, S.: The empirical behavior of sampling methods for stochastic programming. Anna. Oper. Res. 142, 215–241 (2006) · Zbl 1122.90391
[20] Luo, Z.-Q., Pang, J.-S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge (1996)
[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) · Zbl 1128.90043
[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)
[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) · Zbl 0874.90150
[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) · Zbl 1211.90278
[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) · Zbl 0868.90087
[27] Rockafellar, R.T., Uryasev, S.: Optimization of conditional value-of-risk. J. Risk 2, 21–41 (2000)
[28] Rockafellar, R.T., Uryasev, S.: Conditional value-at-risk for general loss distributions. J. Bank. Finance 26, 1443–1471 (2002)
[29] Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998)
[30] Römisch, W., Schultz, R.: Lipschitz stability for stochastic programs with complete recourse. SIAM J. Optim. 6, 531–547 (1996) · Zbl 0854.90113
[31] Rubinstein, R.Y., Shapiro, A.: Discrete Events Systems: Sensitivity Analysis and Stochastic Optimization by the Score Function Methods. Wiley, New York (1993) · Zbl 0805.93002
[32] Rusczyński, A.: A linearization method for nonsmooth stochastic programming problems. Math. Oper. Res. 12, 32–49 (1987) · Zbl 0624.90078
[33] Rusczyński, A., Shapiro, A.: Stochastic Programming, Handbooks in OR & MS, vol. 10. North-Holland, Amsterdam (2003)
[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) · Zbl 1053.90103
[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) · Zbl 0999.90023
[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) · Zbl 1109.60030
[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) · Zbl 1113.90114
[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) · Zbl 1341.90095
[41] Zhang, J.: Transshipment and its impact on supply chain members’ performance. Manage. Sci. 51, 1534–1539 (2005) · Zbl 06008180
[42] Zimmer, K.: Supply chain coordination with uncertain just-in-time delivery. Int. J. Prod. Econ. 77, 1–15 (2002)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.