-
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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. 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. |
[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. Google Scholar |
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] |
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] |
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 |
[3] |
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 |
[4] |
Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225 |
[5] |
María J. Garrido-Atienza, Bohdan Maslowski, Jana Šnupárková. Semilinear stochastic equations with bilinear fractional noise. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3075-3094. doi: 10.3934/dcdsb.2016088 |
[6] |
Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141 |
[7] |
Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881 |
[8] |
Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327 |
[9] |
Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437 |
[10] |
Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311 |
[11] |
Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024 |
[12] |
Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213 |
[13] |
Shihu Li, Wei Liu, Yingchao Xie. Large deviations for stochastic 3D Leray-$ \alpha $ model with fractional dissipation. Communications on Pure & Applied Analysis, 2019, 18 (5) : 2491-2509. doi: 10.3934/cpaa.2019113 |
[14] |
Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1 |
[15] |
Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367 |
[16] |
Lei Liu, Li Wu. Multiplicity of closed characteristics on $ P $-symmetric compact convex hypersurfaces in $ \mathbb{R}^{2n} $. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020378 |
[17] |
Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119 |
[18] |
W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349 |
[19] |
Carlos Fresneda-Portillo, Sergey E. Mikhailov. Analysis of Boundary-Domain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3059-3088. doi: 10.3934/cpaa.2019137 |
[20] |
Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]