A Proximal Difference-of-Convex Algorithm for Sample Average Approximation of Chance Constrained Programming

References

• Ahmed S, Shapiro A (2008) Solving chance-constrained stochastic programs via sampling and integer programming. Chen Z-L, Raghavan S, eds. State-of-the-Art Decision-Making Tools in the Information-Intensive Age (INFORMS, Catonsville, MD), 261–269.Link, Google Scholar
• Attouch H, Bolte J (2009) On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. 116(1–2):5–16.Crossref, Google Scholar
• Attouch H, Bolte J, Svaiter BF (2013) Convergence of descent methods for semi-algebraic and tame problems: Proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math. Program. 137(1–2):91–129.Crossref, Google Scholar
• Attouch H, Bolte J, Redont P, Soubeyran A (2010) Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res. 35(2):438–457.Link, Google Scholar
• Bai X, Sun J, Zheng X (2021) An augmented Lagrangian decomposition method for chance-constrained optimization problems. INFORMS J. Comput. 33(3):1056–1069.Link, 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
• Bolte J, Sabach S, Teboulle M (2014) Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146(1):459–494.Crossref, Google Scholar
• Bonami P, Lejeune MA (2009) An exact solution approach for portfolio optimization problems under stochastic and integer constraints. Oper. Res. 57(3):650–670.Link, Google Scholar
• Calafiore GC, Campi MC (2006) The scenario approach to robust control design. IEEE Trans. Automatic Control 51(5):742–753.Crossref, Google Scholar
• Calafiore GC, Ghaoui LE (2006) On distributionally robust chance-constrained linear programs. J. Optim. Theory Appl. 130(1):1–22.Crossref, Google Scholar
• Cao Y, Zavala VM (2020) A sigmoidal approximation for chance-constrained nonlinear programs. Preprint, submitted April 6, https://arxiv.org/abs/2004.02402.Google Scholar
• Charnes A, Cooper WW (1959) Chance-constrained programming. Management Sci. 6(1):73–79.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 FY, Krass D (2001) Inventory models with minimal service level constraints. Eur. J. Oper. Res. 134(1):120–140.Crossref, Google Scholar
• Cui Y, Liu J, Pang JS (2022) Nonconvex and nonsmooth approaches for affine chance-constrained stochastic programs. Set-Valued Variational Anal. 30(3):1149–1211.Crossref, Google Scholar
• Cui X, Sun X, Zhu S, Jiang R, Li D (2018) Portfolio optimization with nonparametric value at risk: A block coordinate descent method. INFORMS J. Comput. 30(3):454–471.Link, Google Scholar
• Curtis FE, Wächter A, Zavala VM (2018) A sequential algorithm for solving nonlinear optimization problems with chance constraints. SIAM J. Optim. 28(1):930–958.Crossref, Google Scholar
• Dentcheva D, Martinez G (2013) Regularization methods for optimization problems with probabilistic constraints. Math. Program. 138(1):223–251.Crossref, Google Scholar
• Dentcheva D, Prékopa A, Ruszczynski A (2000) Concavity and efficient points of discrete distributions in probabilistic programming. Math. Program. 89:55–77.Crossref, Google Scholar
• Dielman T, Lowry C, Pfaffenberger R (1994) A comparison of quantile estimators. Comm. Statist. Simul. Comput. 23(2):355–371.Crossref, Google Scholar
• Geletu A, Hoffmann A, Klöppel M, Li P (2017) An inner-outer approximation approach to chance constrained optimization. SIAM J. Optim. 27(3):1834–1857.Crossref, Google Scholar
• Ghaoui LE, Oks M, Oustry F (2003) Worst-case value-at-risk and robust portfolio optimization: A conic programming approach. Oper. Res. 51(4):543–556.Link, Google Scholar
• Gurvich I, Luedtke J, Tezcan T (2010) Staffing call centers with uncertain demand forecasts: A chance-constrained optimization approach. Management Sci. 56(7):1093–1115.Link, 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
• Hiriart-Urruty JB, Lemaréchal C (2004) Fundamentals of Convex Analysis (Springer Science & Business Media, Berlin).Google Scholar
• Hong LJ, Liu G (2009) Simulating sensitivities of conditional value at risk. Management Sci. 55(2):281–293.Link, 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
• Horst R, Thoai NV (1999) DC programming: Overview. J. Optim. Theory Appl. 103(1):1–43.Crossref, Google Scholar
• Jadhav D, Ramanathan T (2009) Parametric and non-parametric estimation of value-at-risk. J. Risk Model Validation 3(1):51.Crossref, Google Scholar
• Jiang N, Xie W (2022) ALSO-X and ALSO-X+: Better convex approximations for chance constrained programs. Oper. Res. 70(6):3581–3600.Link, Google Scholar
• Jiang R, Li D (2019) Novel reformulations and efficient algorithms for the generalized trust region subproblem. SIAM J. Optim. 29(2):1603–1633.Crossref, Google Scholar
• Jiang R, Li X (2022) Hölderian error bounds and Kurdyka-Łojasiewicz inequality for the trust region subproblem. Math. Oper. Res. 47(4):3025–3050.Link, Google Scholar
• Kannan R, Luedtke JR (2021) A stochastic approximation method for approximating the efficient frontier of chance-constrained nonlinear programs. Math. Program. Comput. 13(4):705–751.Crossref, Google Scholar
• Kogan A, Lejeune MA (2014) Threshold Boolean form for joint probabilistic constraints with random technology matrix. Math. Program. 147:391–427.Crossref, Google Scholar
• Kogan A, Lejeune MA, Luedtke J (2016) Erratum to: Threshold Boolean form for joint probabilistic constraints with random technology matrix. Math. Program. 155:617–620.Crossref, Google Scholar
• Küçükyavuz S (2012) On mixing sets arising in chance-constrained programming. Math. Program. 132(1):31–56.Crossref, Google Scholar
• Küçükyavuz S, Jiang R (2022) Chance-constrained optimization under limited distributional information: A review of reformulations based on sampling and distributional robustness. EURO J. Comput. Optim. 10:100030.Crossref, Google Scholar
• Kurdyka K (1998) On gradients of functions definable in o-minimal structures. Annal. L’institut Fourier 48(3):769–783.Crossref, Google Scholar
• Lacoste-Julien S (2016) Convergence rate of Frank-Wolfe for non-convex objectives. Preprint, submitted July 1, https://arxiv.org/abs/1607.00345.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
• Laguel Y, Malick J, van Ackooij W (2024) Chance-constrained programs with convex underlying functions: A bilevel convex optimization perspective. Comput. Optim. Appl. 88(3):819–847.Crossref, Google Scholar
• Le Thi HA, Pham Dinh T (2018) DC programming and DCA: Thirty years of developments. Math. Program. 169(1):5–68.Crossref, Google Scholar
• Le Thi HA, Huynh VN, Pham Dinh T (2014) DC programming and DCA for general DC programs. van Do T, Thi H, Nguyen N, eds. Advanced Computational Methods for Knowledge Engineering (Springer, Cham, Switzerland), 15–35.Crossref, Google Scholar
• Le Thi HA, Pham Dinh T, Ngai HV (2012) Exact penalty and error bounds in DC programming. J. Glob. Optim. 52(3):509–535.Crossref, Google Scholar
• Li G, Pong TK (2018) Calculus of the exponent of Kurdyka–Łojasiewicz inequality and its applications to linear convergence of first-order methods. Found. Comput. Math. 18(5):1199–1232.Crossref, Google Scholar
• Li Q, Racine JS (2007) Nonparametric Econometrics: Theory and Practice (Princeton University Press, Princeton, NJ).Google Scholar
• Liu T, Pong TK, Takeda A (2019b) A refined convergence analysis of pDCAe with applications to simultaneous sparse recovery and outlier detection. Comput. Optim. Appl. 73(1):69–100.Crossref, Google Scholar
• Liu H, So AMC, Wu W (2019a) Quadratic optimization with orthogonality constraint: Explicit Łojasiewicz exponent and linear convergence of retraction-based line-search and stochastic variance-reduced gradient methods. Math. Program. 178(1):215–262.Crossref, Google Scholar
• Lu Z (2012) Sequential convex programming methods for a class of structured nonlinear programming. Preprint, submitted October 10, https://arxiv.org/abs/1210.3039v1.Google Scholar
• Lu Z, Sun Z, Zhou Z (2022) Penalty and augmented Lagrangian methods for constrained DC programming. Math. Oper. Res. 47(3):2260–2285.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. Program. 122(2):247–272.Crossref, Google Scholar
• Martins-Filho C, Yao F, Torero M (2018) Nonparametric estimation of conditional value-at-risk and expected shortfall based on extreme value theory. Econom. Theory 34(1):23–67.Crossref, Google Scholar
• Nemirovski A, Shapiro A (2006) Scenario approximations of chance constraints. Calafiore G, Dabbene F, eds. Probabilistic and Randomized Methods for Design under Uncertainty (Springer, London), 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
• 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
• Pang JS, Razaviyayn M, Alvarado A (2017) Computing B-stationary points of nonsmooth DC programs. Math. Oper. Res. 42(1):95–118.Link, Google Scholar
• Parzen E (1979) Nonparametric statistical data modeling. J. Amer. Statist. Assoc. 74(365):105–121.Crossref, Google Scholar
• Peña-Ordieres A, Luedtke JR, Wächter A (2020) Solving chance-constrained problems via a smooth sample-based nonlinear approximation. SIAM J. Optim. 30(3):2221–2250.Crossref, Google Scholar
• Pham Dinh T, Le Thi HA (1997) Convex analysis approach to dc programming: Theory, algorithms and applications. Acta Math. Vietnamica 22(1):289–355.Google Scholar
• Pham Dinh T, Le Thi HA (2014) Recent advances in DC programming and DCA. Trans. Comput. Intelligence XIII:1–37.Google Scholar
• Prékopa A (2003) Probabilistic programming. Ruszczynski A, Shapiro A, eds. Stochastic Programming, Handbooks in Operations Research and Management Science, vol. 10 (Elsevier, Amsterdam), 267–351.Crossref, Google Scholar
• Rockafellar RT (1970) Convex Analysis, Princeton Landmarks in Mathematics and Physics, vol. 18 (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Rockafellar RT, Wets RJB (2004) Variational Analysis, Grundlehren Der Mathematischen Wissenschaften, 2nd ed., vol. 317 (Springer Verlag, Berlin, Heidelberg).Google Scholar
• Ruszczyński A (2002) Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra. Math. Program. 93(2):195–215.Crossref, Google Scholar
• Shan F, Zhang L, Xiao X (2014) A smoothing function approach to joint chance-constrained programs. J. Optim. Theory Appl. 163(1):181–199.Crossref, Google Scholar
• Shen X, Ouyang T, Yang N, Zhuang J (2023) Sample-based neural approximation approach for probabilistic constrained programs. IEEE Trans. Neural Networks Learn. Systems 34(2):1058–1065.Crossref, Google Scholar
• van Ackooij W, Pérez-Aros P, Soto C, Vilches E (2023) Inner Moreau envelope of nonsmooth conic chance constrained optimization problems. Preprint, submitted January 24, https://arxiv.org/abs/2301.09803.Google Scholar
• van Ackooij W, Demassey S, Javal P, Morais H, de Oliveira W, Swaminathan B (2021) A bundle method for nonsmooth DC programming with application to chance-constrained problems. Comput. Optim. Appl. 78(2):451–490.Crossref, Google Scholar
• van der Vaart AW (2000) Asymptotic Statistics, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 3 (Cambridge University Press, Cambridge, UK).Google Scholar
• Wang P, Liu H, So AMC (2021) Linear convergence of a proximal alternating minimization method with extrapolation for ℓ1-norm principal component analysis. Preprint, submitted July 15, https://arxiv.org/abs/2107.07107.Google Scholar
• Wang P, Jiang R, Kong Q, Balzano L (2025) A proximal difference-of-convex algorithm for sample average approximation of chance constrained programming. http://dx.doi.org/10.1287/ijoc.2024.0648.cd, https://github.com/INFORMSJoC/2024.0648.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 (2020) Bicriteria approximation of chance-constrained covering problems. Oper. Res. 68(2):516–533.Abstract, Google Scholar
• Ye J, Zhu D (1995) Optimality conditions for bilevel programming problems. Optimization 33(1):9–27.Crossref, Google Scholar
• Yu P, Pong TK, Lu Z (2021) Convergence rate analysis of a sequential convex programming method with line search for a class of constrained difference-of-convex optimization problems. SIAM J. Optim. 31(3):2024–2054.Crossref, Google Scholar
• Yurtsever A, Sra S (2022) CCCP is Frank-Wolfe in disguise. Adv. Neural Inform. Processing Systems 35:35352–35364.Google Scholar
• Zheng T, Wang P, So AM-C (2022) A linearly convergent algorithm for rotationally invariant ℓ1-norm principal component analysis. Preprint, submitted October 26, https://arxiv.org/abs/2210.05066.Google Scholar