概率约束最优化问题

运筹学学报 ›› 2012, Vol. 16 ›› Issue (3): 65-74.

概率约束最优化问题

孙小玲¹, 白晓迪¹, 郑小金²

1. 复旦大学管理学院
2. 同济大学经济与管理学院

收稿日期:2012-06-18 修回日期:2012-06-07 出版日期:2012-09-15 发布日期:2012-09-18
通讯作者: 孙小玲 E-mail:xls@fudan.edu.cn

A survey on probabilistically constrained optimization problems

SUN Xiaoling¹, BAI Xiaodi¹, ZHENG Xiaojin²

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

Received:2012-06-18 Revised:2012-06-07 Online:2012-09-15 Published:2012-09-18
Contact: SUN Xiaoling E-mail:xls@fudan.edu.cn

摘要/Abstract

摘要： 概率约束最优化问题是随机规划的一类重要问题,在金融、管理和工程计划等领域有广泛的应用. 概率约束优化问题近年来受到了广泛的关注和重视，在应用建模、理论和方法等方面取得了不少重要的进展. 这里主要概述和总结处理概率约束的主要方法和思想，包括凸内逼近方法、情景逼近方法、DC方法和整数规划方法等，并对概率约束最优化的研究前景进行讨论.

关键词: 随机规划, 概率约束最优化, 逼近方法, 整数规划方法

Abstract: We give a brief review on the probabilistically constrained optimization problem which is an important class of stochastic programming with wide applications in finance, management and engineering planning. We introduce the modeling of probabilistic constraints and summarize some important solution methods including convex approximation, DC approach, scenario approach and integer programming approach. We also discuss some future research perspectives of the probabilistically constrained optimization problem.

Key words: stochastic programming, probabilistic constraints, approximation methods, integer programming approach

中图分类号:

90C15
90C26

孙小玲, 白晓迪, 郑小金. 概率约束最优化问题[J]. 运筹学学报, 2012, 16(3): 65-74.

SUN Xiaoling, BAI Xiaodi, ZHENG Xiaojin. A survey on probabilistically constrained optimization problems[J]. Operations Research Transactions, 2012, 16(3): 65-74.

参考文献

Alexander G J, Baptista A M. A comparison of VaR and CVaR constraints on portfolio selection with the mean-variance model [J]. Management Science, 2004, 50: 1261-1273.
Alexander G J, Baptista A M. A comparison of VaR and CVaR constraints on portfolio selection with the mean-variance model [J]. Management Science, 2004, 50: 1261-1273.
Alexander G J, Baptista A M, Yan S. Mean-variance portfolio selection with `at-risk' constraints and discrete distributions [J]. Journal of Banking & Finance, 2007, 31: 3761-3781.
Alexander G J, Baptista A M, Yan S. Mean-variance portfolio selection with `at-risk' constraints and discrete distributions [J]. Journal of Banking & Finance, 2007, 31: 3761-3781.
Benati S, Rizzi R. A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem [J]. European Journal of Operational Research, 2007, 176: 423-434.
Beraldi P, Ruszczynski A. The probabilistic set-covering problem [J]. Operations Research, 2002, 50: 956-967.
Bonami P, Lejeune M A. An exact solution approach for portfolio optimization problems under stochastic and integer constraints [J]. Operations Research, 2009, 57: 650-670.
Boyd S P, Vandenberghe L. Convex Optimization [M]. Cambridge: Cambridge University Press, 2004.
Calafiore G C, Campi M C. The scenario approach to robust control design [J]. IEEE Transactions on Automatic Control, 2006, 51: 742-753.
Charnes A, Cooper W W, Symonds G H. Cost horizons and certainty equivalents: an approach to stochastic programming of heating oil [J]. Management Science, 1958, 4: 235-263.
Chen W, Sim M, Sun J, Teo C P. From CVaR to uncertainty set: Implications in joint chance-constrained optimization [J]. Operations Research, 2010, 58: 470-485.
Cheon M S, Ahmed S, Al-Khayyal F. A branch-reduce-cut algorithm for the global optimization of probabilistically constrained linear programs [J]. Mathematical Programming, 2006, 108: 617-634.
Dentcheva D, Martinez G. Augmented Lagrangian method for probabilistic optimization [J]. Annals of Operations Research, 2011. DOI: 10.1007/s10479-011-0884-5.
Dentcheva D, Prekopa A, Ruszczynski A. Concavity and efficient points of discrete distributions in probabilistic programming [J]. Mathematical Programming, 2000, 89: 55-77.
Gaivoronski A A, Pflug G. Value at risk in portfolio optimization: Properties and computational approach [J]. Journal of Risk, 2005, 7: 1-31.
Henrion R. Structural properties of linear probabilistic constraints [J]. Optimization, 2007, 56: 425-440.

