×

Augmented Lagrangian methods for solving optimization problems with stochastic-order constraints. (English) Zbl 1354.90082

Summary: We investigate risk-averse stochastic optimization problems with a risk-shaping constraint in the form of a stochastic-order relation. Both univariate and multivariate orders are considered. We extend the notion of a linear multivariate order, adding flexibility with respect to the controlled portion of the distributions. We propose several methods for the numerical solution of these problems based on augmented Lagrangian framework and analyze their convergence. The methods construct finite-dimensional risk-neutral approximations of the optimization problem whose solutions converge to the solution of the original problem. In the case of univariate stochastic dominance, we explore augmented Lagrangian functionals based on inverse formulations of the stochastic-order constraint. The performance of the methods is compared to other extant numerical methods and shows the numerical advantage of the augmented Lagrangian framework. The proposed numerical approach is particularly successful when applied to problems with multivariate stochastic dominance constraints.

MSC:

90C15 Stochastic programming

Software:

YALMIP
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Armbruster B, Luedtke J (2015) Models and formulations for multivariate dominance-constrained stochastic programs. IIE Trans. 47(1):1-14. CrossRef
[2] Birgin EG, Fernández D, Martínez JM (2012) The boundedness of penalty parameters in an augmented lagrangian method with constrained subproblems. Optim. Methods and Software 27(6):1001-1024. CrossRef · Zbl 1247.90247
[3] Bonnans JF, Shapiro A (2000) Perturbation Analysis of Optimization Problems, Springer Series in Operations Research and Financial Engineering, 1st ed., Vol. 4 (Springer, New York). CrossRef
[4] Dentcheva D, Martínez G (2012) Two-stage stochastic optimization problems with stochastic ordering constraints on the recourse. Eur. J. Oper. Res. 219(1):1-8. CrossRef · Zbl 1244.90174
[5] Dentcheva D, Ruszczyński A (2003) Optimization with stochastic dominance constraints. SIAM J. Optim. 14(2):548-566. CrossRef · Zbl 1055.90055
[6] Dentcheva D, Ruszczyński A (2004a) Optimality and duality theory for stochastic optimization problems with nonlinear dominance constraints. Math. Programming 99(2):329-350. CrossRef · Zbl 1098.90044
[7] Dentcheva D, Ruszczyński A (2004b) Convexification of stochastic ordering. Comptes Rendus de l’Academie Bulgare des Sciences 57(4):3-11. · Zbl 1083.90031
[8] Dentcheva D, Ruszczyński A (2006) Inverse stochastic dominance constraints and rank dependent expected utility theory. Math. Programming 108(2-3):297-311. CrossRef · Zbl 1130.91327
[9] 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
[10] Dentcheva D, Ruszczyński A (2009) Optimization with multivariate stochastic dominance constraints. Math. Programming 117(1-2):111-127. CrossRef · Zbl 1221.90069
[11] Dentcheva D, Ruszczyński A (2010a) Inverse cutting plane methods for optimization problems with second-order stochastic dominance constraints. Optimization 59(3):323-338. CrossRef · Zbl 1218.90143
[12] Dentcheva D, Ruszczyński A (2010b) Risk-averse portfolio optimization via stochastic dominance constraints. Handbook of Quantitative Finance and Risk Management (Springer, New York), 247-258. CrossRef · Zbl 1216.90064
[13] Dentcheva D, Wolfhagen E (2013) Optimization with multivariate stochastic dominance constraints. Deodatis G, Ellingwood BR, Frangopol DM, eds. Safety, Reliability, Risk and Life-Cycle Performance of Structures and Infrastructures. (CRC Press, Boca Raton, FL), 2603-2610.
[14] Dentcheva D, Wolfhagen E (2015) Optimization with multivariate stochastic dominance constraints. SIAM J. Optim. 25(1):564-588. CrossRef · Zbl 1358.90137
[15] Fishburn PC (1988) Utility Theory (John Wiley & Sons, New York).
[16] Hadar J, Russell WR (1969) Rules for ordering uncertain prospects. Amer. Econom. Rev. 59(1):25-34.
[17] Homem-de-Mello T, Mehrotra S (2009) A cutting-surface method for uncertain linear programs with polyhedral stochastic dominance constraints. SIAM J. Optim. 20(3):1250-1273. CrossRef · Zbl 1198.90291
[18] Hu J, Homem-de-Mello T, Mehrotra S (2012) Sample average approximation of stochastic dominance constrained programs. Math. programming 133(1-2):171-201. CrossRef · Zbl 1259.90083
[19] Lehmann EL (1955) Ordered families of distributions. Ann. Math. Statist. 26(3):399-419. CrossRef · Zbl 0065.11906
[20] Löfberg J (2004) YALMIP: A toolbox for modeling and optimization in MATLAB. IEEE Internat. Sympos. Comput. Aided Control Systems Design (IEEE, Piscataway, NJ), 284-289. CrossRef
[21] Lorenz MO (1905) Methods of measuring the concentration of wealth. Publications Amer. Statist. Assoc. 9(70):209-219. CrossRef
[22] 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(1):50-60. CrossRef · Zbl 0041.26103
[23] 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):111-140. CrossRef · Zbl 1296.90082
[24] Mosler KC, Scarsini M (1991) Stochastic Orders and Decision Under Risk (Institute of Mathematical Statistics, Hayward, CA).
[25] Müller A, Stoyan D (2002) Comparison Methods for Stochastic Models and Risks, Wiley Series in Probability and Statistics, Vol. 389 (John Wiley & Sons, Chichester, UK). · Zbl 0999.60002
[26] Noyan N, Rudolf G (2013) Optimization with multivariate conditional value-at-risk constraints. Oper. Res. 61(4):990-1013. Link · Zbl 1291.91124
[27] Ogryczak W, Ruszczyński A (2002) Dual stochastic dominance and related mean-risk models. SIAM J. Optim. 13(1):60-78. CrossRef · Zbl 1022.91017
[28] Quirk JP, Saposnik R (1962) Admissibility and measurable utility functions. Rev. Econom. Stud. 29(2):140-146. CrossRef
[29] Rockafellar RT (1974a) Conjugate Duality and Optimization, CBMS-NSF Regional Conference Series in Applied Mathematics (SIAM, Philadelphia). CrossRef
[30] Rockafellar RT (1974b) Augmented Lagrange multiplier function and duality in nonconvex programming. SIAM J. Control Optim. 12(2): 268-285. CrossRef · Zbl 0257.90046
[31] Rockafellar RT (1976) Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2):97-116. Link · Zbl 0402.90076
[32] 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(3):1326-1343. CrossRef · Zbl 1198.90308
[33] Ruszczyński A (2006) Nonlinear Optimization, Vol. 13 (Princeton University Press, Princeton, NJ). · Zbl 1108.90001
[34] Shaked M, Shanthikumar JG (1994) Stochastic Orders and Their Applications, Probability and Mathematical Statistics, 1st ed. (Springer, New York).
[35] Strassen V (1965) The existence of probability measures with given marginals. Ann. Math. Statist. 36(2):423-439. CrossRef · Zbl 0135.18701
[36] Szekli R (1995) Stochastic Ordering and Dependence in Applied Probability, Lecture Notes in Statistics (Springer, New York). CrossRef · Zbl 0815.60017
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.