ALSO-X and ALSO-X+: Better Convex Approximations for Chance Constrained Programs

References

• Adler I, Monteiro RD (1992) A geometric view of parametric linear programming. Algorithmica 8(1–6):161–176.Crossref, Google Scholar
• Ahmed S, Papageorgiou DJ (2013) Probabilistic set covering with correlations. Oper. Res. 61(2):438–452.Link, Google Scholar
• Ahmed S, Shapiro A (2008) Solving chance-constrained stochastic programs via sampling and integer programming. Tutorials in Operations Research. (INFORMS, Hanover, MD), 261–269.Link, Google Scholar
• Ahmed S, Xie W (2018) Relaxations and approximations of chance constraints under finite distributions. Math. Programming 170(1):43–65.Crossref, Google Scholar
• Ahmed S, Luedtke J, Song Y, Xie W (2017) Nonanticipative duality, relaxations, and formulations for chance-constrained stochastic programs. Math. Programming 162(1–2):51–81.Crossref, Google Scholar
• Amaldi E, Kann V (1995) The complexity and approximability of finding maximum feasible subsystems of linear relations. Theoretical Comput. Sci. 147(1–2):181–210.Crossref, Google Scholar
• Ben-Tal A, Nemirovski A (2001) Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications (SIAM, Philadelphia).Crossref, Google Scholar
• Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust Optimization (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Beraldi P, Ruszczyński A (2002) The probabilistic set-covering problem. Oper. Res. 50(6):956–967.Link, Google Scholar
• Bertsimas D, Shtern S, Sturt B (2018) A data-driven approach to multi-stage stochastic linear optimization. Preprint, submitted November 3, http://www.optimization-online.org/DB _FILE/2018/11/6907.pdf.Google Scholar
• Bienstock D, Chertkov M, Harnett S (2014) Chance-constrained optimal power flow: Risk-aware network control under uncertainty. SIAM Rev. 56(3):461–495.Crossref, Google Scholar
• Blanchet J, Murthy K (2019) Quantifying distributional model risk via optimal transport. Math. Oper. Res. 44(2):565–600.Link, Google Scholar
• Boyle JP, Dykstra RL (1986) A method for finding projections onto the intersection of convex sets in Hilbert spaces. Advances in Order Restricted Statistical Rnference (Springer, Berlin), 28–47.Crossref, Google Scholar
• Calafiore GC, Campi MC (2006) The scenario approach to robust control design. IEEE Trans. Automated Control 51(5):742–753.Crossref, Google Scholar
• Charnes A, Cooper WW (1963) Deterministic equivalents for optimizing and satisficing under chance constraints. Oper. Res. 11(1):18–39.Link, Google Scholar
• Charnes A, Cooper WW, Symonds GH (1958) Cost horizons and certainty equivalents: An approach to stochastic programming of heating oil. Management Sci. 4(3):235–263.Link, Google Scholar
• Chen Z, Xie W (2021a) Sharing the value-at-risk under distributional ambiguity. Math. Finance 31(1):531–559.Crossref, Google Scholar
• Chen Z, Xie W (2021b) Regret in the newsvendor model with demand and yield randomness. Production Oper. Management 30(11):4176–4197.Crossref, Google Scholar
• Chen Z, Kuhn D, Wiesemann W (2018) Data-driven chance constrained programs over Wasserstein balls. Preprint, submitted September 1, 2018, https://arxiv.org/abs/1809.00210.Google Scholar
• Chow G (1995) Portfolio selection based on return, risk, and relative performance. Financial Anal. J. 51(2):54–60.Crossref, Google Scholar
• Deng Y, Shen S (2016) Decomposition algorithms for optimizing multi-server appointment scheduling with chance constraints. Math. Programming 157(1):245–276.Crossref, Google Scholar
• Dentcheva D, Prékopa A, Ruszczynski A (2000) Concavity and efficient points of discrete distributions in probabilistic programming. Math. Programming 89(1):55–77.Crossref, Google Scholar
• Embrechts P, McNeil A, Straumann D (2002) Correlation and dependence in risk management: Properties and pitfalls. Risk Management 1:176–223.Crossref, Google Scholar
• Fabozzi FJ, Markowitz HM, Kolm PN, Gupta F (2012) Mean-variance model for portfolio selection. Encyclopedia of Financial Models. (John Wiley & Sons, Ltd, Hoboken, NJ).Google Scholar
• Hanasusanto GA, Roitch V, Kuhn D, Wiesemann W (2015) A distributionally robust perspective on uncertainty quantification and chance constrained programming. Math. Programming 151(1):35–62.Crossref, Google Scholar
• Hanasusanto GA, Roitch V, Kuhn D, Wiesemann W (2017) Ambiguous joint chance constraints under mean and dispersion information. Oper. Res. 65(3):751–767.Link, Google Scholar
• Henrion R (2006) Some remarks on value-at-risk optimization. Internat. J. Management Sci. Engrg. Management 1(2):111–118.Google Scholar
• Henrion R (2007) Structural properties of linear probabilistic constraints. Optimization 56(4):425–440.Crossref, Google Scholar
• Henrion R, Strugarek C (2008) Convexity of chance constraints with independent random variables. Comput. Optim. Appl. 41(2):263–276.Crossref, Google Scholar
• Henrion R, Strugarek C (2011) Convexity of chance constraints with dependent random variables: the use of copulae. Stochastic Optimization Methods in Finance and Energy (Springer, Berlin), 427–439.Crossref, Google Scholar
• Hong LJ, Yang Y, Zhang L (2011) Sequential convex approximations to joint chance constrained programs: A Monte Carlo approach. Oper. Res. 59(3):617–630.Link, Google Scholar
• Jaworski P, Durante F, Hardle WK, Rychlik T (2010) Copula Theory and Its Applications, vol. 198 (Springer, Berlin).Crossref, Google Scholar
• Ji R, Lejeune MA (2021) Data-driven distributionally robust chance constrained optimization with Wasserstein metric. J. Global Optim. 79(4):779–811.Crossref, Google Scholar
• Kamdem JS (2005) Value-at-risk and expected shortfall for linear portfolios with elliptically distributed risk factors. Internat. J. Theoretical Appl. Finance 8(05):537–551.Crossref, Google Scholar
• Kataoka S (1963) A stochastic programming model. Econometrica 31(1–2):181–196.Crossref, Google Scholar
• Lagoa CM, Li X, Sznaier M (2005) Probabilistically constrained linear programs and risk-adjusted controller design. SIAM J. Optim. 15(3):938–951.Crossref, Google Scholar
• Landsman ZM, Valdez EA (2003) Tail conditional expectations for elliptical distributions. North Amer. Actuarial J. 7(4):55–71.Crossref, Google Scholar
• Lejeune MA, Margot F (2016) Solving chance-constrained optimization problems with stochastic quadratic inequalities. Oper. Res. 64(4):939–957.Link, Google Scholar
• Luedtke J, Ahmed S (2008) A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19(2):674–699.Crossref, Google Scholar
• Luedtke J, Ahmed S, Nemhauser GL (2010) An integer programming approach for linear programs with probabilistic constraints. Math. Programming 122(2):247–272.Crossref, Google Scholar
• Markowitz HM (1991) Foundations of portfolio theory. J. Finance 46(2):469–477.Crossref, Google Scholar
• Nemirovski A, Shapiro A (2006) Scenario approximations of chance constraints. Probabilistic and Randomized Methods for Design Under Uncertainty (Springer, Berlin), 3–47.Crossref, Google Scholar
• Nemirovski A, Shapiro A (2007) Convex approximations of chance constrained programs. SIAM J. Optim. 17(4):969–996.Crossref, Google Scholar
• Nemirovski A, Juditsky A, Lan G, Shapiro A (2009) Robust stochastic approximation approach to stochastic programmings. SIAM J. Optim. 19(4):1574–1609.Crossref, Google Scholar
• Nesterov Y (2003) Introductory Lectures on Convex Optimization: A Basic Course, vol. 87 (Springer Science & Business Media, New York).Google Scholar
• Pagnoncelli BK, Ahmed S, Shapiro A (2009) Sample average approximation method for chance constrained programming: Theory and applications. J. Optim. Theory Appl. 142(2):399–416.Crossref, Google Scholar
• Pena-Ordieres A, Luedtke JR, Wachter A (2020) Solving chance-constrained problems via a smooth sample-based nonlinear approximation. SIAM J. Optim. 30(3):2221–2250.Crossref, Google Scholar
• Prékopa A (1974) Programming under probabilistic constraints with a random technology matrix. Statistics 5(2):109–116.Google Scholar
• Prékopa A (2013) Stochastic Programming, vol. 324 (Springer Science & Business Media, New York).Google Scholar
• Qiu F, Ahmed S, Dey SS, Wolsey LA (2014) Covering linear programming with violations. INFORMS J. Comput. 26(3):531–546.Link, Google Scholar
• Rahimian H, Mehrotra S (2019) Distributionally robust optimization: A review. Preprint, submitted August 13, https://arxiv.org/abs/1908.05659.Google Scholar
• Rockafellar RT, Wets RJ (1982) On the interchange of subdifferentiation and conditional expectation for convex functionals. Stochastics 7(3):173–182.Crossref, Google Scholar
• Ruszczyński A (2002) Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra. Math. Programming 93(2):195–215.Crossref, Google Scholar
• Shiina T (1999) Numerical solution technique for joint chance-constrained programming problem: An application to electric power capacity expansion. J. Oper. Res. Soc. Japan 42(2):128–140.Google Scholar
• Song Y, Luedtke JR, Küçükyavuz S (2014) Chance-constrained binary packing problems. INFORMS J. Comput. 26(4):735–747.Link, Google Scholar
• Sun H, Xu H, Wang Y (2014) Asymptotic analysis of sample average approximation for stochastic optimization problems with joint chance constraints via conditional value at risk and difference of convex functions. J. Optim. Theory Appl. 161(1):257–284.Crossref, Google Scholar
• Suykens JA, Vandewalle J (1999) Least squares support vector machine classifiers. Neural Processing Lett. 9(3):293–300.Crossref, Google Scholar
• Takyi AK, Lence BJ (1999) Surface water quality management using a multiple-realization chance constraint method. Water Resources Res. 35(5):1657–1670.Crossref, Google Scholar
• Talluri S, Narasimhan R, Nair A (2006) Vendor performance with supply risk: A chance-constrained dea approach. Internat. J. Production Econom. 100(2):212–222.Crossref, Google Scholar
• Tao PD, An LTH (1997) Convex analysis approach to dc programming: Theory, algorithms and applications. Acta Math. Vietnam 22(1):289–355.Google Scholar
• Tavakoli R (2016) On the coupled continuous knapsack problems: Projection onto the volume constrained Gibbs n-simplex. Optim. Lett. 10(1):137–158.Crossref, Google Scholar
• Tibshirani R (1996) Regression shrinkage and selection via the lasso. J. Royal Statist. Soc. B 58(1):267–288.Crossref, Google Scholar
• Van Ackooij W, Malick J (2019) Eventual convexity of probability constraints with elliptical distributions. Math. Programming 175(1):1–27.Crossref, Google Scholar
• Xie W (2020) Tractable reformulations of two-stage distributionally robust linear programs over the type-∞ Wasserstein ball. Oper. Res. Lett. 48(4):513–523.Crossref, Google Scholar
• Xie W (2021) On distributionally robust chance constrained programs with Wasserstein distance. Math. Programming 186(1):115–155.Crossref, Google Scholar
• Xie W, Ahmed S (2017) Distributionally robust chance constrained optimal power flow with renewables: A conic reformulation. IEEE Trans. Power Systems 33(2):1860–1867.Crossref, Google Scholar
• Xie W, Ahmed S (2018a) On deterministic reformulations of distributionally robust joint chance constrained optimization problems. SIAM J. Optim. 28(2):1151–1182.Crossref, Google Scholar
• Xie W, Ahmed S (2018b) On quantile cuts and their closure for chance constrained optimization problems. Math. Programming 172(1–2):621–646.Crossref, Google Scholar
• Xie W, Ahmed S (2020) Bicriteria approximation of chance-constrained covering problems. Oper. Res. 68(2):516–533.Abstract, Google Scholar
• Zhang J, Xie W, Sarin SC (2021) Robust multi-product newsvendor model with uncertain demand and substitution. Eur. J. Oper. Res. 293(1):190–202.Crossref, Google Scholar
• Zhang Y, Shen S, Mathieu JL (2016) Distributionally robust chance-constrained optimal power flow with uncertain renewables and uncertain reserves provided by loads. IEEE Trans. Power Systems 32(2):1378–1388.Google Scholar
• Zymler S, Kuhn D, Rustem B (2013) Distributionally robust joint chance constraints with second-order moment information. Math. Programming 137(1–2):167–198.Crossref, Google Scholar