American Institute of Mathematical Sciences

Advanced
2012, 2(4): 767-778. doi: 10.3934/naco.2012.2.767

A survey on probabilistically constrained optimization problems

Xiaodi Bai 1, , Xiaojin Zheng 2, and  Xiaoling Sun 1,

1. 

School of Management, Fudan University, Shanghai 200433, China
2. 

School of Economics and Management, Tongji University, Shanghai 200092, China

Received  November 2011 Revised  October 2012 Published  November 2012

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: DC approach, integer programming approach., probabilistic constraints, Stochastic programming, convex approximation method.
Mathematics Subject Classification: Primary: 91C15; Secondary: 90C2.
Citation: Xiaodi Bai, Xiaojin Zheng, Xiaoling Sun. A survey on probabilistically constrained optimization problems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 767-778. doi: 10.3934/naco.2012.2.767
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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[4]

A. Ben-Tal, L. El Ghaoui and A. S. Nemirovski, "Robust Optimization," Princeton University Press, 2009.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

S. P. Boyd and L. Vandenberghe, "Convex Optimization," Cambridge University Press, 2004.  Google Scholar

[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.  Google Scholar

[10]

A. Charnes and W. W. Cooper, Chance-constrained programming, Management Science, 6 (1959), 73-79. doi: 10.1287/mnsc.6.1.73.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

A. A. Gaivoronski and G. Pflug, Value at risk in portfolio optimization: Properties and computational approach, Journal of Risk, 7 (2005), 1-31. Google Scholar

[16]

R. Henrion, Structural properties of linear probabilistic constraints, Optimization, 56 (2007), 425-440. doi: 10.1080/02331930701421046.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[25]

A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs, SIAM Journal on Optimization, 17 (2006), 969-996. doi: 10.1137/050622328.  Google Scholar

[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.  Google Scholar

[27]

J. Nocedal and S. J. Wright, "Numerical Optimization," Springer, 1999. doi: 10.1007/b98874.  Google Scholar

[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.  Google Scholar

[29]

R. T. Rockafellar and S. Uryasev, Optimization of conditional value-at-risk, Journal of Risk, 2 (2000), 21-42. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[4]

A. Ben-Tal, L. El Ghaoui and A. S. Nemirovski, "Robust Optimization," Princeton University Press, 2009.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[8]

S. P. Boyd and L. Vandenberghe, "Convex Optimization," Cambridge University Press, 2004.  Google Scholar

[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.  Google Scholar

[10]

A. Charnes and W. W. Cooper, Chance-constrained programming, Management Science, 6 (1959), 73-79. doi: 10.1287/mnsc.6.1.73.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

A. A. Gaivoronski and G. Pflug, Value at risk in portfolio optimization: Properties and computational approach, Journal of Risk, 7 (2005), 1-31. Google Scholar

[16]

R. Henrion, Structural properties of linear probabilistic constraints, Optimization, 56 (2007), 425-440. doi: 10.1080/02331930701421046.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[25]

A. Nemirovski and A. Shapiro, Convex approximations of chance constrained programs, SIAM Journal on Optimization, 17 (2006), 969-996. doi: 10.1137/050622328.  Google Scholar

[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.  Google Scholar

[27]

J. Nocedal and S. J. Wright, "Numerical Optimization," Springer, 1999. doi: 10.1007/b98874.  Google Scholar

[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.  Google Scholar

[29]

R. T. Rockafellar and S. Uryasev, Optimization of conditional value-at-risk, Journal of Risk, 2 (2000), 21-42. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

Jian Gu, Xiantao Xiao, Liwei Zhang. A subgradient-based convex approximations method for DC programming and its applications. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1349-1366. doi: 10.3934/jimo.2016.12.1349
[2]

Changzhi Wu, Chaojie Li, Qiang Long. A DC programming approach for sensor network localization with uncertainties in anchor positions. Journal of Industrial & Management Optimization, 2014, 10 (3) : 817-826. doi: 10.3934/jimo.2014.10.817
[3]

Le Thi Hoai An, Tran Duc Quynh, Pham Dinh Tao. A DC programming approach for a class of bilevel programming problems and its application in Portfolio Selection. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 167-185. doi: 10.3934/naco.2012.2.167
[4]

Harald Held, Gabriela Martinez, Philipp Emanuel Stelzig. Stochastic programming approach for energy management in electric microgrids. Numerical Algebra, Control & Optimization, 2014, 4 (3) : 241-267. doi: 10.3934/naco.2014.4.241
[5]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353
[6]

Xiantao Xiao, Jian Gu, Liwei Zhang, Shaowu Zhang. A sequential convex program method to DC program with joint chance constraints. Journal of Industrial & Management Optimization, 2012, 8 (3) : 733-747. doi: 10.3934/jimo.2012.8.733
[7]

Ailing Zhang, Shunsuke Hayashi. Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 83-98. doi: 10.3934/naco.2011.1.83
[8]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557
[9]

Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102
[10]

Ye Tian, Shucherng Fang, Zhibin Deng, Qingwei Jin. Cardinality constrained portfolio selection problem: A completely positive programming approach. Journal of Industrial & Management Optimization, 2016, 12 (3) : 1041-1056. doi: 10.3934/jimo.2016.12.1041
[11]

Shu-Cherng Fang, David Y. Gao, Ruey-Lin Sheu, Soon-Yi Wu. Canonical dual approach to solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125
[12]

Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058
[13]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723
[14]

Rhoda P. Agdeppa, Nobuo Yamashita, Masao Fukushima. An implicit programming approach for the road pricing problem with nonadditive route costs. Journal of Industrial & Management Optimization, 2008, 4 (1) : 183-197. doi: 10.3934/jimo.2008.4.183
[15]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171
[16]

Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965
[17]

Bao Qing Hu, Song Wang. A novel approach in uncertain programming part II: a class of constrained nonlinear programming problems with interval objective functions. Journal of Industrial & Management Optimization, 2006, 2 (4) : 373-385. doi: 10.3934/jimo.2006.2.373
[18]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363
[19]

Zhi-Bin Deng, Ye Tian, Cheng Lu, Wen-Xun Xing. Globally solving quadratic programs with convex objective and complementarity constraints via completely positive programming. Journal of Industrial & Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064
[20]

Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247

 Impact Factor: 

Tools

Metrics

  • PDF downloads (105)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences