Probabilistic optimization via approximate \(p\)-efficient points and bundle methods. (English) Zbl 1391.90450
Summary: For problems when decisions are taken prior to observing the realization of underlying random events, probabilistic constraints are an important modeling tool if reliability is a concern. A key concept to numerically dealing with probabilistic constraints is that of \(p\)-efficient points. By adopting a dual point of view, we develop a solution framework that includes and extends various existing formulations. The unifying approach is built on the basis of a recent generation of bundle methods called with on-demand accuracy, characterized by its versatility and flexibility. Numerical results for several difficult problems confirm the interest of the approach.
MSC:
| 90C15 | Stochastic programming |
| 90C25 | Convex programming |
| 65K05 | Numerical mathematical programming methods |
| 90C30 | Nonlinear programming |
| 90C90 | Applications of mathematical programming |
Keywords:
probabilistic constraints; stochastic programming; duality; bundle methods; \(p\)-efficient pointsReferences:
| [1] | Morgan, D.; Eheart, J.; Valocchi, A., Aquifer remediation design under uncertainty using a new chance constraint programming technique, Water Resour Res, 29, 551-561, (1993) |
| [2] | Prékopa, A.; Szántai, T., Flood control reservoir system design using stochastic programming, Math Program Study, 9, 138-151, (1978) · Zbl 0385.90073 |
| [3] | Prékopa, A.; Szántai, T., On optimal regulation of a storage level with application to the water level regulation of a lake, Eur J Oper Res, 3, 175-189, (1979) · Zbl 0399.90051 |
| [4] | van Ackooij, W.; Henrion, R.; Möller, A.; Zorgati, R., Joint chance constrained programming for hydro reservoir management, Optim Eng, 15, 509-531, (2014) · Zbl 1364.90232 |
| [5] | Henrion, R.; Strugarek, C., Convexity of chance constraints with dependent random variablesthe use of copulae, (Bertocchi, M.; Consigli, G.; Dempster, M., Stochastic optimization methods in finance and energy: new financial products and energy market strategies, International series in operations research and management science, (2011), Springer-Verlag New York), 427-439 · Zbl 1405.91116 |
| [6] | van Ackooij, W., Eventual convexity of chance constrained feasible sets, Optimization (J Math Program Oper Res), 64, 5, 1263-1284, (2015) · Zbl 1321.49042 |
| [7] | van Ackooij, W.; de Oliveira, W., Convexity and optimization with copulae structured probabilistic constraints, Optimization: J Math Program Oper Res, 65, 7, 1349-1376, (2016) · Zbl 1345.49042 |
| [8] | Prékopa, A., Probabilistic programming, (Ruszczyński, A.; Shapiro, A., Stochastic programming, Handbooks in operations research and management science, vol. 10, (2003), Elsevier Amsterdam), 267-351 · Zbl 1115.90001 |
| [9] | Prékopa, A., Stochastic programming, (1995), Kluwer Dordrecht · Zbl 0834.90098 |
| [10] | Luedtke, J.; Ahmed, S., A sample approximation approach for optimization with probabilistic constraints, SIAM J Optim, 19, 674-699, (2008) · Zbl 1177.90301 |
| [11] | Luedtke, J., A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support, Math Program, 146, 1-2, 219-244, (2014) · Zbl 1297.90092 |
| [12] | Calafiore, G. C.; Campi, M. C., Uncertain convex programsrandomized solutions and confidence levels, Math Program, 102, 1, 25-46, (2005) · Zbl 1177.90317 |
| [13] | Campi, M. C.; Garatti, S., A sampling-and-discarding approach to chance-constrained optimizationfeasibility and optimality, J Optim Theory Appl, 148, 2, 257-280, (2011) · Zbl 1211.90146 |
| [14] | Lejeune, M. A., Pattern-based modeling and solution of probabilistically constrained optimization problems, Oper Res, 60, 6, 1356-1372, (2012) · Zbl 1269.90071 |
| [15] | Lejeune, M. A., Pattern definition of the p-efficiency concept, Ann Oper Res, 200, 23-36, (2012) · Zbl 1261.90032 |
| [16] | Dentcheva, D., Optimisation models with probabilistic constraints, (Shapiro, A.; Dentcheva, D.; Ruszczyński, A., Lectures on stochastic programming. Modeling and theory. MPS-SIAM series on optimization, vol. 9, (2009), SIAM and MPS Philadelphia), 87-154 · Zbl 1183.90005 |
| [17] | Dentcheva, D.; Martinez, G., Regularization methods for optimization problems with probabilistic constraints, Math Program (Ser A), 138, 1-2, 223-251, (2013) · Zbl 1276.90043 |
| [18] | Prékopa, A., Dual method for a one-stage stochastic programming problem with random rhs obeying a discrete probability distribution, Z Oper Res, 34, 441-461, (1990) · Zbl 0724.90048 |
| [19] | 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 |
| [20] | van Ackooij, W.; de Oliveira, W., Level bundle methods for constrained convex optimization with various oracles, Comput Optim Appl, 57, 3, 555-597, (2014) · Zbl 1329.90109 |
| [21] | Bremer, I.; Henrion, R.; Möller, A., Probabilistic constraints via SQP solverapplication to a renewable energy management problem, Comput Manag Sci, 12, 435-459, (2015) · Zbl 1317.90216 |
| [22] | van Ackooij, W.; Henrion, R., Gradient formulae for nonlinear probabilistic constraints with gaussian and Gaussian-like distributions, SIAM J Optim, 24, 4, 1864-1889, (2014) · Zbl 1319.93080 |
| [23] | van Ackooij W, Henrion R. (Sub-) gradient formulae for probability functions of random inequality systems under Gaussian distribution, WIAS preprint 2016;2230:1-24, submitted for publication. · Zbl 1434.90111 |
| [24] | Prékopa, A.; Vízvári, B.; Badics, T., Programming under probabilistic constraints with discrete random variable, (Giannessi, F.; Komlósi, S.; Rapcsák, T., New trends in mathematical programming: Hommage to Steven Vajda, Applied optimization, vol. 13, (1998), Dordrecht: Springer), 235-255, http://www.springer.com/fr/book/9780792350361?wt_mc=ThirdParty.SpringerLink.3.EPR653.About_eBook#otherversion=9781441947932 · Zbl 0907.90215 |
| [25] | Mayer, J., On the numerical solution of jointly chance constrained problems, (Uryas’ev, S., Probabilistic constrained optimization: methodology and applications, (2000), Dordrecht: Kluwer Academic Publishers), 220-235, http://link.springer.com/chapter/10.1007 · Zbl 0991.90092 |
| [26] | Dentcheva, D.; Martinez, G., Augmented Lagrangian method for probabilistic optimization, Ann Oper Res, 200, 1, 109-130, (2012) · Zbl 1255.90087 |
| [27] | de Oliveira, W.; Sagastizábal, C.; Lemaréchal, C., Convex proximal bundle methods in deptha unified analysis for inexact oracles, Math Prog Ser B, 148, 241-277, (2014) · Zbl 1327.90321 |
| [28] | Dentcheva, D.; Lai, B.; Ruszczyński, A., Dual methods for probabilistic optimization problems, Math Methods Oper Res, 60, 2, 331-346, (2004) · Zbl 1076.90038 |
| [29] | Lemaréchal, C.; Renaud, A., A geometric study of duality gaps, with applications, Math Program, 90, 399-427, (2001) · Zbl 1039.90087 |
| [30] | Dentcheva, D.; Prékopa, A.; Ruszczyński, A., Concavity and efficient points for discrete distributions in stochastic programming, Math Program, 89, 55-77, (2000) · Zbl 1033.90078 |
| [31] | Prékopa, A., Logarithmic concave measures with applications to stochastic programming, Acta Sci Math (Szeged), 32, 301-316, (1971) · Zbl 0235.90044 |
| [32] | Tahanan, M.; van Ackooij, W.; Frangioni, A.; Lacalandra, F., Large-scale unit commitment under uncertaintya literature survey, 4OR, 13, 2, 115-171, (2015) · Zbl 1321.90007 |
| [33] | Dubost, L.; Gonzalez, R.; Lemaréchal, C., A primal-proximal heuristic applied to French unit-commitment problem, Math Program, 104, 1, 129-151, (2005) · Zbl 1077.90083 |
| [34] | Lejeune, M. A.; Ruszczyński, A., An efficient trajectory method for probabilistic production-inventory-distribution problems, Oper Res, 55, 2, 378-394, (2007) · Zbl 1167.90489 |
| [35] | Lejeune, M. A.; Noyan, N., Mathematical programming approaches for generating p-efficient points, Eur J Oper Res, 207, 2, 590-600, (2010) · Zbl 1205.90210 |
| [36] | 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 |
| [37] | Lejeune, M.; Margot, F., Solving chance-constrained optimization problems with stochastic quadratic inequalities, Oper Res, 1-39, (2016) |
| [38] | Boros, E.; Hammer, P. L.; Ibaraki, T.; Kogan, A., Logical analysis of numerical data, Math Program, 79, 1, 163-190, (1997) · Zbl 0887.90179 |
| [39] | Boros, E.; Hammer, P. L.; Ibaraki, T.; Kogan, A.; Mayoraz, E.; Muchnik, I., An implementation of logical analysis of data, IEEE Trans Knowl Data Eng, 12, 2, 292-306, (2000) |
| [40] | Kogan, A.; Lejeune, M. A.; Luedtke, J., Erratum tothreshold Boolean form for joint probabilistic constraints with random technology matrix, Math Program, 155, 1, 617-620, (2016) · Zbl 1464.90044 |
| [41] | Kogan, A.; Lejeune, M. A., Threshold Boolean form for joint probabilistic constraints with random technology matrix, Math Program, 147, 1-2, 391-427, (2014) · Zbl 1297.90101 |
| [42] | Pagès, G.; Printems, J., Optimal quadratic quantization for numericsthe Gaussian case, Monte Carlo Methods Appl, 9, 2, 135-166, (2003) · Zbl 1029.65012 |
| [43] | Shapiro A, Dentcheva D, Ruszczyński A. Lectures on stochastic programming. Modeling and theory, MPS-SIAM series on optimization, vol. 9. SIAM and MPS, Philadelphia; 2009. · Zbl 1183.90005 |
| [44] | Ruszczyński, A., Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra, Math Program, 93, 195-215, (2002) · Zbl 1065.90058 |
| [45] | Henrion R. Introduction to chance constraint programming, Tutorial paper for the stochastic programming community homepage, 〈http://www.wias-berlin.de/people/henrion/publikat.html〉; 2004. |
| [46] | Moreau, J. J., Proximité et dualité dans un espace hilbertien, Bull Soc Math France, 93, 273-299, (1965) · Zbl 0136.12101 |
| [47] | Rockafellar, R. T., Monotone operators and the proximal point algorithm, SIAM J Control Optim, 14, 877-898, (1976) · Zbl 0358.90053 |
| [48] | Bonnans, J.; Gilbert, J.; Lemaréchal, C.; Sagastizábal, C., Numerical optimization: theoretical and practical aspects, (2006), Berlin: Springer-Verlag, http://www.springer.com/us/book/9783540354451 · Zbl 1108.65060 |
| [49] | de Oliveira, W.; Sagastizábal, C., Bundle methods in the XXI centurya birds’-eye view, Pesqui Oper, 34, 3, 647-670, (2014) |
| [50] | Kiwiel, K., A proximal bundle method with approximate subgradient linearizations, SIAM J Optim, 16, 4, 1007-1023, (2006) · Zbl 1104.65055 |
| [51] | Wolf, C.; Fábián, C. I.; Koberstein, A.; Stuhl, L., Applying oracles of on-demand accuracy in two-stage stochastic programming—a computational study, Eur J Oper Res, 239, 2, 437-448, (2014) · Zbl 1339.90257 |
| [52] | Zaourar, S.; Malick, J., Prices stabilization for inexact unit-commitment problems, Math Methods Oper Res, 78, 3, 341-359, (2013) · Zbl 1291.90300 |
| [53] | Hintermüller, M., A proximal bundle method based on approximate subgradients, Comput Optim Appl, 20, 245-266, (2001) · Zbl 1054.90053 |
| [54] | Rockafellar, R. T.; Wets, R.-B., A Lagrangian finite generation technique for solving linear-quadratic problems in stochastic programming, Math Program Study, 28, 63-93, (1986) · Zbl 0599.90090 |
| [55] | Lemaréchal, C., Lagrangian decomposition and nonsmooth optimizationbundle algorithm, prox iteration, augmented Lagrangian, (Giannessi, F., Nonsmooth optimization methods and applications, (1992), Amsterdam: Gordon & Breach), 201-216, https://www.amazon.com/Nonsmooth-Optimization-Methods-F-Giannessi/dp/2881248780 · Zbl 1050.90553 |
| [56] | Genz A, Bretz F. Computation of multivariate normal and T probabilities. Lecture notes in statistics, vol. 195. Dordrecht: Springer; 2009. · Zbl 1204.62088 |
| [57] | Dolan, E. D.; Moré, J. J., Benchmarking optimization software with performance profiles, Math Program, 91, 201-213, (2002) · Zbl 1049.90004 |
| [58] | Gaudioso M, Giallombardo G, Miglionico G. An incremental method for solving convex finite min-max problems. Math Oper Res 2006;31. · Zbl 1278.90439 |
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.
