Stability analysis for stochastic programs. (English) Zbl 0748.90047
Stochastic optimization problems depending on random elements through the corresponding probability measure appear in stochastic programming practice very often. Evidently, the probability measure can be considered as a parameter of such a problem. Consequently, a stability analysis with respect to a probability measure perturbation should yield useful results.
The paper is devided into two parts. First, the stability of recourse problems is studied. The Wasserstein matrix is employed to obtain the Lipschitz property of the optimal value and the upper semicontinuity of the optimal solutions. The cases of linear and quadratic recourse are studied in particular. The second part of the paper is devoted to stochastic programming problems with (several joint) probabilistic constraints. There a suitable discrepancy is chosen to obtain (local) upper semicontinuity of the optimal solutions set and (local) Lipschitz continuity of the optimal value too. Special attention is paid to the class of \(r\)-convex probability measures in this part. The achieved results are applied to empirical measures in both considered cases.
Let us finally point out that the presented results extend some previous ones on this topic by the same authors.
The paper is devided into two parts. First, the stability of recourse problems is studied. The Wasserstein matrix is employed to obtain the Lipschitz property of the optimal value and the upper semicontinuity of the optimal solutions. The cases of linear and quadratic recourse are studied in particular. The second part of the paper is devoted to stochastic programming problems with (several joint) probabilistic constraints. There a suitable discrepancy is chosen to obtain (local) upper semicontinuity of the optimal solutions set and (local) Lipschitz continuity of the optimal value too. Special attention is paid to the class of \(r\)-convex probability measures in this part. The achieved results are applied to empirical measures in both considered cases.
Let us finally point out that the presented results extend some previous ones on this topic by the same authors.
Reviewer: V.Kankova (Praha)
Keywords:
Stochastic optimization; stability analysis; probability measure perturbation; stability of recourse problemsReferences:
| [1] | W. Alt, Lipschitzian perturbations of infinite optimization problems, in:Mathematical Programming with Data Perturbations II, ed. A.V. Fiacco (M. Dekker, New York, 1983) pp. 7–21. |
| [2] | R.N. Bhattacharya and R. Ranga Rao,Normal Approximation and Asymptotic Expansions (Wiley, New York, 1976). · Zbl 0331.41023 |
| [3] | P. Billingsley,Convergence of Probability Measures (Wiley, New York, 1968). · Zbl 0172.21201 |
| [4] | J.R. Birge and R.J.-B. Wets, Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recourse, Math. Progr. Study 27 (1986) 54–102. · Zbl 0603.90104 |
| [5] | C. Borell, Convex set functions ind-space, Periodica Math. Hung. 6 (1975) 111–136. · doi:10.1007/BF02018814 |
| [6] | F.H. Clarke,Optimization and Nonsmooth Analysis (Wiley, New York, 1983). · Zbl 0582.49001 |
| [7] | S. Dancs and B. Uhrin, On a class of integral inequalities and their measure-theoretic consequences, J. Math. Anal. Appl. 74 (1980) 388–400. · Zbl 0442.26011 · doi:10.1016/0022-247X(80)90136-5 |
| [8] | R.M. Dudley, The speed of mean Glivenko-Cantelli convergence, Ann. Math. Statist. 40 (1969) 40–50. · Zbl 0184.41401 · doi:10.1214/aoms/1177697802 |
| [9] | R.M. Dudley,Probabilities and Metrics, Lecture Notes Series No. 45. Aarhus Universitet, Aarhus, Denmark (1976). |
| [10] | J. Dupačová, Stability and sensitivity analysis for stochastic programming, Ann. Oper. Res. 27 (1990) 115–142. · Zbl 0724.90049 · doi:10.1007/BF02055193 |
| [11] | J. Dupačová and R.J.-B. Wets, Asymptotic behaviour of statistical estimators and of optimal solutions of stochastic optimization problems, Ann. Statist. 16 (1988) 1517–1549. · Zbl 0667.62018 · doi:10.1214/aos/1176351052 |
| [12] | Y. Ermoliev and R.J.-B. Wets (eds.),Numerical Techniques for Stochastic Optimization (Springer, Berlin, 1988). · Zbl 0658.00020 |
| [13] | P. Gaenssler and W. Stute, Empirical processes: A survey of results for independent and identically distributed random variables, Ann. Prob. 7 (1979) 193–243. · Zbl 0402.60031 · doi:10.1214/aop/1176995085 |
| [14] | M. Gelbrich, On a formula for theL 2-Wasserstein metric between measures on Euclidean and Hilbert spaces, Math. Nachr. 147 (1990) 185–203. · Zbl 0711.60003 · doi:10.1002/mana.19901470121 |
| [15] | C.R. Givens and R.M. Shortt, A class of Wasserstein metrics for probability distributions, Michigan Math. J. 31 (1984) 231–240. · Zbl 0582.60002 · doi:10.1307/mmj/1029003026 |
| [16] | P. Kall,Stochastic Linear Programming (Springer, Berlin, 1976). · Zbl 0317.90042 |
| [17] | P. Kall, On approximations and stability in stochastic programming, in:Parametric Optimization and Related Topics, eds. J. Guddat, H.Th. Jongen, B. Kummer and F. Nožička (Akademie-Verlag, Berlin, 1987) pp. 387–407. |
| [18] | V. Kaňková, Estimates in stochastic programming-chance constrained case, Problems Control Inf. Theory, to appear. |
| [19] | A.J. King and R.J.-B. Wets, Epi-consistency of convex stochastic programs, Research Report, IBM Research Division, T.J. Watson Research Center, Yorktown Heights, New York (1989). · Zbl 0733.90049 |
| [20] | D. Klatte, A note on quantitative stability results in nonlinear optimization, in:Proc. 19. Jahrestagung Mathematische Optimierung, ed. K. Lommatzsch (Seminarbericht Nr. 90, Humboldt-Universität Berlin, Sektion Mathematik, 1987) pp. 77–86. · Zbl 0636.90082 |
| [21] | R. Lucchetti, G. Salinetti and R.J.-B. Wets Uniform convergence of probability measures: Topological criteria, Technical Report, University of California, Davis (1989). |
| [22] | H. Niederreiter and J.M. Wills, Diskrepanz und Distanz von Massen bezüglich konvexer und Jordanscher Mengen, Math. Zeits. 144 (1975) 125–134. · Zbl 0295.28028 · doi:10.1007/BF01190941 |
| [23] | C. van de Panne and W. Popp, Minimum cost cattle feed under probabilistic protein constraints, Manag. Sci. 9 (1963) 405–430. · doi:10.1287/mnsc.9.3.405 |
| [24] | A. Prékopa. Logarithmic concave measures with applications to stochastic programming, Acta Sci. Math. 32 (1971) 301–316. · Zbl 0235.90044 |
| [25] | A. Prékopa, Logarithmic concave measures and related topics, in:Stochastic Programming, ed. M.A.H. Dempster, (Academic Press, London, 1980) pp. 63–82. |
| [26] | S.T. Rachev, The Monge-Kantorovich mass transference problem and its stochastic applications, Theory Prob. Appl. 29 (1984) 647–676. · Zbl 0581.60010 · doi:10.1137/1129093 |
| [27] | Y. Rinott, On convexity of measures, Ann. Prob. 4 (1976) 1020–1026. · Zbl 0347.60003 · doi:10.1214/aop/1176995947 |
| [28] | S.M. Robinson, Stability theory for systems of inequalities, Part I: Linear systems, SIAM J. Num. Anal. 12 (1975) 754–769. · Zbl 0317.90035 · doi:10.1137/0712056 |
| [29] | S.M. Robinson, Regularity and stability for convex multivalued functions, Math. Oper. Res. 1 (1976) 130–143. · Zbl 0418.52005 · doi:10.1287/moor.1.2.130 |
| [30] | S.M. Robinson, Local epi-continuity and local optimization, Math. Progr. 37 (1987) 208–223. · Zbl 0623.90078 · doi:10.1007/BF02591695 |
| [31] | S.M. Robinson and R.J.-B. Wets, Stability in two-stage stochastic programming, SIAM J. Control Optim. 25 (1987) 1409–1416. · Zbl 0639.90074 · doi:10.1137/0325077 |
| [32] | R.T. Rockafellar, Lipschitzian properties of multifunctions, Nonlinear Anal. Theory, Meth. Appl. 9 (1985) 867–885. · Zbl 0573.54011 · doi:10.1016/0362-546X(85)90024-0 |
| [33] | W. Römisch and R. Schultz, Distribution sensitivity in stochastic programming, Math. Progr. (1991) to appear. · Zbl 0743.90083 |
| [34] | W. Römisch and R. Schultz, Distribution sensitivity for certain classes of chance constrained models–with application to power dispatch, J. Optim. Theory Appl., to appear. · Zbl 0793.90045 |
| [35] | W. Römisch and R. Schultz, Stability of solutions for stochastic programs with complete recourse havingC 1,1 data, Manuskript, Institut für Operations Research, Universität Zürich, Switzerland (1989). |
| [36] | W. Römisch and A. Wakolbinger, Obtaining convergence rates for approximations in stochastic programming, in:Parametric Optimization and Related Topics, eds. J. Guddat, H.Th. Jongen, B. Kummer and F. Nožička (Akademie-Verlag, Berlin, 1987) pp. 327–343. |
| [37] | G. Salinetti, Approximations for chance-constrained programming problems, Stochastics 10 (1983) 157–179. · Zbl 0536.90067 |
| [38] | A. Shapiro, Gâteaux, Fréchet and Hadamard directional differentiability of functional solutions in stochastic programming, Mimeograph Series No. 395, Operations Research and Statistics, Technion, Haifa, Israel (1988). |
| [39] | G.R. Shorack and J.A. Wellner,Empirical Processes with Applications to Statistics (Wiley, New York, 1986). · Zbl 1170.62365 |
| [40] | S. Vogel, Stability results for stochastic programming problems, Optimization 19 (1988) 269–288. · Zbl 0649.90078 · doi:10.1080/02331938808843343 |
| [41] | J. Wang, Continuity of feasible solution sets of probabilistic constrained programs, J. Optim. Theory Appl. 63 (1989) 79–89. · Zbl 0661.90066 · doi:10.1007/BF00940733 |
| [42] | R.J.-B. Wets, Stochastic programming: solution techniques and approximation schemes, in:Mathematical Programming–The State of the Art 1982, eds. A Bachem, M. Grötschel and B. Korte (Springer, Berlin, 1983) pp. 566–603. |
| [43] | R.J.-B. Wets, Stochastic programming, in:Handbooks in Operations Research and Management Science. Vol. 1: Optimization, eds. G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd (North-Holland, 1989) pp. 573–629. |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
