-
Previous Article
$ E $-eigenvalue localization sets for tensors
- JIMO Home
- This Issue
-
Next Article
Cost-sharing strategy for carbon emission reduction and sales effort: A nash game with government subsidy
Robust sensitivity analysis for linear programming with ellipsoidal perturbation
Department of Mathematical Sciences, Tsinghua University, Beijing 100086, China |
Sensitivity analysis is applied to the robust linear programming problem in this paper. The coefficients of the linear program are assumed to be perturbed in three perturbation manners within ellipsoidal sets. Our robust sensitivity analysis is to calculate the maximal radii of the perturbation sets to keep some properties of the robust feasible set. Mathematical models are formulated for the robust sensitivity analysis problems and all models are either reformulated into linear programs or convex quadratic programs except for the bi-convex programs where more than one row of the constraint matrix is perturbed. For the bi-convex programs, we develop a binary search algorithm.
References:
[1] |
A. Ben-Tal, D. D. Hertog, A. D. Waegenaere, B. Melenberg and G. Rennen, Robust solutions of optimization problems affected by uncertain probabilities, Management Science, 59 (2013), Pages iv–527.
doi: 10.1287/mnsc.1120.1641. |
[2] |
A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms and Engineering Applications, Society for Industrial and Applied Mathematics, 2001.
doi: 10.1137/1.9780898718829. |
[3] |
D. Bertsimas and D. B. Brown,
Constructing uncertainty sets for robust linear optimization, Operations Research, 57 (2009), 1483-1495.
doi: 10.1287/opre.1080.0646. |
[4] |
D. Bertsimas, V. Gupta and N. Kallus,
Data-driven robust optimization, Mathematical Programming, 167 (2018), 235-292.
doi: 10.1007/s10107-017-1125-8. |
[5] |
D. Bertsimas and M. Sim,
The price of robustness, Operations Research, 52 (2004), 35-53.
doi: 10.1287/opre.1030.0065. |
[6] |
F. Chandra, D. F. Gayme, L. Chen and J. C. Doyle,
Robustness, optimization, and architectures, European Journal of Control, 17 (2011), 472-482.
doi: 10.3166/ejc.17.472-482. |
[7] |
G. E. Dullerud and F. G. Paganini, A Course in Robust Control Theory–-A Convex Approach, Springer-Verlag, New York, 2000. |
[8] |
M. Frank and P. Wolfe,
An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3 (1956), 95-110.
doi: 10.1002/nav.3800030109. |
[9] |
S. I. Gass, Linear Programming: Methods and Applications, Corrected reprint of the 1995 fifth edition. Dover Publications, Inc., Mineola, NY, 2003. |
[10] |
J. Gorski, F. Pfeuffer and K. Klamroth,
Biconvex sets and optimization with biconvex functions: A survey and extensions, Mathematical Methods of Operations Research, 66 (2007), 373-407.
doi: 10.1007/s00186-007-0161-1. |
[11] |
C.-L. Hwang and A. S. Masud, Multiple Objective Decision Making–-Methods and Applications: A State-of-the-Art Survey, Springer-Verlag, Berlin, 1979. |
[12] |
A. Marandi, A. Ben-Tal, D. D. Hertog and B. Melenberg, Extending the scope of robust quadratic optimization, Available on Optimization Online, 2017. |
[13] |
S. Schaible,
Parameter-free convex equivalent and dual programs of fractional programming problems, Zeitschrift für Operations Research, 18 (1974), 187-196.
doi: 10.1007/BF02026600. |
[14] |
A. L. Soyster,
Convex programming with set-inclusive constraints and applications to inexact linear programming, Operations Research, 22 (1974), 892-898.
doi: 10.1287/opre.22.4.892. |
[15] |
G. Xu and S. Burer,
Robust sensitivity analysis of the optimal value of linear programming, Optimization Methods and Software, 32 (2017), 1187-1205.
doi: 10.1080/10556788.2016.1256400. |
[16] |
K. Zhou, J. C. Doyle and K. Glover, Robust and Optimal Control, Prentice Hall Englewood Cliffs, NJ, 1996. |
show all references
References:
[1] |
A. Ben-Tal, D. D. Hertog, A. D. Waegenaere, B. Melenberg and G. Rennen, Robust solutions of optimization problems affected by uncertain probabilities, Management Science, 59 (2013), Pages iv–527.
doi: 10.1287/mnsc.1120.1641. |
[2] |
A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms and Engineering Applications, Society for Industrial and Applied Mathematics, 2001.
doi: 10.1137/1.9780898718829. |
[3] |
D. Bertsimas and D. B. Brown,
Constructing uncertainty sets for robust linear optimization, Operations Research, 57 (2009), 1483-1495.
doi: 10.1287/opre.1080.0646. |
[4] |
D. Bertsimas, V. Gupta and N. Kallus,
Data-driven robust optimization, Mathematical Programming, 167 (2018), 235-292.
doi: 10.1007/s10107-017-1125-8. |
[5] |
D. Bertsimas and M. Sim,
The price of robustness, Operations Research, 52 (2004), 35-53.
doi: 10.1287/opre.1030.0065. |
[6] |
F. Chandra, D. F. Gayme, L. Chen and J. C. Doyle,
Robustness, optimization, and architectures, European Journal of Control, 17 (2011), 472-482.
doi: 10.3166/ejc.17.472-482. |
[7] |
G. E. Dullerud and F. G. Paganini, A Course in Robust Control Theory–-A Convex Approach, Springer-Verlag, New York, 2000. |
[8] |
M. Frank and P. Wolfe,
An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3 (1956), 95-110.
doi: 10.1002/nav.3800030109. |
[9] |
S. I. Gass, Linear Programming: Methods and Applications, Corrected reprint of the 1995 fifth edition. Dover Publications, Inc., Mineola, NY, 2003. |
[10] |
J. Gorski, F. Pfeuffer and K. Klamroth,
Biconvex sets and optimization with biconvex functions: A survey and extensions, Mathematical Methods of Operations Research, 66 (2007), 373-407.
doi: 10.1007/s00186-007-0161-1. |
[11] |
C.-L. Hwang and A. S. Masud, Multiple Objective Decision Making–-Methods and Applications: A State-of-the-Art Survey, Springer-Verlag, Berlin, 1979. |
[12] |
A. Marandi, A. Ben-Tal, D. D. Hertog and B. Melenberg, Extending the scope of robust quadratic optimization, Available on Optimization Online, 2017. |
[13] |
S. Schaible,
Parameter-free convex equivalent and dual programs of fractional programming problems, Zeitschrift für Operations Research, 18 (1974), 187-196.
doi: 10.1007/BF02026600. |
[14] |
A. L. Soyster,
Convex programming with set-inclusive constraints and applications to inexact linear programming, Operations Research, 22 (1974), 892-898.
doi: 10.1287/opre.22.4.892. |
[15] |
G. Xu and S. Burer,
Robust sensitivity analysis of the optimal value of linear programming, Optimization Methods and Software, 32 (2017), 1187-1205.
doi: 10.1080/10556788.2016.1256400. |
[16] |
K. Zhou, J. C. Doyle and K. Glover, Robust and Optimal Control, Prentice Hall Englewood Cliffs, NJ, 1996. |
Instance (m1, n2, pert3, scale4) | Lower Bound | Maximum Radius | Improvement Ratio5 | CPU Time | ||||
Ave | Std | Ave | Std | Ave | Std | Ave | Std | |
(20, 20, 0.25, 0.5) | 0.4151 | 0.1551 | 1.1650 | 0.8647 | 2.3001 | 3.0673 | 15.8480 | 1.1491 |
(20, 20, 0.25, 1) | td> 0.2283 | 0.0969 | 0.7672 | 0.3066 | 2.6969 | 1.3452 | 15.6160 | 0.9467 |
(20, 20, 0.5, 0.5) | 0.3056 | 0.1443 | 1.0726 | 0.7539 | 2.8557 | 3.0440 | 17.0120 | 1.2904 |
(20, 20, 0.5, 1) | 0.1385 | 0.0818 | 0.4476 | 0.2327 | 2.6981 | 2.4415 | 18.3810 | 1.8375 |
(20, 100, 0.25, 0.5) | 0.1108 | 0.0106 | 0.5120 | 0.1750 | 3.5828 | 1.5280 | 27.2940 | 1.0984 |
(20, 100, 0.25, 1) | 0.0521 | 0.0047 | 0.3152 | 0.2321 | 5.0011 | 4.4017 | 27.9500 | 1.7346 |
(20, 100, 0.5, 0.5) | 0.0800 | 0.0066 | 0.4237 | 0.2145 | 4.3204 | 2.7268 | 35.2770 | 1.7099 |
(20, 100, 0.5, 1) | 0.0435 | 0.0064 | 0.1897 | 0.2614 | 3.7842 | 7.3197 | 33.4340 | 1.9935 |
(80, 100, 0.25, 0.5) | 0.1381 | 0.0534 | 0.5341 | 0.2676 | 2.9914 | 1.9738 | 118.4410 | 5.8678 |
(80, 100, 0.25, 1) | 0.0676 | 0.0148 | 0.4115 | 0.1058 | 5.3278 | 1.8796 | 120.0080 | 7.0440 |
(80, 100, 0.5, 0.5) | 0.1033 | 0.0238 | 0.5436 | 0.2278 | 4.3561 | 2.4909 | 184.1960 | 9.4721 |
(80, 100, 0.5, 1) | 0.0450 | 0.0075 | 0.2548 | 0.0952 | 4.7366 | 2.3818 | 201.1790 | 20.2812 |
1 number of constraints 2 dimension of x 3 ratio of the number of perturbation vectors for one row to m + n 4 scale of perturbation vectors 5 improvement ratio=(maximum radius-lower bound)/lower bound |
Instance (m1, n2, pert3, scale4) | Lower Bound | Maximum Radius | Improvement Ratio5 | CPU Time | ||||
Ave | Std | Ave | Std | Ave | Std | Ave | Std | |
(20, 20, 0.25, 0.5) | 0.4151 | 0.1551 | 1.1650 | 0.8647 | 2.3001 | 3.0673 | 15.8480 | 1.1491 |
(20, 20, 0.25, 1) | td> 0.2283 | 0.0969 | 0.7672 | 0.3066 | 2.6969 | 1.3452 | 15.6160 | 0.9467 |
(20, 20, 0.5, 0.5) | 0.3056 | 0.1443 | 1.0726 | 0.7539 | 2.8557 | 3.0440 | 17.0120 | 1.2904 |
(20, 20, 0.5, 1) | 0.1385 | 0.0818 | 0.4476 | 0.2327 | 2.6981 | 2.4415 | 18.3810 | 1.8375 |
(20, 100, 0.25, 0.5) | 0.1108 | 0.0106 | 0.5120 | 0.1750 | 3.5828 | 1.5280 | 27.2940 | 1.0984 |
(20, 100, 0.25, 1) | 0.0521 | 0.0047 | 0.3152 | 0.2321 | 5.0011 | 4.4017 | 27.9500 | 1.7346 |
(20, 100, 0.5, 0.5) | 0.0800 | 0.0066 | 0.4237 | 0.2145 | 4.3204 | 2.7268 | 35.2770 | 1.7099 |
(20, 100, 0.5, 1) | 0.0435 | 0.0064 | 0.1897 | 0.2614 | 3.7842 | 7.3197 | 33.4340 | 1.9935 |
(80, 100, 0.25, 0.5) | 0.1381 | 0.0534 | 0.5341 | 0.2676 | 2.9914 | 1.9738 | 118.4410 | 5.8678 |
(80, 100, 0.25, 1) | 0.0676 | 0.0148 | 0.4115 | 0.1058 | 5.3278 | 1.8796 | 120.0080 | 7.0440 |
(80, 100, 0.5, 0.5) | 0.1033 | 0.0238 | 0.5436 | 0.2278 | 4.3561 | 2.4909 | 184.1960 | 9.4721 |
(80, 100, 0.5, 1) | 0.0450 | 0.0075 | 0.2548 | 0.0952 | 4.7366 | 2.3818 | 201.1790 | 20.2812 |
1 number of constraints 2 dimension of x 3 ratio of the number of perturbation vectors for one row to m + n 4 scale of perturbation vectors 5 improvement ratio=(maximum radius-lower bound)/lower bound |
[1] |
Behrouz Kheirfam, Kamal mirnia. Multi-parametric sensitivity analysis in piecewise linear fractional programming. Journal of Industrial and Management Optimization, 2008, 4 (2) : 343-351. doi: 10.3934/jimo.2008.4.343 |
[2] |
Hui Zhang, Jian-Feng Cai, Lizhi Cheng, Jubo Zhu. Strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems and Imaging, 2012, 6 (2) : 357-372. doi: 10.3934/ipi.2012.6.357 |
[3] |
Behrouz Kheirfam. Multi-parametric sensitivity analysis of the constraint matrix in piecewise linear fractional programming. Journal of Industrial and Management Optimization, 2010, 6 (2) : 347-361. doi: 10.3934/jimo.2010.6.347 |
[4] |
Qingshan You, Qun Wan, Yipeng Liu. A short note on strongly convex programming for exact matrix completion and robust principal component analysis. Inverse Problems and Imaging, 2013, 7 (1) : 305-306. doi: 10.3934/ipi.2013.7.305 |
[5] |
Ling Zhang, Xiaoqi Sun. Stability analysis of time-varying delay neural network for convex quadratic programming with equality constraints and inequality constraints. Discrete and Continuous Dynamical Systems - B, 2022 doi: 10.3934/dcdsb.2022035 |
[6] |
Yue Qi, Tongyang Liu, Su Zhang, Yu Zhang. Robust Markowitz: Comprehensively maximizing Sharpe ratio by parametric-quadratic programming. Journal of Industrial and Management Optimization, 2022 doi: 10.3934/jimo.2021235 |
[7] |
Xiaojin Zheng, Zhongyi Jiang. Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2331-2343. doi: 10.3934/jimo.2020071 |
[8] |
Radu Ioan Boţ, Anca Grad, Gert Wanka. Sequential characterization of solutions in convex composite programming and applications to vector optimization. Journal of Industrial and Management Optimization, 2008, 4 (4) : 767-782. doi: 10.3934/jimo.2008.4.767 |
[9] |
Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial and Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075 |
[10] |
Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial and Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177 |
[11] |
Charles Fefferman. Interpolation by linear programming I. Discrete and Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477 |
[12] |
Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial and Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 |
[13] |
Rui Qian, Rong Hu, Ya-Ping Fang. Local smooth representation of solution sets in parametric linear fractional programming problems. Numerical Algebra, Control and Optimization, 2019, 9 (1) : 45-52. doi: 10.3934/naco.2019004 |
[14] |
Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323 |
[15] |
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 and Management Optimization, 2018, 14 (2) : 625-636. doi: 10.3934/jimo.2017064 |
[16] |
Ailing Zhang, Shunsuke Hayashi. Celis-Dennis-Tapia based approach to quadratic fractional programming problems with two quadratic constraints. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 83-98. doi: 10.3934/naco.2011.1.83 |
[17] |
Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193 |
[18] |
Mansoureh Alavi Hejazi, Soghra Nobakhtian. Optimality conditions for multiobjective fractional programming, via convexificators. Journal of Industrial and Management Optimization, 2020, 16 (2) : 623-631. doi: 10.3934/jimo.2018170 |
[19] |
Guowei Hua, Shouyang Wang, Chi Kin Chan, S. H. Hou. A fractional programming model for international facility location. Journal of Industrial and Management Optimization, 2009, 5 (3) : 629-649. doi: 10.3934/jimo.2009.5.629 |
[20] |
Ankhbayar Chuluunbaatar, Enkhbat Rentsen. Solving a fractional programming problem in a commercial bank. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021153 |
2020 Impact Factor: 1.801
Tools
Metrics
Other articles
by authors
[Back to Top]