Abstract
We present an exact formula for the radius of robust feasibility of uncertain linear programs with a compact and convex uncertainty set. The radius of robust feasibility provides a value for the maximal ‘size’ of an uncertainty set under which robust feasibility of the uncertain linear program can be guaranteed. By considering spectrahedral uncertainty sets, we obtain numerically tractable radius formulas for commonly used uncertainty sets of robust optimization, such as ellipsoids, balls, polytopes and boxes. In these cases, we show that the radius of robust feasibility can be found by solving a linearly constrained convex quadratic program or a minimax linear program. The results are illustrated by calculating the radius of robust feasibility of uncertain linear programs for several different uncertainty sets.
Similar content being viewed by others
References
Bertsimas, D., Thiele, A.: A robust optimization approach to supply chain management. Oper. Res. 54, 150–168 (2006)
Fabozzi, F.J., Huang, D., Zhou, G.: Robust portfolios: contributions from operations research and finance. Ann. Oper. Res. 176, 191–220 (2010)
Soyster, A.: Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 1, 1154–1157 (1973)
Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization, Princeton Ser. Appl. Math. Princeton University Press, Princeton (2009)
Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM Philadelphia (2001)
El Ghaoui, L., Lebret, H.: Robust solutions to least-squares problems with uncertain data. SIAM J. Matrix Anal. Appl. 18, 1035–1064 (1997)
Beck, A., Ben-Tal, A.: Duality in robust optimization: primal worst equals dual best. Oper. Res. Lett. 37, 1–6 (2009)
Beck, A., Eldar, Y.C., Ben-Tal, A.: Mean-squared error estimation for linear systems with block circulant uncertainty. SIAM J. Matrix Anal. Appl. 29, 712–730 (2007)
den Ben-Tal, A., Hertog, D., Vial, J.-P.: Deriving robust counterparts of nonlinear uncertain inequalities. Math. Program. 149, 265–299 (2015)
Bertsimas, D., Brown, D.B., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53, 464–501 (2011)
Bertsimas, D., Brown, D.B.: Constructing uncertainty sets for robust linear optimization. Oper. Res. 57, 1483–1495 (2009)
Gorissen, B.L., Blanc, H., den Hertog, D., Ben-Tal, A.: Technical note-deriving robust and globalized robust solutions of uncertain linear programs with general convex uncertainty sets. Oper. Res. 62, 672–679 (2014)
Jeyakumar, V., Li, G.: Characterizing robust set containments and solutions of uncertain linear programs without qualifications. Oper. Res. Lett. 38, 188–194 (2010)
Jeyakumar, V., Li, G., Vicente-Perez, J.: Robust SOS-convex polynomial programs: exact SDP relaxations. Optim. Lett. 9, 1–18 (2015)
Goberna, M.A., Jeyakumar, V., Li, G., Linh, N.: Radius of robust feasibility formulas for classes of convex programs with uncertain polynomial constraints. Oper. Res. Lett. 44, 67–73 (2016)
Goberna, M.A., Jeyakumar, V., Li, G., Perez, J.-V.: Robust solutions to multi-objective linear programs with uncertain data. Eur. J. Oper. Res. 242, 730–743 (2015)
Goberna, M.A., Jeyakumar, V., Li, G., Perez, J.-V.: Robust solutions of multi-objective linear semi-infinite programs under constraint data uncertainty. SIAM J. Optim. 24, 1402–1419 (2014)
Cánovas, M.J., López, M.A., Parra, J., Toledo, F.J.: Distance to ill-posedness and the consistency value of linear semi-infinite inequality systems. Math. Program. 103A, 95–126 (2005)
Cánovas, M.J., López, M.A., Parra, J., Toledo, F.J.: Distance to ill-posedness for linear inequality systems under block perturbations: convex and infinite-dimensional cases. Optimization 60, 925–946 (2011)
Cánovas, M.J., López, M.A., Parra, J., Todorov, M.I.: Stability and well-posedness in linear semi-infinite programming. SIAM J. Optim. 10, 82–98 (1999)
Schirotzek, W.: Nonsmooth Analysis. Universitext. Springer, Berlin (2007)
Goberna, M.A., López, M.A.: Linear Semi-Infinite Optimization. Wiley, Chichester (1998)
Chuong, T.D., Jeyakumar, V.: Robust global error bounds for uncertain linear inequality systems with applications. Linear Algebra Appl. 493, 183–205 (2016)
Nie, J.: Semidefinite representability. Semidefinite optimization and convex algebraic geometry, 251291, MOS–SIAM Ser. Optim., 13, SIAM, Philadelphia (2013)
Ramana, M., Goldman, A.J.: Some geometric results in semidefinite programming. J. Glob. Optim. 7, 33–50 (1995)
Vinzant, C.: What is a spectrahedron? Not. Am. Math. Soc. 61, 492–494 (2014)
Acknowledgements
The authors would like to thank the referees for the valuable comments and suggestions which have improved the final preparation of the paper. Research of the first author was supported by the UNSW Vice-Chancellor’s Postdoctoral Research Fellowship (RG134608/SIR50). Research of the second author was partially supported by a grant from the Australian Research Council.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Jean-Pierre Crouzeix.
Appendix
Appendix
In this section, we give the proof of Lemma 2.4 by exploiting some techniques from [15].
Proof of Lemma 2.4
We assume by contradiction that there exists \(\delta >0\) such that
Applying the separation theorem, we find a nonzero element \((u,v)\in {\mathbb {R}}^n\times {\mathbb {R}}\) such that
Obviously \(v\le 0\) because of \(0_{n+1}\in \mathrm{cone}\Big \{\bigcup \limits _{j=1}^p[(-{\overline{a}}_j,-{\overline{b}}_j)-(\alpha +\delta )Z]\Big \},\) and further, we assert that
Otherwise, there exists \((a_0,b_0)\in \mathrm{cone}\Big \{\bigcup \limits _{j=1}^p[(-{\overline{a}}_j,-{\overline{b}}_j)-(\alpha +\delta )Z]\Big \}\) such that \(\langle (u,v),(a_0,b_0)\rangle < 0.\) Then, \(\lambda (a_0,b_0)\in \mathrm{cone}\Big \{\bigcup \limits _{j=1}^p[(-{\overline{a}}_j,-{\overline{b}}_j)-(\alpha +\delta )Z]\Big \}\) for all \(\lambda >0\), and so,
This fact contradicts (62) and thus, the assertion (63) holds.
By our assumption,
Then, there exists a sequence \(\{(u_k,v_k)\}\subset \mathrm{cone}\Big \{\bigcup \limits _{j=1}^p[(-{\overline{a}}_j,-{\overline{b}}_j)-\alpha Z]\Big \}\) such that
So, for each \(k\in {\mathbb {N}}\), there exist \(z_k^j\in Z\) and \(\lambda _k^j\ge 0, j=1,\ldots ,p,\) such that
We claim that there exists \(\kappa >0\) such that
If this is not the case, then by passing to a subsequence if necessary, we may assume that \(\sum _{j=1}^{p}\lambda _k^j\rightarrow 0\) as \(k\rightarrow \infty .\) It implies by (65) that \((u_k,v_k)\rightarrow 0_{n+1}\) as \(k\rightarrow \infty \) due to the compactness of Z. This contradicts (64), and so, our claim in (66) holds.
By \(0_{n+1}\in \mathrm{int}Z,\) we find \(\rho >0\) such that \(\rho {\mathbb {B}}_{n+1}\subset Z.\) Note that \(||(u,v)||=\max \limits _{w^*\in {\mathbb {B}}_{n+1}}{\langle (u,v),w^*\rangle },\) and hence, there exists \(w^*\in {\mathbb {B}}_{n+1}\) such that \(||(u,v)||=\langle (u,v),w^*\rangle .\) Now, letting \(z:=\rho w^*,\) it follows that \(z\in \rho {\mathbb {B}}_{n+1}\subset Z\) and that
Taking (65) into account, we see that
where \(\big (\frac{\alpha }{\alpha +\delta } z^j_k+\frac{\delta }{\alpha +\delta } z\big )\in Z\) inasmuch as Z is a convex set. Granting this, (63) and (67) entail that
This together with (66) entails that
Letting \(k\rightarrow \infty \) in (68), we arrive at \(0\le v-\delta \rho \kappa ||(u,v)||\), which is absurd by virtue of \(v\le 0\) and \((u,v)\ne 0_{n+1}.\) So, the proof is complete. \(\square \)
Rights and permissions
About this article
Cite this article
Chuong, T.D., Jeyakumar, V. An Exact Formula for Radius of Robust Feasibility of Uncertain Linear Programs. J Optim Theory Appl 173, 203–226 (2017). https://doi.org/10.1007/s10957-017-1067-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-017-1067-6
Keywords
- Uncertain linear program
- Robust linear optimization
- Spectrahedron
- Robust solution
- Linear matrix inequality