[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Log in

An Exact Formula for Radius of Robust Feasibility of Uncertain Linear Programs

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Bertsimas, D., Thiele, A.: A robust optimization approach to supply chain management. Oper. Res. 54, 150–168 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  2. Fabozzi, F.J., Huang, D., Zhou, G.: Robust portfolios: contributions from operations research and finance. Ann. Oper. Res. 176, 191–220 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  3. Soyster, A.: Convex programming with set-inclusive constraints and applications to inexact linear programming. Oper. Res. 1, 1154–1157 (1973)

    Article  MATH  Google Scholar 

  4. Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization, Princeton Ser. Appl. Math. Princeton University Press, Princeton (2009)

    Google Scholar 

  5. Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM Philadelphia (2001)

  6. El Ghaoui, L., Lebret, H.: Robust solutions to least-squares problems with uncertain data. SIAM J. Matrix Anal. Appl. 18, 1035–1064 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  7. Beck, A., Ben-Tal, A.: Duality in robust optimization: primal worst equals dual best. Oper. Res. Lett. 37, 1–6 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. 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)

    Article  MathSciNet  MATH  Google Scholar 

  9. den Ben-Tal, A., Hertog, D., Vial, J.-P.: Deriving robust counterparts of nonlinear uncertain inequalities. Math. Program. 149, 265–299 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  10. Bertsimas, D., Brown, D.B., Caramanis, C.: Theory and applications of robust optimization. SIAM Rev. 53, 464–501 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  11. Bertsimas, D., Brown, D.B.: Constructing uncertainty sets for robust linear optimization. Oper. Res. 57, 1483–1495 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  12. 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)

    Article  MathSciNet  MATH  Google Scholar 

  13. Jeyakumar, V., Li, G.: Characterizing robust set containments and solutions of uncertain linear programs without qualifications. Oper. Res. Lett. 38, 188–194 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  14. Jeyakumar, V., Li, G., Vicente-Perez, J.: Robust SOS-convex polynomial programs: exact SDP relaxations. Optim. Lett. 9, 1–18 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  15. 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)

    Article  MathSciNet  Google Scholar 

  16. 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)

    Article  MathSciNet  MATH  Google Scholar 

  17. 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)

    Article  MathSciNet  MATH  Google Scholar 

  18. 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)

    Article  MathSciNet  MATH  Google Scholar 

  19. 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)

    Article  MathSciNet  MATH  Google Scholar 

  20. 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)

    Article  MathSciNet  MATH  Google Scholar 

  21. Schirotzek, W.: Nonsmooth Analysis. Universitext. Springer, Berlin (2007)

    Book  MATH  Google Scholar 

  22. Goberna, M.A., López, M.A.: Linear Semi-Infinite Optimization. Wiley, Chichester (1998)

    MATH  Google Scholar 

  23. Chuong, T.D., Jeyakumar, V.: Robust global error bounds for uncertain linear inequality systems with applications. Linear Algebra Appl. 493, 183–205 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  24. Nie, J.: Semidefinite representability. Semidefinite optimization and convex algebraic geometry, 251291, MOS–SIAM Ser. Optim., 13, SIAM, Philadelphia (2013)

  25. Ramana, M., Goldman, A.J.: Some geometric results in semidefinite programming. J. Glob. Optim. 7, 33–50 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  26. Vinzant, C.: What is a spectrahedron? Not. Am. Math. Soc. 61, 492–494 (2014)

    MathSciNet  MATH  Google Scholar 

Download references

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

Authors

Corresponding author

Correspondence to T. D. Chuong.

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

$$\begin{aligned} (0_n,1)\notin \mathrm{cone}\Big \{\bigcup _{j=1}^p[(-{\overline{a}}_j,-{\overline{b}}_j)-(\alpha +\delta )Z]\Big \}. \end{aligned}$$

Applying the separation theorem, we find a nonzero element \((u,v)\in {\mathbb {R}}^n\times {\mathbb {R}}\) such that

$$\begin{aligned} v\le \inf {\left\{ \langle (u,v),(a,b)\rangle \,:\, (a,b)\in \mathrm{cone}\Big \{\bigcup _{j=1}^p[(-{\overline{a}}_j,-{\overline{b}}_j)-(\alpha +\delta )Z]\Big \}\right\} }. \end{aligned}$$
(62)

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

$$\begin{aligned} \langle (u,v),(a,b)\rangle \ge 0\; \text{ for } \text{ all } \; (a,b)\in \mathrm{cone}\Big \{\bigcup \limits _{j=1}^p[(-{\overline{a}}_j,-{\overline{b}}_j)-(\alpha +\delta )Z]\Big \}. \end{aligned}$$
(63)

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,

$$\begin{aligned} \langle (u,v),\lambda (a_0,b_0)\rangle =\lambda \langle (u,v),(a_0,b_0)\rangle \rightarrow -\infty \text{ as } \lambda \rightarrow +\infty . \end{aligned}$$

This fact contradicts (62) and thus, the assertion (63) holds.

By our assumption,

$$\begin{aligned} (0_n,1)\in \mathrm{cl\, cone}\Big \{\bigcup \limits _{j=1}^p[(-{\overline{a}}_j,-{\overline{b}}_j)-\alpha Z]\Big \}. \end{aligned}$$

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

$$\begin{aligned} (u_k,v_k)\rightarrow (0_n,1) \; \text{ as } \; k\rightarrow \infty . \end{aligned}$$
(64)

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

$$\begin{aligned} (u_k,v_k)=\sum _{j=1}^{p}\lambda _k^j \left[ \left( -{\overline{a}}_j,-{\overline{b}}_j\right) -\alpha z^j_k\right] . \end{aligned}$$
(65)

We claim that there exists \(\kappa >0\) such that

$$\begin{aligned} \sum _{j=1}^{p}\lambda _k^j\ge \kappa \; \text{ for } \text{ all } \; k\in {\mathbb {N}}. \end{aligned}$$
(66)

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

$$\begin{aligned} \langle (u,v),z\rangle =\rho ||(u,v)||. \end{aligned}$$
(67)

Taking (65) into account, we see that

$$\begin{aligned} (u_k,v_k)-\delta \sum _{j=1}^{p}\lambda _k^jz&=\sum _{j=1}^{p}\lambda _k^j [(-{\overline{a}}_j,-{\overline{b}}_j)-\alpha z^j_k-\delta z]\\&=\sum _{j=1}^{p}\lambda _k^j \left[ (-{\overline{a}}_j,-{\overline{b}}_j)-(\alpha +\delta )\left( \frac{\alpha }{\alpha +\delta } z^j_k+\frac{\delta }{\alpha +\delta } z\right) \right] \\&\in \mathrm{cone}\Bigg \{\bigcup \limits _{j=1}^p[(-{\overline{a}}_j,-{\overline{b}}_j)-(\alpha +\delta )Z]\Bigg \},\; \forall k\in {\mathbb {N}}, \end{aligned}$$

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

$$\begin{aligned}0\le \langle (u,v),(u_k,v_k)-\delta \sum _{j=1}^{p}\lambda _k^jz\rangle&=\langle (u,v),(u_k,v_k)\rangle -\delta \sum _{j=1}^{p}\lambda _k^j\langle (u,v),z\rangle \\&=\langle (u,v),(u_k,v_k)\rangle -\delta \sum _{j=1}^{p}\lambda _k^j\rho ||(u,v)||. \end{aligned}$$

This together with (66) entails that

$$\begin{aligned} 0\le \langle (u,v),(u_k,v_k)\rangle -\delta \rho \kappa ||(u,v)||, \;\forall k\in {\mathbb {N}}. \end{aligned}$$
(68)

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

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

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

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-017-1067-6

Keywords

Mathematics Subject Classification

Navigation