鲁棒线性优化若干模型研究
|
摘要
鲁棒优化(RO)作为数学规划的一个新分支近几年才发展起来,它是解决不确定规划问题的一种强有力工具。由于测量误差或模型本身的缺陷,或者决策阶段缺乏信息等原因,实际中许多优化问题的数据是受到干扰的或者是不确定的,并且概率分布也无法预知。鲁棒优化通过“集合”形式描述数据的不确定性(而不是概率分布),使得约束条件在不确定数据取值于已知集合中所有可能值的情况下都满足,并以此建立最坏情况下最优目标函数的鲁棒对应模型(RC),从而得到问题的鲁棒最优解。已有文献中的各种鲁棒线性优化模型大都是基于约束矩阵为列不确定或行不确定性的情况,本文对线性优化(LP)对偶能否将行不确定的鲁棒LP模型转化为列不确定的鲁棒LP模型,以及系数b为不确定的情况下鲁棒线性优化模型的对偶等问题进行初步的研究。
另一方面,半定规划由于其比较强的表示能力,可以处理实际应用中大量的非线性凸优化问题,在工程以及生物优化中具有广泛的应用,然而由于实际建模中的决策环境是不确定的,需要对所建的模型进行安全性判别,即分析模型中输入数据发生的微小变化对模型最优解所产生的影响。对于一个给定的模型,若判定该模型是鲁棒不可行的,则此模型对数据的变化很敏感,其实际应用价值不大。这时可利用鲁棒优化建模的方法重新建模使其所求解具有鲁棒性。
本文的主要工作如下:
(1)给出了约束条件中右端系数b为区间不确定情况鲁棒线性优化基于不同决策准则的等价模型,并分析了模型的计算复杂性。
(2)研究了鲁棒线性优化模型的对偶和线性优化模型对偶的鲁棒形式的关系,以及仅系数b为不确定下的LP对偶。
(3)建立了判别半定规划鲁棒不可行的准则。
Robust optimization (RO) is a relatively recent technique as a new branch of math programming, and it is a powerful methodology used to solve uncertain program problems. Many real-world optimization problems involve input data that are perturbed or uncertain, and the probability distributions of the uncertain data are unknown or unavailable due to measurement or modeling errors, or the unavailability of the information at the time of the decision. RO describe uncertainty via sets, as opposed to probability distributions. The uncertain parameters are only known to belong to known sets, and one associates with the uncertain problem its robust counterpart (RC) where the constraints are enforced for every possible value of the parameters within their prescribed sets; under such constraints, the worst-case value of the cost function is then minimized to obtain a "robust" solution of the problem. The literatures of most robust linear optimization model are based on the rows or columns uncertain constraint matrix. However, can LP dual transform a rows uncertain robust LP model into a columns uncertain robust LP model? The dual problem of robust linear optimization model in case of only coefficient b is uncertain. This article will conduct a preliminary study.
On the other hand, Semidefinite Programming can handle a large number of non-linear convex optimization problems because of its relatively strong expression ability and can be applied in a wide range of engineering and biological optimization. However, due to decision-making environment is uncertain, we need to discriminate the security of the model, which is Analysis the impaction cured on the optimal solution of the model when input data have small changes. For a given model, if we determine the model is robust infeasibility, then this model is very sensitive to changes in the data of little value in practical applications. In this case, we can make use of robust modeling methods to optimize the model and get a robust solution.
The main work of this paper is as follows:
(1) The equivalence of different models of robust linear optimization is given. Coefficient b is interval uncertain and the equivalence of different models is based different decision-making criteria. Also the computational complexity of the different models is being analysis.
(2) Study the relationship between the dual of robust linear optimization model and robust counterpart of the dual of robust linear optimization mode and the LP dual in case of only coefficient b is uncertain.
(3) A principle which is used to judge the robust infeasibility of semidefinite programming is introduced.
另一方面,半定规划由于其比较强的表示能力,可以处理实际应用中大量的非线性凸优化问题,在工程以及生物优化中具有广泛的应用,然而由于实际建模中的决策环境是不确定的,需要对所建的模型进行安全性判别,即分析模型中输入数据发生的微小变化对模型最优解所产生的影响。对于一个给定的模型,若判定该模型是鲁棒不可行的,则此模型对数据的变化很敏感,其实际应用价值不大。这时可利用鲁棒优化建模的方法重新建模使其所求解具有鲁棒性。
本文的主要工作如下:
(1)给出了约束条件中右端系数b为区间不确定情况鲁棒线性优化基于不同决策准则的等价模型,并分析了模型的计算复杂性。
(2)研究了鲁棒线性优化模型的对偶和线性优化模型对偶的鲁棒形式的关系,以及仅系数b为不确定下的LP对偶。
(3)建立了判别半定规划鲁棒不可行的准则。
Robust optimization (RO) is a relatively recent technique as a new branch of math programming, and it is a powerful methodology used to solve uncertain program problems. Many real-world optimization problems involve input data that are perturbed or uncertain, and the probability distributions of the uncertain data are unknown or unavailable due to measurement or modeling errors, or the unavailability of the information at the time of the decision. RO describe uncertainty via sets, as opposed to probability distributions. The uncertain parameters are only known to belong to known sets, and one associates with the uncertain problem its robust counterpart (RC) where the constraints are enforced for every possible value of the parameters within their prescribed sets; under such constraints, the worst-case value of the cost function is then minimized to obtain a "robust" solution of the problem. The literatures of most robust linear optimization model are based on the rows or columns uncertain constraint matrix. However, can LP dual transform a rows uncertain robust LP model into a columns uncertain robust LP model? The dual problem of robust linear optimization model in case of only coefficient b is uncertain. This article will conduct a preliminary study.
On the other hand, Semidefinite Programming can handle a large number of non-linear convex optimization problems because of its relatively strong expression ability and can be applied in a wide range of engineering and biological optimization. However, due to decision-making environment is uncertain, we need to discriminate the security of the model, which is Analysis the impaction cured on the optimal solution of the model when input data have small changes. For a given model, if we determine the model is robust infeasibility, then this model is very sensitive to changes in the data of little value in practical applications. In this case, we can make use of robust modeling methods to optimize the model and get a robust solution.
The main work of this paper is as follows:
(1) The equivalence of different models of robust linear optimization is given. Coefficient b is interval uncertain and the equivalence of different models is based different decision-making criteria. Also the computational complexity of the different models is being analysis.
(2) Study the relationship between the dual of robust linear optimization model and robust counterpart of the dual of robust linear optimization mode and the LP dual in case of only coefficient b is uncertain.
(3) A principle which is used to judge the robust infeasibility of semidefinite programming is introduced.
引文
1. Sun C R. A comprehensive survey of robust optimization, subjected to The Third Annual Conference on Uncertainty[C], 2005
2. Soyster A L. Convex programming with set inclusive constraints and applications to inexact linear programming[J], Operation Research, 1973, 21: 1154-157
3. John M M, Robert J V, Stavros A Z. Robust optimization of large-scale systems[J], Operations Research, 1995, 43(2): 264-281
4. Ahmed S, Sahinidis N V. Robust process planning under uncertainty[J], Industrial Engineering Chemistry Research, 1998, 37:1883-1892
5. Manuel L. Applying robust optimization to capacity expansion of one location in telecommunications with demand uncertainty [J], Management Science, 1998, 11:101-110
6. Yu C R, Li H L. A robust optimization model for stochastic logistic problems[J], International Journal of Production Economics, 2000, 64:385-39
7. Leung S C H, Yue W, Lai K K.A robust optimization model for a cross-border logistics problem with fleet composition in an uncertain environment[J], Mathematical and Computer Modeling, 2002, 36:1221-1234
8. Ben-Tal A, Nemirovski A. Robust solutions of LP problems contaminated with uncertain data[J], Math Programming, 2000, 88:411-424
9. Ben-Tal A, Nemirovski A. Robust solutions of uncertain linear programs[J], Operation Research Letter, 1999, 25:1-13
10. Ben-Tal A, Nemirovski A. Robust convex optimization[J], Math Oper Res, 1998, 23: 769-805
11. Ghaoui L El, Lebret H. Robust solutions to least-square problems to uncertain data matrices[J], SIAM J Matrix Anal Appl, 1997, 18:1035-1064
12. Ghaoui L EI, Oustry F, Lebret H. Robust solutions to uncertain semi definite programs [J], SIAM Journal on Optimization, 1998, 9(1):33-52
13. Ben-Tal A, et al. Adjustable Robust solutions of uncertain linear programs[J], Mathematical Programming, 2004, 99(2):351-376
14. Ben-Tal A, Boyd S. Extending scope of robust optimization: comprehensive robust counterparts of uncertain problems[J], Mathematical Programming, 2006,107(1):63-89
15. Ben-Tal A, Nemirovski A. Stable truss topology design via semidefinite programming[J], SIAM Journal on Optimization, 1997, 7(4):991-1016
16. Ben-Tal A, Nemirovski A. Robust optimization methodology and applications[J], Math Program, Ser.B, 2002,92:453-480
17. Ben-Tal A, Golany B, Nemirovski A. Supplier-retailer flexible commitments contracts: a robust optimization approach-Manufacturing service operations management[J], Math. Program, Ser.B, 2005, 7(3):248-273
18. Bertsimas D, Sim M. The price of robustness[J], Operations Research, 2004, 52(1):35-53
19. Bertsimas D, Sim M. Robust discrete optimization and network flows[J], Math Program Ser.B, 2003, 98:49-71
20. Bertsimas D, Sim M. Robust discrete optimization and downside risk measures[R], Working Paper, National University of Singapore, 2004
21. Bertsimas D, Sim M. robust conic optimization[R], Working Paper, Mit, 2004
22. Mustafa C P. A note on robust 0-1 optimization with uncertain cost coefficients[Z], Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2004, 4:309-316
23. Chen X, Sim M, Sun P. A robust optimization perspective of stochastic programming[J], Operations Research, 2007, 6:1058-1071
24. Bertsimas D. A robust optimization approach to inventory theory[J], Math Program Ser.B, 2003, 95:49-69
25. Bertsimas D. A robust optimization approach to supply chain management, integer programming and combinatorial optimization[J], Proceedings lecture notes in Computer Science 3046, 2004, 86-100
26. Robert D C, Harvey J G, Henry Lin. Robust optimization of contaminant water systems[J], Mathematical Programming, 2006,107(1):337-356
27. Elodie A, Georgia P. A robust optimization approach to dynamic precing and inventory control with no backorders[J], Mathematical Programming, 2005, 8:1-33
28. Alan L E, Juan C M, Martin S. Robust optimization for empty repositioning problems[R], Working Paper, September, 2005
29. Lu J G, Ban X G, Qiu Z J. A robust optimization model for route guidance based on ATIS[R], Working Paper, November, 2004
30. Ben-Tal A, Nemirovski A, Roos C. Robust solutions of uncertain quadratic and conic-quadratic problems[J], SIAM J.OPTIM.Vol.13, No.2:535-560
31. Vandenberghe L, Boyd S. Semidefinite programming[J], SIAM Rev., 1996, 38: 49-95
32. Ben-Tal A, Nemirovski A. Robust convex optimization[J], Math Oper Res, 1998, 23: 769-805
33. Ben-Tal A, Ghaoul L Ei, Nemirovski A. Semidefinite programming and applications[M], Kluwer Academic Publishers, 2000
2. Soyster A L. Convex programming with set inclusive constraints and applications to inexact linear programming[J], Operation Research, 1973, 21: 1154-157
3. John M M, Robert J V, Stavros A Z. Robust optimization of large-scale systems[J], Operations Research, 1995, 43(2): 264-281
4. Ahmed S, Sahinidis N V. Robust process planning under uncertainty[J], Industrial Engineering Chemistry Research, 1998, 37:1883-1892
5. Manuel L. Applying robust optimization to capacity expansion of one location in telecommunications with demand uncertainty [J], Management Science, 1998, 11:101-110
6. Yu C R, Li H L. A robust optimization model for stochastic logistic problems[J], International Journal of Production Economics, 2000, 64:385-39
7. Leung S C H, Yue W, Lai K K.A robust optimization model for a cross-border logistics problem with fleet composition in an uncertain environment[J], Mathematical and Computer Modeling, 2002, 36:1221-1234
8. Ben-Tal A, Nemirovski A. Robust solutions of LP problems contaminated with uncertain data[J], Math Programming, 2000, 88:411-424
9. Ben-Tal A, Nemirovski A. Robust solutions of uncertain linear programs[J], Operation Research Letter, 1999, 25:1-13
10. Ben-Tal A, Nemirovski A. Robust convex optimization[J], Math Oper Res, 1998, 23: 769-805
11. Ghaoui L El, Lebret H. Robust solutions to least-square problems to uncertain data matrices[J], SIAM J Matrix Anal Appl, 1997, 18:1035-1064
12. Ghaoui L EI, Oustry F, Lebret H. Robust solutions to uncertain semi definite programs [J], SIAM Journal on Optimization, 1998, 9(1):33-52
13. Ben-Tal A, et al. Adjustable Robust solutions of uncertain linear programs[J], Mathematical Programming, 2004, 99(2):351-376
14. Ben-Tal A, Boyd S. Extending scope of robust optimization: comprehensive robust counterparts of uncertain problems[J], Mathematical Programming, 2006,107(1):63-89
15. Ben-Tal A, Nemirovski A. Stable truss topology design via semidefinite programming[J], SIAM Journal on Optimization, 1997, 7(4):991-1016
16. Ben-Tal A, Nemirovski A. Robust optimization methodology and applications[J], Math Program, Ser.B, 2002,92:453-480
17. Ben-Tal A, Golany B, Nemirovski A. Supplier-retailer flexible commitments contracts: a robust optimization approach-Manufacturing service operations management[J], Math. Program, Ser.B, 2005, 7(3):248-273
18. Bertsimas D, Sim M. The price of robustness[J], Operations Research, 2004, 52(1):35-53
19. Bertsimas D, Sim M. Robust discrete optimization and network flows[J], Math Program Ser.B, 2003, 98:49-71
20. Bertsimas D, Sim M. Robust discrete optimization and downside risk measures[R], Working Paper, National University of Singapore, 2004
21. Bertsimas D, Sim M. robust conic optimization[R], Working Paper, Mit, 2004
22. Mustafa C P. A note on robust 0-1 optimization with uncertain cost coefficients[Z], Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 2004, 4:309-316
23. Chen X, Sim M, Sun P. A robust optimization perspective of stochastic programming[J], Operations Research, 2007, 6:1058-1071
24. Bertsimas D. A robust optimization approach to inventory theory[J], Math Program Ser.B, 2003, 95:49-69
25. Bertsimas D. A robust optimization approach to supply chain management, integer programming and combinatorial optimization[J], Proceedings lecture notes in Computer Science 3046, 2004, 86-100
26. Robert D C, Harvey J G, Henry Lin. Robust optimization of contaminant water systems[J], Mathematical Programming, 2006,107(1):337-356
27. Elodie A, Georgia P. A robust optimization approach to dynamic precing and inventory control with no backorders[J], Mathematical Programming, 2005, 8:1-33
28. Alan L E, Juan C M, Martin S. Robust optimization for empty repositioning problems[R], Working Paper, September, 2005
29. Lu J G, Ban X G, Qiu Z J. A robust optimization model for route guidance based on ATIS[R], Working Paper, November, 2004
30. Ben-Tal A, Nemirovski A, Roos C. Robust solutions of uncertain quadratic and conic-quadratic problems[J], SIAM J.OPTIM.Vol.13, No.2:535-560
31. Vandenberghe L, Boyd S. Semidefinite programming[J], SIAM Rev., 1996, 38: 49-95
32. Ben-Tal A, Nemirovski A. Robust convex optimization[J], Math Oper Res, 1998, 23: 769-805
33. Ben-Tal A, Ghaoul L Ei, Nemirovski A. Semidefinite programming and applications[M], Kluwer Academic Publishers, 2000