Henrion R, Strugarek C. Convexity of chance constraints with independent random variables [J]. Computational Optimization and Applications, 2008, 41: 263-276.
Hong L J, Yang Y, Zhang L. Sequential convex approximations to joint chance constrained programs: A monte carlo approach [J]. Operations Research, 2011, 59: 617-630.
Kucukyavuz S. On mixing sets arising in chance-constrained programming [J]. Mathematical Programming, 2012, 132: 31-56.
Lagoa C M, Li X, Sznaier M. Probabilistically constrained linear programs and risk-adjusted controller design [J]. SIAM Journal on Optimization, 2005, 15: 938-951.
Lejeune M, Noyan N. Mathematical programming approaches for generating p-efficient points [J]. European Journal of Operational Research, 2010, 207: 590-600.
Lejeune M, Noyan N. Mathematical programming approaches for generating p-efficient points [J]. European Journal of Operational Research, 2010, 207: 590-600.
Lejeune M A, Ruszczynski A. An efficient trajectory method for probabilistic inventory production-distribution problems [J]. Operations Research, 2007, 55: 378-394.

Luedtke J, Ahmed S. A sample approximation approach for optimization with probabilistic constraints [J]. SIAM Journal on Optimization, 2008, 19: 674-699.
Luedtke J, Ahmed S, Nemhauser G L. An integer programming approach for linear programs with probabilistic constraints [J]. Mathematical Programming, 2010, 122: 247-272.
Nemirovski A, Shapiro A. Convex approximations of chance constrained programs [J]. SIAM Journal on Optimization, 2006, 17: 969-996.
Nemirovski A, Shapiro A. Scenario approximations of chance constraints [M]//Calafiore G, Dabbene F, editors. Probabilistic and Randomized Methods for Design Under Uncertainty, Berlin: Springer, 2006, 3-47.
Nocedal J, Wright S J. Numerical Optimization [M]. Berlin: Springer, 1999.
Prekopa A. Probabilistic programming [M]//Ruszczynski A, Shapiro A, editors. Stochastic Programming, Handbooks in Operations Research and Management Science. Amsterdam: Elsevier Science, 2003: 267-351.
Rockafellar R T, Uryasev S. Optimization of conditional value-at-risk [J]. Journal of Risk, 2000, 2: 21-42.
Ruszczynski A. Probabilistic programming with discrete distributions and precedence constrained knapsack polyhedra [J]. Mathematical Programming, 2002, 93: 195-215.
Saxena A, Goyal V, Lejeune M A. MIP reformulations of the probabilistic set covering problem [J]. Mathematical Programming, 2010, 121: 1-31.
Zheng X J, Sun X L, Li D, Cui X T. Lagrangian decomposition and mixed-integer quadratic programming reformulations for probabilistically constrained quadratic programs [J]. European Journal of Operational Research, 2012, 221: 38-48.

[1]	张艳丽, 马新顺. 一类带有MaxEMin评判的补偿型随机规划算法[J]. 运筹学学报, 2016, 20(4): 52-60.
[2]	霍永亮. 极大极小随机规划逼近问题最优解集和最优值的稳定性[J]. 运筹学学报, 2016, 20(1): 75-83.