×

Nonlinear chance constrained problems: optimality conditions, regularization and solvers. (English) Zbl 1346.90634

Summary: We deal with chance constrained problems with differentiable nonlinear random functions and discrete distribution. We allow nonconvex functions both in the constraints and in the objective. We reformulate the problem as a mixed-integer nonlinear program and relax the integer variables into continuous ones. We approach the relaxed problem as a mathematical problem with complementarity constraints and regularize it by enlarging the set of feasible solutions. For all considered problems, we derive necessary optimality conditions based on Fréchet objects corresponding to strong stationarity. We discuss relations between stationary points and minima. We propose two iterative algorithms for finding a stationary point of the original problem. The first is based on the relaxed reformulation, while the second one employs its regularized version. Under validity of a constraint qualification, we show that the stationary points of the regularized problem converge to a stationary point of the relaxed reformulation and under additional condition it is even a stationary point of the original problem. We conclude the paper by a numerical example.

MSC:

90C15 Stochastic programming
90C26 Nonconvex programming, global optimization
49M05 Numerical methods based on necessary conditions

Software:

Matlab
Full Text: DOI

References:

[1] Charnes, A., Cooper, W.W., Symonds, G.H.: Cost horizons and certainty equivalents: an approach to stochastic programming of heating oil. Manag. Sci. 4(3), 235-263 (1958) · doi:10.1287/mnsc.4.3.235
[2] Rockafellar, R., Uryasev, S.: Conditional value-at-risk for general loss distributions. J. Bank. Finance 26(7), 1443-1471 (2002) · doi:10.1016/S0378-4266(02)00271-6
[3] Wozabal, D., Hochreiter, R., Pflug, G.C.: A difference of convex formulation of value-at-risk constrained optimization. Optimization 59(3), 377-400 (2010) · Zbl 1196.90088 · doi:10.1080/02331931003700731
[4] van Ackooij, W., Henrion, R., Möller, A., Zorgati, R.: Joint chance constrained programming for hydro reservoir management. Optim. Eng. 15(2), 509-531 (2014) · Zbl 1364.90232
[5] Ehmke, J.F., Campbell, A.M., Urban, T.L.: Ensuring service levels in routing problems with time windows and stochastic travel times. Eur. J. Oper. Res. 240(2), 539-550 (2015) · Zbl 1357.90015 · doi:10.1016/j.ejor.2014.06.045
[6] van Ackooij, W., Sagastizábal, C.: Constrained bundle methods for upper inexact oracles with application to joint chance constrained energy problems. SIAM J. Optim. 24(2), 733-765 (2014) · Zbl 1297.49057 · doi:10.1137/120903099
[7] Branda, M.: Optimization approaches to multiplicative tariff of rates estimation in non-life insurance. Asia Pac J. Oper. Res. 31(05), 1450,032 (2014) · Zbl 1299.91054 · doi:10.1142/S0217595914500328
[8] Klein Haneveld, W., Streutker, M., van der Vlerk, M.: An ALM model for pension funds using integrated chance constraints. Ann. Oper. Res. 177(1), 47-62 (2010) · Zbl 1195.91170 · doi:10.1007/s10479-009-0594-4
[9] Luedtke, J., Ahmed, S.: A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19(2), 674-699 (2008) · Zbl 1177.90301 · doi:10.1137/070702928
[10] Beraldi, P., Bruni, M.: An exact approach for solving integer problems under probabilistic constraints with random technology matrix. Ann. Oper. Res. 177(1), 127-137 (2010) · Zbl 1195.90066 · doi:10.1007/s10479-009-0670-9
[11] Luedtke, J., Ahmed, S., Nemhauser, G.: An integer programming approach for linear programs with probabilistic constraints. Math. Program. 122(2), 247-272 (2010) · Zbl 1184.90115 · doi:10.1007/s10107-008-0247-4
[12] Prékopa, A.: Dual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution. Zeitschrift für Oper. Res. 34(6), 441-461 (1990) · Zbl 0724.90048
[13] Van Ackooij, W., Berge, V., De Oliveira, W., Sagastizabal, C.: Probabilistic optimization via approximate p-efficient points and bundle methods. Working Paper (2014) · Zbl 1391.90450
[14] Shapiro, A., Dentcheva, D., Ruszczyński, A.: Lectures on Stochastic Programming. Society for Industrial and Applied Mathematics, Philadelphia (2009) · Zbl 1183.90005 · doi:10.1137/1.9780898718751
[15] Kogan, A., Lejeune, M.: Threshold boolean form for joint probabilistic constraints with random technology matrix. Math. Program. 147(1-2), 391-427 (2014) · Zbl 1297.90101 · doi:10.1007/s10107-013-0728-y
[16] Lejeune, M.A.: Pattern-based modeling and solution of probabilistically constrained optimization problems. Oper. Res. 60(6), 1356-1372 (2012) · Zbl 1269.90071 · doi:10.1287/opre.1120.1120
[17] Lejeune, M.A., Margot, F.: Solving chance-constrained optimization problems with stochastic quadratic inequalities. Tepper Working Paper E8 (2014) · Zbl 1348.90504
[18] Prékopa, A.; Ruszczyński, A. (ed.); Shapiro, A. (ed.), Probabilistic programming, No. 10, 267-351 (2003), Amsterdam · Zbl 1115.90001
[19] Dentcheva, D., Martinez, G.: Augmented Lagrangian method for probabilistic optimization. Ann. Oper. Res. 200(1), 109-130 (2012) · Zbl 1255.90087 · doi:10.1007/s10479-011-0884-5
[20] Sun, H., Xu, H., Wang, Y.: 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 (2014) · Zbl 1314.90059 · doi:10.1007/s10957-012-0127-1
[21] Haneveld, W., van der Vlerk, M.: Integrated chance constraints: reduced forms and an algorithm. Comput. Manag. Sci. 3(4), 245-269 (2006) · Zbl 1136.90424 · doi:10.1007/s10287-005-0007-3
[22] Nemirovski, A., Shapiro, A.: Convex approximations of chance constrained programs. SIAM J. Optim. 17(4), 969-996 (2007) · Zbl 1126.90056 · doi:10.1137/050622328
[23] Hong, L.J., Yang, Y., Zhang, L.: Sequential convex approximations to joint chance constrained programs: A Monte Carlo approach. Oper. Res. 59(3), 617-630 (2011) · Zbl 1231.90303 · doi:10.1287/opre.1100.0910
[24] Cheng, J., Houda, M., Lisser, A.: Chance constrained 0-1 quadratic programs using copulas. Optim. Lett. 9(7), 1283-1295 (2015) · Zbl 1332.90180 · doi:10.1007/s11590-015-0854-y
[25] Henrion, R., Möller, A.: A gradient formula for linear chance constraints under Gaussian distribution. Math. Oper. Res. 37(3), 475-488 (2012) · Zbl 1297.90095 · doi:10.1287/moor.1120.0544
[26] Raike, W.M.: Dissection methods for solutions in chance constrained programming problems under discrete distributions. Manag. Sci. 16(11), 708-715 (1970) · Zbl 0211.22601 · doi:10.1287/mnsc.16.11.708
[27] Rockafellar, R.T., Wets, R.J.B.: Variational Analysis. Springer, Berlin (1998) · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3
[28] Flegel, M.L., Kanzow, C.: On the Guignard constraint qualification for mathematical programs with equilibrium constraints. Optimization 54(6), 517-534 (2005) · Zbl 1147.90397 · doi:10.1080/02331930500342591
[29] Burdakov, O.; Kanzow, C.; Schwartz, A.; Gao, D. (ed.); Ruan, N. (ed.); Xing, W. (ed.), On a reformulation of mathematical programs with cardinality constraints, No. 95, 3-14 (2015), Berlin · Zbl 1327.90228
[30] Červinka, M., Kanzow, C., Schwartz, A.: Constraint qualifications and optimality conditions for optimization problems with cardinality constraints. Math. Program. (2016). doi:10.1007/s10107-016-0986-6 · Zbl 1356.90146
[31] Scholtes, S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11(4), 918-936 (2001) · Zbl 1010.90086 · doi:10.1137/S1052623499361233
[32] Bonami, P., Lodi, A., Tramontani, A., Wiese, S.: On mathematical programming with indicator constraints. Math. Program. 151(1), 191-223 (2015) · Zbl 1328.90086 · doi:10.1007/s10107-015-0891-4
[33] Shan, F., Zhang, L., Xiao, X.: A smoothing function approach to joint chance-constrained programs. J. Optim. Theory Appl. 163(1), 181-199 (2014) · Zbl 1333.90085 · doi:10.1007/s10957-013-0513-3
[34] Ioffe, A.D., Outrata, J.: On metric and calmness qualification conditions in subdifferential calculus. Set Valued Anal. 16(2-3), 199-227 (2008) · Zbl 1156.49013 · doi:10.1007/s11228-008-0076-x
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.