收稿日期: 2015-01-19
修回日期: 2015-04-14
网络出版日期: 2015-09-15
基金资助
Supported by National 973 Plan Project(2011CB706900), 863 Plan Project(2011AA01A102), NSFC(71171189, 11331012, 71271204, and 11101420), the "Strategic Priority Research Program" of Chinese Academy of Sciences (XDA06010302), and the Open Preject of Key Laboratory of Big Data Mining and Knowledge Management, Chinese Academy of Sciences and Huawei Technology Co., Ltd.
A further discussion on the conservatism of robust linear optimization problems
Received date: 2015-01-19
Revised date: 2015-04-14
Online published: 2015-09-15
Supported by
Supported by National 973 Plan Project(2011CB706900), 863 Plan Project(2011AA01A102), NSFC(71171189, 11331012, 71271204, and 11101420), the "Strategic Priority Research Program" of Chinese Academy of Sciences (XDA06010302), and the Open Preject of Key Laboratory of Big Data Mining and Knowledge Management, Chinese Academy of Sciences and Huawei Technology Co., Ltd.
刘鹏飞 , 杨文国 . 对鲁棒线性规划保守性的进一步讨论[J]. 中国科学院大学学报, 2015 , 32(5) : 577 -581 . DOI: 10.7523/j.issn.2095-6134.2015.05.001
The conservatism is an important indicator for measuring a robust approach. In the process of our previous research for the conservatism of robust linear programming problems, we have found that k is a critical parameter to depict the conservatism of robust linear programming problems, where k is the number of nonzero components in optimal solution of the extremely conservative robust linear programming problems. In this paper we give the distribution and expectation of k through analyzing the probability that any basic solutions are the optimal solutions of the extremely conservative robust linear programming problems.
Key words： robust approach; conservatism; linear programming; distribution
[1] Liu P F, Yang W G, Guo T D. A discussion on the conservatism of robust linear optimization problems[J/OL]. Eprints for the optimization community. (2014-10)[2015-01-10]. http://www.optimization-online.org/DB_HTML/2014/10/4598.html.
[2] Soyster A L. Technical note-convex programming with set-inclusive constraints and applications to inexact linearprogramming[J]. Operations Research, 1973, 21(5):1154-1157.
[3] Bertsimas D, Sim M. The price of robustness[J]. Operations Research, 2004, 52(1):35-53.
[4] Ben-Tal A, Nemirovski A. Robust convex optimization[J]. Mathematics of Operations Research, 1998, 23(4):769-805.
[5] Ben-Tal A, Nemirovski A. Robust solutions of uncertain linear programs[J]. Operations Research Letters, 1999, 25(1):1-13.
[6] EI-Ghaoui L, Lebret H. Robust solutions to least-square problems to uncertain data matrices[J]. Sima Journal on Matrix Analysis and Applications, 1997, 18:1035-1064.
[7] El Ghaoui L, Oustry F, Lebret H. Robust solutions to uncertain semidefinite programs[J]. SIAM Journal on Optimization, 1998, 9(1):33-52.
[8] Hillier F S, Lieberman G J. Introduction to operations research[M].9th ed. San Francisco:Mc Graw Hill-Higher Education, 2010:107-109.
[9] Adler I, Karp R M, Shamir R. A simplex variant solving an m×d linear program in O(min(m2,d2)) expected number of pivot steps[J]. Journal of Complexity, 1987, 3(4):372-387.
/
| 〈 |
|
〉 |
