Augmented Lagrangian method for probabilistic optimization. (English) Zbl 1255.90087

Summary: We analyze nonlinear stochastic optimization problems with probabilistic constraints described by continuously differentiable non-convex functions. We describe the tangent and the normal cone to the level sets of the underlying probability function and provide new insight into their structure. Furthermore, we formulate fist order and second order conditions of optimality for these problems based on the notion of \(p\)-efficient points. We develop an augmented Lagrangian method for the case of discrete distribution functions. The method is based on progressive inner approximation of the level set of the probability function by generation of \(p\)-efficient points. Numerical experience is provided.


90C15 Stochastic programming
90C46 Optimality conditions and duality in mathematical programming
Full Text: DOI


[1] Bonnans, J. F., & Shapiro, A. (2000). Perturbation analysis of optimization problems. New York: Springer. · Zbl 0966.49001
[2] Dentcheva, D., & Martinez, G. (2010, submitted). Regularization in probabilistic optimization. · Zbl 1276.90043
[3] Dentcheva, D., Prékopa, A., & Ruszczyński, A. (2000). Concavity and efficient points of discrete distributions in probabilistic programming. Mathematical Programming, 89, 55–77. · Zbl 1033.90078
[4] Dentcheva, D., Prékopa, A., & Ruszczyński, A. (2002). Bounds for integer stochastic programs with probabilistic constraints. Discrete Applied Mathematics, 124, 55–65. · Zbl 1173.90488
[5] Dentcheva, D., Lai, B., & Ruszczyński, A. (2004). Dual methods for probabilistic optimization problems. Mathematical Methods of Operations Research, 60, 331–346. · Zbl 1076.90038
[6] Lejeune, M., & Noyan, N. (2010). Mathematical programming generation of p-efficient points (Working paper). · Zbl 1205.90210
[7] Luedtke, J., Ahmed, S., & Nemhauser, G. (2010). An integer programming approach for linear programming with probabilistic constraints. Mathematical Programming, 122, 247–272. · Zbl 1184.90115
[8] Norkin, V. I., & Roenko, N. V. (1991). {\(\alpha\)}-concave functions and measures and their applications. Kibernetika I Sistemnyj Analiz, 189, 77–88 (in Russian); translation in: Cybernet. Systems Anal. 27 (1991) 860–869. · Zbl 0875.90336
[9] Prékopa, A. (1970). On probabilistic constrained programming. In Proceedings of the Princeton symposium on mathematical programming (pp. 113–138). Princeton: Princeton University Press.
[10] Prékopa, A. (1995). Stochastic programming. Dordrecht: Kluwer. · Zbl 0834.90098
[11] Prékopa, A., Vizvári, B., & Badics, T. (1998). Programming under probabilistic constraint with discrete random variable. In L. Grandinetti et al. (Ed.), New trends in mathematical programming (pp. 235–255). Dordrecht: Kluwer. · Zbl 0907.90215
[12] Rinott, Y. (1976). On convexity of measures. Annals of Probability, 4, 1020–1026. · Zbl 0347.60003
[13] Ruszczyński, A. (2002). Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra. Mathematical Programming, 93, 195–215. · Zbl 1065.90058
[14] Ruszczyński, A. (2006). Nonlinear optimization. Princeton: Princeton University Press. · Zbl 1108.90001
[15] Ruszczyński, A., & Shapiro, A. (Eds.) (2003). Stochastic programming. Amsterdam: Elsevier Science. · Zbl 1115.90001
[16] Shapiro, A., Dentcheva, D., & Ruszczyński, A. (2009). MPS/SIAM Series on Optimization: Vol. 9. Lectures on Stochastic Programming: Modeling and Theory. Philadelphia: SIAM. · Zbl 1183.90005
[17] Szántai, T. (1987). Calculation of the multivariate probability distribution function values and their gradient vectors (IIASA Working Paper, WP-87-82).
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.