×

Two-stage optimization problems with multivariate stochastic order constraints. (English) Zbl 1334.90089

Summary: We propose a two-stage risk-averse stochastic optimization problem with a stochastic-order constraint on a vector-valued function of the second-stage decisions. This model is motivated by a multiobjective second-stage problem. We formulate optimality conditions for the problem and analyse the Lagrangian relaxation of the order constraint. We propose two decomposition methods to solve the problems and prove their convergence. The methods are based on Lagrangian relaxation of the order constraints and on a construction of successive risk-neutral two-stage problems. Additionally, we propose a new combinatorial method for verification of the multivariate order relation, which is a key part of both methods. We analyse a supply chain problem using our model and we apply our methods to solve the optimization problem. Numerical results confirm the efficiency of the proposed methods.

MSC:

90C15 Stochastic programming
60E15 Inequalities; stochastic orderings
90B50 Management decision making, including multiple objectives

Software:

PLCP; DDSIP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Armbruster B, Luedtke J (2014) Models and formulations for multivariate dominance constrained stochastic programs. IIE Trans. 47: 1-14. CrossRef
[2] Benson HP (1999) Generalized {\(\gamma\)}-valid cut for concave minimization. J. Optim. Theory Appl. 102(2):289-298. CrossRef · Zbl 0937.90084
[3] Blackwell D (1953) Equivalent comparisons of experiments. Ann. Math. Statist. 24:265-272. CrossRef · Zbl 0050.36004
[4] Bonnans JF, Gilvert JC, Lemaréchal C, Sagastizábal C (2003) Numerical Optimization, Theoretical and Practical Aspects (Springer, Berlin).
[5] Branda M, Kopa M (2014) On relations between DEA-risk models and stochastic dominance effciency tests. Central Eur. J. Oper. Res. 22:13-35. CrossRef · Zbl 1339.90229
[6] Dentcheva D, Martinez G (2012) Two-stage stochastic optimization problems with stochastic ordering constraints on the recourse. Eur. J. Oper. Res. 219:1-8. CrossRef · Zbl 1244.90174
[7] Dentcheva D, Ruszczyński A (2003) Optimization with stochastic dominance constraints. SIAM J. Optim. 14:548-566. CrossRef · Zbl 1055.90055
[8] Dentcheva D, Ruszczyński A (2004) Optimality and duality theory for stochastic optimization problems with nonlinear dominance constraints. Math. Programming 99:329-350. CrossRef · Zbl 1098.90044
[9] Dentcheva D, Ruszczyński A (2006) Inverse stochastic dominance constraints and rank dependent expected utility theory. Math. Programming 108:297-311. CrossRef · Zbl 1130.91327
[10] Dentcheva D, Ruszczyński A (2008) Duality between coherent risk measures and stochastic dominance constraints in risk-averse optimization. Pacific J. Optim. 4(3):433-446. · Zbl 1206.90108
[11] Dentcheva D, Ruszczyński A (2009) Optimization with multivariate stochastic dominance constraints. Math. Programming 117:111-127. CrossRef · Zbl 1221.90069
[12] Dentcheva D, Ruszczyński A (2009) Stochastic dynamic optimization with discounted stochastic dominance constraints. SIAM J. Control Optim. 47(5):2540-2556. CrossRef · Zbl 1180.90211
[13] Dentcheva D, Wolfhagen E (2013) Optimization with multivariate stochastic dominance constraints. Deodatis G, Elingwood BR, Frangopol DM, eds. Safety, Reliability, Risk, and Life-Cycle Performance of Structures and Infrastructures. Proceedings of ICOSSAR 2013 (Taylor & Francis Group, London), 8.
[14] Dentcheva D, Wolfhagen E (2015) Optimization with multivariate stochastic dominance constraints. SIAM J. Optim. 25(1):564-588. CrossRef · Zbl 1358.90137
[15] Drapkin D, Schultz R (2011) An algorithm for stochastic programs with first-order dominance constraints induced by linear recourse. Preprint series, Department of Mathematics, University of Duisburg-Essen, Germany, 653-2007. · Zbl 1185.90160
[16] Fábián CI, Mitra G, Roman D (2011) Processing second-order stochastic dominance models using cutting-plane representations. Math. Programming 130:33-57. CrossRef · Zbl 1229.90108
[17] Gollmer R, Gotzes U, Neise F, Schultz R (2007) Risk modeling via stochastic dominance in power systems with dispersed generation. Technical report, Department of Mathematics, University of Duisburg-Essen, Germany.
[18] Gollmer R, Neise F, Schultz R (2008) Stochastic programs with first-order dominance constraints induced by mixed-integer linear recourse. SIAM J. Optim. 19:552-571. CrossRef · Zbl 1173.90490
[19] Grechuk B (2014) A simple SSD-efficiency test. Optim. Letters 8(7):2135-2143. CrossRef · Zbl 1308.90097
[20] Hardy GH, Littlewood JE, Pólya G (1934) Inequalities. (Cambridge University Press, Cambridge, UK).
[21] Homem-de-Mello T, Mehrotra S (2009) A cutting surface method for uncertain linear programs with polyhedral stochastic dominance constraints. SIAM J. Optim. 20:1250-1273. CrossRef · Zbl 1198.90291
[22] Hu J, Homem-de-Mello T, Mehrotra S (2012) Sample average approximation of stochastic dominance constrained programs. Math. Programming 133:171-201. CrossRef · Zbl 1259.90083
[23] Kiwiel KC (1985) Methods of descent for nondifferentiable optimization. Lecture Notes in Mathematics, Vol. 1133 (Springer-Verlag, Berlin). · Zbl 0561.90059
[24] Konno H (1976) A cutting plane algorithm for solving bilinear programs. Math. Programming 11:14-27. CrossRef · Zbl 0353.90069
[25] Lehmann E (1955) Ordered families of distributions. Ann. Math. Statist. 26:399-419. CrossRef · Zbl 0065.11906
[26] Lizyayev A, Ruszczyński A (2012) Tractable almost stochastic dominance. Eur. J. Oper. Res. 218:448-455. CrossRef · Zbl 1244.91112
[27] Lorenz MO (1905) Methods of measuring concentration of wealth. J. Amer. Statist. Assoc. 9:209-219. CrossRef
[28] Mann HB, Whitney DR (1947) On a test of whether one of two random variables is stochastically larger than the other. Ann. Math. Statist. 18:50-60. CrossRef · Zbl 0041.26103
[29] Meskarian R, Fliege J, Xu H (2014) Stochastic programming with multivariate second order stochastic dominance constraints with applications in portfolio optimization. Appl. Math. Optim. 70(1):1-30. CrossRef · Zbl 1296.90082
[30] Mosler K, Scarsini M eds. (1991) Stochastic Orders and Decision Under Risk. Lecture Notes–Monograph Series (Institute of Mathematical Statistics, Hayward, CA), 261-284. CrossRef · Zbl 0755.90006
[31] Müller A, Stoyan D (2002) Comparison Methods for Stochastic Models and Risks (John Wiley & Sons, Chichester, UK). · Zbl 0999.60002
[32] Ogryczak W, Ruszczyński A (2002) Dual stochastic dominance and related mean-risk models. SIAM J. Optim. 13:60-78. CrossRef · Zbl 1022.91017
[33] Quiggin J (1992) Efficient sets with and without the expected utility hypothesis: A generalization. J. Math. Econ. 21:395-399. CrossRef · Zbl 0762.90017
[34] Rockafellar RT (1974) Conjugate duality and optimization. CBMS-NSF Regional Conference Series in Applied Mathematics, Vol. 16 (SIAM, Philadelphia). · Zbl 0296.90036
[35] Rudolf G, Ruszczyński A (2008) Optimization problems with second order stochastic dominance constraints: duality, compact formulations, and cut generation methods. SIAM J. Optim. 19:1326-1343. CrossRef · Zbl 1198.90308
[36] Ruszczyński A (2006) Nonlinear Optimization (Princeton University Press, Princeton, NJ).
[37] Ruszczyński A, Shapiro A, eds. (2003) Stochastic Programming.Handbooks in Operations Research and Management Science, Vol. 10 (Elsevier, Amsterdam).
[38] Shaked M, Shanthikumar JG (1994) Stochastic Orders and Their Applications (Academic Press, Boston).
[39] Shapiro A, Dentcheva D, Ruszczyński A (2009) Lectures on Stochastic Programming.MPS-SIAM Series on Optimization (SIAM, Philadelphia). CrossRef
[40] Shorrocks AF (1983) Ranking income distributions. Economica, New Series 50:3-17. CrossRef
[41] Strassen V (1965) The existence of probability measures with given marginals. Ann. Math. Statist. 38:423-439. CrossRef · Zbl 0135.18701
[42] Wang SS, Yong VR, Panjer HH (1997) Axiomatic characterization of insurance prices. Insurance Math. Econom. 21:173-183. CrossRef · Zbl 0959.62099
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.