×

Ambiguous chance constrained problems and robust optimization. (English) Zbl 1134.90028

Summary: In this paper we study ambiguous chance constrained problems where the distributions of the random parameters in the problem are themselves uncertain. We focus primarily on the special case where the uncertainty set \(\mathcal Q\) of the distributions is of the form \(\mathcal Q = \{\mathbb Q : \rho_p(\mathbb Q,\mathbb Q_0) \leq \beta\}\), where \(\rho_p\) denotes the Prokhorov metric. The ambiguous chance constrained problem is approximated by a robust sampled problem where each constraint is a robust constraint centered at a sample drawn according to the central measure \(\mathbb Q_0\). The main contribution of this paper is to show that the robust sampled problem is a good approximation for the ambiguous chance constrained problem with a high probability. This result is established using the Strassen-Dudley Representation Theorem that states that when the distributions of two random variables are close in the Prokhorov metric one can construct a coupling of the random variables such that the samples are close with a high probability. We also show that the robust sampled problem can be solved efficiently both in theory and in practice.

MSC:

90C15 Stochastic programming
68Q32 Computational learning theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anthony, M., Biggs, N.: Computational Learning Theory. Cambridge University Press, 1992 · Zbl 0755.68115
[2] Artzner, Math. Finance, 9, 203 (1999) · Zbl 0980.91042 · doi:10.1111/1467-9965.00068
[3] Ben-Tal, SIAM J. Optim., 7, 991 (4) · Zbl 0899.90133 · doi:10.1137/S1052623495291951
[4] Ben-Tal, Math. Oper. Res., 23, 769 (4)
[5] Ben-Tal, Oper. Res. Lett., 25, 1 (1) · Zbl 0941.90053 · doi:10.1016/S0167-6377(99)00016-4
[6] Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization. SIAM, Philadelphia, PA, 2001 · Zbl 0986.90032
[7] Bertsimas, D., Sim, M.: Robust conic optimization (May 2004). Under review in Math. Prog. · Zbl 1134.90026
[8] Birge, Math. Prog. Study, 27, 54 (1986) · Zbl 0603.90104
[9] Blumer, J. ACM, 36, 929 (4) · Zbl 0697.68079 · doi:10.1145/76359.76371
[10] Calafiore, G., Campi, M.C.: Uncertain convex programs: Randomized solutions and confidence levels, 2003. To appear in Math. Prog. · Zbl 1177.90317
[11] Calafiore, G., Campi, M.C.: Decision making in an uncertain environment: the scenario-based optimization approach, 2004. Working paper
[12] Charnes, Mgmt. Sc., 6, 73 (1959) · Zbl 0995.90600
[13] Chen, Z., Epstein, L.: Ambiguity, risk and asset returns in continuous time, 2000. Mimeo · Zbl 1121.91359
[14] Dudley, Ann. Math. Stat., 39, 1563 (1968) · Zbl 0169.20602
[15] Dupačová, Stochastics, 20, 73 (1987) · Zbl 0616.90046
[16] Dupačová, J.: Stochastic programming: minimax approach. In: Encyclopedia of Optimization. Kluwer, 2001 · Zbl 0984.90027
[17] Ghaoui, SIAM J. Matrix Anal. Appl., 18, 1035 (4) · Zbl 0891.65039 · doi:10.1137/S0895479896298130
[18] Ghaoui, SIAM J. Optim., 9, 33 (1) · Zbl 0960.93007 · doi:10.1137/S1052623496305717
[19] Epstein, L.G., Schneider, M.: Recursive multiple priors. Tech. Rep. 485, Rochester Center for Economic Research, 2001. Available at http://rcer.econ.rochester.edu. To appear in J. Econ. Theory · Zbl 1107.91360
[20] Epstein, L.G., Schneider, M.: Learning under Ambiguity. Tech. Rep. 497, Rochester Center for Economic Research, 2002. Available at http://rcer.econ.rochester.edu. · Zbl 1206.91020
[21] Erdoğan, E., Iyengar, G.: Approximation algorithms for ambiguous chance constrained problems. February, 2004 · Zbl 1134.90028
[22] de Farias, D.P., Van Roy, B.: On constraint sampling in the linear programming approach to approximate dynamic programming, 2001. To appear in Math. Oper. Res. · Zbl 1082.90124
[23] Föllmer, Fin. and Stoch., 6, 429 (2002) · Zbl 1041.91039 · doi:10.1007/s007800200072
[24] El Ghaoui, L., Nilim, A.: The curse of uncertainty in dynamic programming and how to fix it, 2002. To appear in Oper. Res.. UC Berkeley Tech Report UCB-ERL-M02/31
[25] Gibbs, Intl. Stat. Rev., 7, 419 (3)
[26] Gilboa, J. Math. Econ., 18, 141 (2) · Zbl 0675.90012 · doi:10.1016/0304-4068(89)90018-9
[27] Goldfarb, Math. Oper. Res., 28, 1 (1) · Zbl 1082.90082 · doi:10.1287/moor.28.1.1.14260
[28] Hansen, American Economic Review, 91, 60 (2001) · doi:10.1257/aer.91.2.60
[29] Iyengar, G.: Robust dynamic programming 2002. To appear in Math. Oper. Res.. Available at http://www.corc.ieor.columbia.edu/reports/techreports/tr-2002-07.pd f
[30] Jagannathan, Oper. Res., 25, 173 (1977) · Zbl 0371.90105 · doi:10.1287/opre.25.1.173
[31] Kearns, M.J., Vazirani, U.V.: An introduction to computational learning theory. MIT Press, Cambridge, MA, 1997 · Zbl 0922.65002
[32] Long, Machine Learning, 37, 337 (3) · Zbl 0945.68083 · doi:10.1023/A:1007666507971
[33] Nemirovski, A.: On tractable approximations of randomly perturbed convex constraints. In: Proc. 42nd IEEE Conf. Dec. Contr. (CDC), vol. 3, 2003, pp. 2419-2422
[34] Nemirovski, A., Shapiro, A.: Scenario approximations of chance constraints, 2004. To appear in Probabilistic and randomized methods for design under uncertainty
[35] Rachev, S.T.: Probability metrics and the stability of stochastic models. John Wiley & Sons, 1991 · Zbl 0744.60004
[36] Rockafellar, R.T.: Convex analysis. Princeton University Press, Princeton, New Jersey, 1997 · Zbl 0932.90001
[37] Ruszczynski, A., Shapiro, A. (eds.): Stochastic Programming. Handbook in Operations Research and Management Science. Elsevier, 2003 · Zbl 1115.90001
[38] Ruszczynski, A., Shapiro, A.: Optimization of risk measures (2004). Available at http://www.optimization-online.org/DB_HTML/2004/02/822.html · Zbl 1181.90281
[39] Ruszczynski, A., Shapiro, A.: Optimization of risk measures (2004). Available at http://ideas.repec. org/p/wpa/wuwpri/0407002.html · Zbl 1181.90281
[40] Shapiro, A.: Some recent developments in stochastic programming. ORB Newsletter 13, 2004. Available at http://www.ballarat.edu.au/ard/itms/CIAO/ORBNewsletter/issue13. shtml#11
[41] Shapiro, A., Ahmed, S.: On a class of minimax stochastic programs, 2004. To appear in SIAM J. Opt. · Zbl 1073.90027
[42] Shapiro, Optimization Methods and Software, 17, 523 (2002) · Zbl 1040.90030 · doi:10.1080/1055678021000034008
[43] Strassen, Ann. Math. Stat., 36, 423 (1965) · Zbl 0135.18701
[44] Thorisson, H.: Coupling, Stationary, and Regeneration. Probability and its Applications. Springer-Verlag, 2000 · Zbl 0949.60007
[45] Vapnik, V.N.: The Nature of Statistical Learning Theory. Springer, New York, NY, 1995 · Zbl 0833.62008
[46] Žáčková, J.: On minimax solutions of stochastic linear programs. Čas. Pěst. Mat. 1966, pp. 423-430 · Zbl 0161.17102
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.