American Institute of Mathematical Sciences

Advanced
July  2020, 16(4): 2029-2044. doi: 10.3934/jimo.2019041

Robust sensitivity analysis for linear programming with ellipsoidal perturbation

Ruotian Gao and  Wenxun Xing ,

Department of Mathematical Sciences, Tsinghua University, Beijing 100086, China

* Corresponding author

Received  September 2018 Revised  January 2019 Published  May 2019

Fund Project: Funding: This research has been supported by the National Natural Science Foundation of China under Grant numbers 11771243 and 11571029

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.

Keywords: Linear programming, sensitivity analysis, robust optimization, convex quadratic programming, fractional programming.
Mathematics Subject Classification: Primary: 90C31, 90C05; Secondary: 90C20.
Citation: Ruotian Gao, Wenxun Xing. Robust sensitivity analysis for linear programming with ellipsoidal perturbation. Journal of Industrial & Management Optimization, 2020, 16 (4) : 2029-2044. doi: 10.3934/jimo.2019041
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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

D. Bertsimas and M. Sim, The price of robustness, Operations Research, 52 (2004), 35-53.  doi: 10.1287/opre.1030.0065.  Google Scholar

[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.  Google Scholar

[7]

G. E. Dullerud and F. G. Paganini, A Course in Robust Control Theory–-A Convex Approach, Springer-Verlag, New York, 2000. Google Scholar

[8]

M. Frank and P. Wolfe, An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3 (1956), 95-110.  doi: 10.1002/nav.3800030109.  Google Scholar

[9]

S. I. Gass, Linear Programming: Methods and Applications, Corrected reprint of the 1995 fifth edition. Dover Publications, Inc., Mineola, NY, 2003.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

A. Marandi, A. Ben-Tal, D. D. Hertog and B. Melenberg, Extending the scope of robust quadratic optimization, Available on Optimization Online, 2017. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[16]

K. Zhou, J. C. Doyle and K. Glover, Robust and Optimal Control, Prentice Hall Englewood Cliffs, NJ, 1996. Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[5]

D. Bertsimas and M. Sim, The price of robustness, Operations Research, 52 (2004), 35-53.  doi: 10.1287/opre.1030.0065.  Google Scholar

[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.  Google Scholar

[7]

G. E. Dullerud and F. G. Paganini, A Course in Robust Control Theory–-A Convex Approach, Springer-Verlag, New York, 2000. Google Scholar

[8]

M. Frank and P. Wolfe, An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3 (1956), 95-110.  doi: 10.1002/nav.3800030109.  Google Scholar

[9]

S. I. Gass, Linear Programming: Methods and Applications, Corrected reprint of the 1995 fifth edition. Dover Publications, Inc., Mineola, NY, 2003.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

A. Marandi, A. Ben-Tal, D. D. Hertog and B. Melenberg, Extending the scope of robust quadratic optimization, Available on Optimization Online, 2017. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[16]

K. Zhou, J. C. Doyle and K. Glover, Robust and Optimal Control, Prentice Hall Englewood Cliffs, NJ, 1996. Google Scholar

Table 1.  Numerical Results
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
Table Options

Download as excel

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]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[2]

Qing Liu, Bingo Wing-Kuen Ling, Qingyun Dai, Qing Miao, Caixia Liu. Optimal maximally decimated M-channel mirrored paraunitary linear phase FIR filter bank design via norm relaxed sequential quadratic programming. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1993-2011. doi: 10.3934/jimo.2020055
[3]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[4]

Vladimir Gaitsgory, Ilya Shvartsman. Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021102
[5]

Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058
[6]

Khosro Sayevand, Valeyollah Moradi. A robust computational framework for analyzing fractional dynamical systems. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021022
[7]

Tadeusz Kaczorek, Andrzej Ruszewski. Analysis of the fractional descriptor discrete-time linear systems by the use of the shuffle algorithm. Journal of Computational Dynamics, 2021  doi: 10.3934/jcd.2021007
[8]

Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034
[9]

Xue Qiao, Zheng Wang, Haoxun Chen. Joint optimal pricing and inventory management policy and its sensitivity analysis for perishable products: lost sale case. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021079
[10]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023
[11]

Bingru Zhang, Chuanye Gu, Jueyou Li. Distributed convex optimization with coupling constraints over time-varying directed graphs†. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2119-2138. doi: 10.3934/jimo.2020061
[12]

Prabhu Manyem. A note on optimization modelling of piecewise linear delay costing in the airline industry. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1809-1823. doi: 10.3934/jimo.2020047
[13]

Zehui Jia, Xue Gao, Xingju Cai, Deren Han. The convergence rate analysis of the symmetric ADMM for the nonconvex separable optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1943-1971. doi: 10.3934/jimo.2020053
[14]

Jun Moon. Linear-quadratic mean-field type stackelberg differential games for stochastic jump-diffusion systems. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021026
[15]

Xianbang Chen, Yang Liu, Bin Li. Adjustable robust optimization in enabling optimal day-ahead economic dispatch of CCHP-MG considering uncertainties of wind-solar power and electric vehicle. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1639-1661. doi: 10.3934/jimo.2020038
[16]

Kehan Si, Zhenda Xu, Ka Fai Cedric Yiu, Xun Li. Open-loop solvability for mean-field stochastic linear quadratic optimal control problems of Markov regime-switching system. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021074
[17]

Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Existence results and stability analysis for a nonlinear fractional boundary value problem on a circular ring with an attached edge : A study of fractional calculus on metric graph. Networks & Heterogeneous Media, 2021, 16 (2) : 155-185. doi: 10.3934/nhm.2021003
[18]

Peng Luo. Comparison theorem for diagonally quadratic BSDEs. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2543-2557. doi: 10.3934/dcds.2020374
[19]

Alexander Tolstonogov. BV solutions of a convex sweeping process with a composed perturbation. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021012
[20]

Paul A. Glendinning, David J. W. Simpson. A constructive approach to robust chaos using invariant manifolds and expanding cones. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3367-3387. doi: 10.3934/dcds.2020409

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (124)
  • HTML views (580)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences