A survey on probabilistically constrained optimization problems

Xiaodi Bai; Xiaojin Zheng; Xiaoling Sun

doi:10.3934/naco.2012.2.767

Article Contents

2012, Volume 2, Issue 4: 767-778. Doi: 10.3934/naco.2012.2.767

This issue Previous Article Simulation of Lévy-Driven models and its application in finance Next Article A note on semicontinuity to a parametric generalized Ky Fan inequality

A survey on probabilistically constrained optimization problems

1.
School of Management, Fudan University, Shanghai 200433
2.
School of Economics and Management, Tongji University, Shanghai 200092

Received: November 2011

Revised: October 2012

Published: November 2012

Abstract / Introduction Related Papers Cited by

Abstract

Probabilistically constrained optimization problems are an important class of stochastic programming problems with wide applications in finance, management and engineering planning. In this paper, we summarize some important solution methods including convex approximation, DC approach, scenario approach and integer programming approach. We also discuss some future research perspectives on the probabilistically constrained optimization problems.

Keywords:

Mathematics Subject Classification: Primary: 91C15; Secondary: 90C26.

Citation:

Related Papers

Cited by

References

[1]	G. J. Alexander and A. M. Baptista, A comparison of VaR and CVaR constraints on portfolio selection with the mean-variance model, Management Science, 50 (2004), 1261-1273.doi: 10.1287/mnsc.1040.0201.
[2]	G. J. Alexander, A. M. Baptista and S. Yan, Mean-variance portfolio selection with 'at-risk' constraints and discrete distributions, Journal of Banking & Finance, 31 (2007), 3761-3781.doi: 10.1016/j.jbankfin.2007.01.019.
[3]	X. D. Bai, J. Sun, X. J. Zheng and X. L. Sun, A penalty decomposition method for probabilistically constrained convex programs, Technical report, School of Management, Fudan University, P. R. China, 2012. Available from: http://www.optimization-online.org/DB_HTML/2012/04/3448.html.
[4]	A. Ben-Tal, L. El Ghaoui and A. S. Nemirovski, "Robust Optimization," Princeton University Press, 2009.
[5]	S. Benati and R. Rizzi, A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem, European Journal of Operational Research, 176 (2007), 423-434.doi: 10.1016/j.ejor.2005.07.020.
[6]	P. Beraldi and A. Ruszczyński, The probabilistic set-covering problem, Operations Research, 50 (2002), 956-967.doi: 10.1287/opre.50.6.956.345.
[7]	P. Bonami and M. A. Lejeune, An exact solution approach for portfolio optimization problems under stochastic and integer constraints, Operations Research, 57 (2009), 650-670.doi: 10.1287/opre.1080.0599.
[8]	S. P. Boyd and L. Vandenberghe, "Convex Optimization," Cambridge University Press, 2004.
[9]	G. C. Calafiore and M. C. Campi, The scenario approach to robust control design, IEEE Transactions on Automatic Control, 51 (2006), 742-753.doi: 10.1109/TAC.2006.875041.
[10]	A. Charnes and W. W. Cooper, Chance-constrained programming, Management Science, 6 (1959), 73-79.doi: 10.1287/mnsc.6.1.73.
[11]	W. Chen, M. Sim, J. Sun and C. P. Teo, From CVaR to uncertainty set: Implications in joint chance-constrained optimization, Operations Research, 58 (2010), 470-485.doi: [10.1287/opre.1090.0712.
[12]	M. S. Cheon, S. Ahmed and F. Al-Khayyal, A branch-reduce-cut algorithm for the global optimization of probabilistically constrained linear programs, Mathematical Programming, 108 (2006), 617-634.doi: 10.1007/s10107-006-0725-5.
[13]	D. Dentcheva and G. Martinez, Augmented Lagrangian method for probabilistic optimization, Annals of Operations Research, 200 (2012), 109-130.doi: 10.1007/s10479-011-0884-5.
[14]	D. Dentcheva, A. Prékopa and A. Ruszczynski, Concavity and efficient points of discrete distributions in probabilistic programming, Mathematical Programming, 89 (2000), 55-77.doi: 10.1007/PL00011393.
[15]	A. A. Gaivoronski and G. Pflug, Value at risk in portfolio optimization: Properties and computational approach, Journal of Risk, 7 (2005), 1-31.
[16]	R. Henrion, Structural properties of linear probabilistic constraints, Optimization, 56 (2007), 425-440.doi: 10.1080/02331930701421046.
[17]	R. Henrion and C. Strugarek, Convexity of chance constraints with independent random variables, Computational Optimization and Applications, 41 (2008), 263-276.doi: 10.1007/s10589-007-9105-1.
[18]	L. J. Hong, Y. Yang, and L. Zhang, Sequential convex approximations to joint chance constrained programs: A monte carlo approach, Operations Research, 59 (2011), 617-630.doi: 10.1287/opre.1100.0910.
[19]	S. Küçükyavuz, On mixing sets arising in chance-constrained programming, Mathematical Programming, 132 (2012), 31-56.doi: 10.1007/s10107-010-0385-3.
[20]	C. M. Lagoa, X. Li, and M. Sznaier, Probabilistically constrained linear programs and risk-adjusted controller design, SIAM Journal on Optimization, 15 (2005), 938-951.doi: 10.1137/S1052623403430099.
[21]	M. Lejeune and N. Noyan, Mathematical programming approaches for generating p-efficient points, European Journal of Operational Research, 207 (2010), 590-600.doi: 10.1016/j.ejor.2010.05.025.
[22]	M. A. Lejeune and A. Ruszczynski, An efficient trajectory method for probabilistic inventory production-distribution problems, Operations Research, 55 (2007), 378-394.doi: 10.1287/opre.1060.0356.
[23]	J. Luedtke and S. Ahmed, A sample approximation approach for optimization with probabilistic constraints, SIAM Journal on Optimization, 19 (2008), 674-699.doi: 10.1137/070702928.
[24]	J. Luedtke, S. Ahmed and G. L. Nemhauser, An integer programming approach for linear programs with probabilistic constraints, Mathematical Programming, 122 (2010), 247-272.doi: 10.1007/s10107-008-0247-4.
[25]	A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs, SIAM Journal on Optimization, 17 (2006), 969-996.doi: 10.1137/050622328.
[26]	A. Nemirovski and A. Shapiro, Scenario approximations of chance constraints, in "Probabilistic and Randomized Methods for Design Under Uncertainty" (eds. G. Calafiore and F. Dabbene), Springer, (2006), 3-47.doi: 10.1007/1-84628-095-8_1.
[27]	J. Nocedal and S. J. Wright, "Numerical Optimization," Springer, 1999.doi: 10.1007/b98874.
[28]	A. Prékopa, Probabilistic programming, in "Stochastic Programming, " Handbooks in Operations Research and Management Science (eds. A. Ruszczyński and A. Shapiro), Elsevier, (2003), 267-351.
[29]	R. T. Rockafellar and S. Uryasev, Optimization of conditional value-at-risk, Journal of Risk, 2 (2000), 21-42.
[30]	A. Ruszczyński, Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra, Mathematical Programming, 93 (2002), 195-215.doi: 10.1007/s10107-002-0337-7.
[31]	A. Saxena, V. Goyal and M. A. Lejeune, MIP reformulations of the probabilistic set covering problem, Mathematical Programming, 121 (2010), 1-31.doi: 10.1007/s10107-008-0224-y.
[32]	X. J. Zheng, X. L. Sun, D. Li and X. T. Cui, Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs, European Journal of Operational Research, 221 (2012), 38-48.doi: 10.1016/j.ejor.2012.03.006.