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.  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.  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, (2012).   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.  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.  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.  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.  doi: 10.1109/TAC.2006.875041.  Google Scholar

[10]

A. Charnes and W. W. Cooper, Chance-constrained programming,, Management Science, 6 (1959), 73.  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.  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.  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.  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.  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.   Google Scholar

[16]

R. Henrion, Structural properties of linear probabilistic constraints,, Optimization, 56 (2007), 425.  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.  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.  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.  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.  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.  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.  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.  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.  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.  doi: 10.1137/050622328.  Google Scholar

[26]

A. Nemirovski and A. Shapiro, Scenario approximations of chance constraints,, in, (2006), 3.  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, (2003), 267.   Google Scholar

[29]

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

[30]

A. Ruszczyński, Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra,, Mathematical Programming, 93 (2002), 195.  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.  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.  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.  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.  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, (2012).   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.  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.  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.  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.  doi: 10.1109/TAC.2006.875041.  Google Scholar

[10]

A. Charnes and W. W. Cooper, Chance-constrained programming,, Management Science, 6 (1959), 73.  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.  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.  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.  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.  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.   Google Scholar

[16]

R. Henrion, Structural properties of linear probabilistic constraints,, Optimization, 56 (2007), 425.  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.  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.  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.  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.  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.  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.  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.  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.  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.  doi: 10.1137/050622328.  Google Scholar

[26]

A. Nemirovski and A. Shapiro, Scenario approximations of chance constraints,, in, (2006), 3.  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, (2003), 267.   Google Scholar

[29]

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

[30]

A. Ruszczyński, Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra,, Mathematical Programming, 93 (2002), 195.  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.  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.  doi: 10.1016/j.ejor.2012.03.006.  Google Scholar

[1]

Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162
[2]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[3]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054
[4]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012
[5]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136
[6]

Kai Zhang, Xiaoqi Yang, Song Wang. Solution method for discrete double obstacle problems based on a power penalty approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021018
[7]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070
[8]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[9]

Editorial Office. Retraction: Xiao-Qian Jiang and Lun-Chuan Zhang, A pricing option approach based on backward stochastic differential equation theory. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 969-969. doi: 10.3934/dcdss.2019065
[10]

Junkee Jeon. Finite horizon portfolio selection problems with stochastic borrowing constraints. Journal of Industrial & Management Optimization, 2021, 17 (2) : 733-763. doi: 10.3934/jimo.2019132
[11]

Knut Hüper, Irina Markina, Fátima Silva Leite. A Lagrangian approach to extremal curves on Stiefel manifolds. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020031
[12]

Felix Finster, Jürg Fröhlich, Marco Oppio, Claudio F. Paganini. Causal fermion systems and the ETH approach to quantum theory. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020451
[13]

Xinpeng Wang, Bingo Wing-Kuen Ling, Wei-Chao Kuang, Zhijing Yang. Orthogonal intrinsic mode functions via optimization approach. Journal of Industrial & Management Optimization, 2021, 17 (1) : 51-66. doi: 10.3934/jimo.2019098
[14]

Constantine M. Dafermos. A variational approach to the Riemann problem for hyperbolic conservation laws. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 185-195. doi: 10.3934/dcds.2009.23.185
[15]

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013
[16]

Martin Heida, Stefan Neukamm, Mario Varga. Stochastic homogenization of $ \Lambda $-convex gradient flows. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 427-453. doi: 10.3934/dcdss.2020328
[17]

Haodong Yu, Jie Sun. Robust stochastic optimization with convex risk measures: A discretized subgradient scheme. Journal of Industrial & Management Optimization, 2021, 17 (1) : 81-99. doi: 10.3934/jimo.2019100
[18]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018
[19]

Touria Karite, Ali Boutoulout. Global and regional constrained controllability for distributed parabolic linear systems: RHUM approach. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020055
[20]

Shuang Liu, Yuan Lou. A functional approach towards eigenvalue problems associated with incompressible flow. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3715-3736. doi: 10.3934/dcds.2020028

 Impact Factor: 

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences