[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

New characterizations of Hoffman constants for systems of linear constraints

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

We give a characterization of the Hoffman constant of a system of linear constraints in \({{\mathbb {R}}}^n\) relative to a reference polyhedron \(R\subseteq {{\mathbb {R}}}^n\). The reference polyhedron R represents constraints that are easy to satisfy such as box constraints. In the special case \(R = {{\mathbb {R}}}^n\), we obtain a novel characterization of the classical Hoffman constant. More precisely, suppose \(R\subseteq \mathbb {R}^n\) is a reference polyhedron, \(A\in {{\mathbb {R}}}^{m\times n},\) and \(A(R):=\{Ax: x\in R\}\). We characterize the sharpest constant \(H(A\vert R)\) such that for all \(b \in A(R) + {{\mathbb {R}}}^m_+\) and \(u\in R\)

$$\begin{aligned} {\mathrm {dist}}(u, P_{A}(b)\cap R) \le H(A\vert R) \cdot \Vert (Au-b)_+\Vert , \end{aligned}$$

where \(P_A(b) = \{x\in {{\mathbb {R}}}^n:Ax\le b\}\). Our characterization is stated in terms of the largest of a canonical collection of easily computable Hoffman constants. Our characterization in turn suggests new algorithmic procedures to compute Hoffman constants.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Amelunxen, D., Bürgisser, P.: A coordinate-free condition number for convex programming. SIAM J. Optim. 22(3), 1029–1041 (2012)

    MathSciNet  MATH  Google Scholar 

  2. Azé, D., Corvellec, J.: On the sensitivity analysis of Hoffman constants for systems of linear inequalities. SIAM J. Optim. 12(4), 913–927 (2002)

    MathSciNet  MATH  Google Scholar 

  3. Bauschke, H., Bolte, J., Teboulle, M.: A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Math. Oper. Res. 42(2), 330–348 (2016)

    MathSciNet  MATH  Google Scholar 

  4. Beck, A., Shtern, S.: Linearly convergent away-step conditional gradient for non-strongly convex functions. Math. Program. 164, 1–27 (2017)

    MathSciNet  MATH  Google Scholar 

  5. Bürgisser, P., Cucker, F.: Condition. Springer, Berlin (2013)

    MATH  Google Scholar 

  6. Burke, J., Tseng, P.: A unified analysis of Hoffman’s bound via Fenchel duality. SIAM J. Optim. 6(2), 265–282 (1996)

    MathSciNet  MATH  Google Scholar 

  7. Epelman, M., Freund, R.: A new condition measure, preconditioners, and relations between different measures of conditioning for conic linear systems. SIAM J. Optim. 12, 627–655 (2002)

    MathSciNet  MATH  Google Scholar 

  8. Freund, R.: Complexity of convex optimization using geometry-based measures and a reference point. Math. Program. 99, 197–221 (2004)

    MathSciNet  MATH  Google Scholar 

  9. Freund, R., Vera, J.: Some characterizations and properties of the “distance to ill-posedness” and the condition measure of a conic linear system. Math. Program. 86, 225–260 (1999)

    MathSciNet  MATH  Google Scholar 

  10. Freund, R., Vera, J.: On the complexity of computing estimates of condition measures of a conic linear system. Math. Oper. Res. 28(4), 625–648 (2003)

    MathSciNet  MATH  Google Scholar 

  11. Garber, D.: Fast rates for online gradient descent without strong convexity via Hoffman’s bound. arXiv preprint arXiv:1802.04623 (2018)

  12. Granot, F., Skorin-Kapov, J.: Some proximity and sensitivity results in quadratic integer programming. Math. Program. 47(1–3), 259–268 (1990)

    MathSciNet  MATH  Google Scholar 

  13. Güler, O., Hoffman, A., Rothblum, U.: Approximations to solutions to systems of linear inequalities. SIAM J. Matrix Anal. Appl. 16(2), 688–696 (1995)

    MathSciNet  MATH  Google Scholar 

  14. Gutman, D., Peña, J.: The condition number of a function relative to a set. arXiv preprint arXiv:1901.08359 (2019)

  15. Hoffman, A.: On approximate solutions of systems of linear inequalities. J. Res. Natl. Bur. Stand. 49(4), 263–265 (1952)

    MathSciNet  Google Scholar 

  16. IBM ILOG CPLEX Optimization Studio-CPLEX. Users manual-version 12 release 6 (2013)

  17. Jourani, A.: Hoffman’s error bound, local controllability, and sensitivity analysis. SIAM J. Control Optim. 38(3), 947–970 (2000)

    MathSciNet  MATH  Google Scholar 

  18. Júdice, J.: Algorithms for linear programming with linear complementarity constraints. Top 20(1), 4–25 (2012)

    MathSciNet  MATH  Google Scholar 

  19. Klatte, D., Thiere, G.: Error bounds for solutions of linear equations and inequalities. Z. Oper. Res. 41(2), 191–214 (1995)

    MathSciNet  MATH  Google Scholar 

  20. Lacoste-Julien, S., Jaggi, M.: On the global linear convergence of Frank–Wolfe optimization variants. In: Advances in Neural Information Processing Systems (NIPS) (2015)

  21. Leventhal, D., Lewis, A.: Randomized methods for linear constraints: convergence rates and conditioning. Math. Oper. Res. 35, 641–654 (2010)

    MathSciNet  MATH  Google Scholar 

  22. Lewis, A.: Ill-conditioned convex processes and linear inequalities. Math. Oper. Res. 24, 829–834 (1999)

    MathSciNet  MATH  Google Scholar 

  23. Lewis, A.: The structured distance to ill-posedness for conic systems. Math. Oper. Res. 29, 776–785 (2005)

    MathSciNet  MATH  Google Scholar 

  24. Li, W.: The sharp Lipschitz constants for feasible and optimal solutions of a perturbed linear program. Linear Algebra Appl. 187, 15–40 (1993)

    MathSciNet  MATH  Google Scholar 

  25. Lu, H.: Relative-continuity” for non-Lipschitz non-smooth convex optimization using stochastic (or deterministic) mirror descent. arXiv preprint arXiv:1710.04718 (2017)

  26. Lu, H., Freund, R., Nesterov, Y.: Relatively smooth convex optimization by first-order methods, and applications. SIAM J. Optim. 28(1), 333–354 (2018)

    MathSciNet  MATH  Google Scholar 

  27. Luo, Z., Tseng, P.: Error bounds and convergence analysis of feasible descent methods: a general approach. Ann. Oper. Res. 46(1), 157–178 (1993)

    MathSciNet  MATH  Google Scholar 

  28. Mangasarian, O., Shiau, T.-H.: Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems. SIAM J. Control Optim. 25(3), 583–595 (1987)

    MathSciNet  MATH  Google Scholar 

  29. Necoara, I., Nesterov, Y., Glineur, F.: Linear convergence of first order methods for non-strongly convex optimization. Math. Program. 175, 69–107 (2019)

    MathSciNet  MATH  Google Scholar 

  30. Nguyen, T.: A stroll in the jungle of error bounds. arXiv preprint arXiv:1704.06938 (2017)

  31. Pang, J.S.: Error bounds in mathematical programming. Math. Program. 79, 299–332 (1997)

    MathSciNet  MATH  Google Scholar 

  32. Peña, J.: Understanding the geometry on infeasible perturbations of a conic linear system. SIAM J. Optim. 10, 534–550 (2000)

    MathSciNet  MATH  Google Scholar 

  33. Peña, J.: A characterization of the distance to infeasibility under block-structured perturbations. Linear Algebra Appl. 370, 193–216 (2003)

    MathSciNet  MATH  Google Scholar 

  34. Peña, J., Rodríguez, D.: Polytope conditioning and linear convergence of the Frank–Wolfe algorithm. Math. Oper. Res. 44, 1–18 (2019)

    MathSciNet  MATH  Google Scholar 

  35. Pineda, S., Bylling, H., Morales, J.: Efficiently solving linear bilevel programming problems using off-the-shelf optimization software. Optim. Eng. 19(1), 187–211 (2018)

    MathSciNet  MATH  Google Scholar 

  36. Ramdas, A., Peña, J.: Towards a deeper geometric, analytic and algorithmic understanding of margins. Optim. Methods Softw. 31(2), 377–391 (2016)

    MathSciNet  MATH  Google Scholar 

  37. Renegar, J.: Incorporating condition measures into the complexity theory of linear programming. SIAM J. Optim. 5, 506–524 (1995)

    MathSciNet  MATH  Google Scholar 

  38. Renegar, J.: Linear programming, complexity theory and elementary functional analysis. Math. Program. 70, 279–351 (1995)

    MathSciNet  MATH  Google Scholar 

  39. Robinson, S.: Bounds for error in the solution set of a perturbed linear program. Linear Algebra Appl. 6, 69–81 (1973)

    MathSciNet  MATH  Google Scholar 

  40. Siddiqui, S., Gabriel, S.: An SOS1-based approach for solving mpecs with a natural gas market application. Netw. Spat. Econ. 13(2), 205–227 (2013)

    MathSciNet  MATH  Google Scholar 

  41. Stein, O.: Error bounds for mixed integer linear optimization problems. Math. Program. 156(1–2), 101–123 (2016)

    MathSciNet  MATH  Google Scholar 

  42. Stewart, G.: On scaled projections and pseudoinverses. Linear Algebra Appl. 112, 189–193 (1989)

    MathSciNet  MATH  Google Scholar 

  43. Teboulle, M.: A simplified view of first order methods for optimization. Math. Program. 1, 1–30 (2018)

    MathSciNet  MATH  Google Scholar 

  44. Todd, M.: A Dantzig–Wolfe-like variant of Karmarkar’s interior-point linear programming algorithm. Oper. Res. 38(6), 1006–1018 (1990)

    MathSciNet  MATH  Google Scholar 

  45. Van Ngai, H., Théra, M.: Error bounds for systems of lower semicontinuous functions in Asplund spaces. Math. Program. 116(1–2), 397–427 (2009)

    MathSciNet  MATH  Google Scholar 

  46. Vavasis, S., Ye, Y.: A primal-dual interior point method whose running time depends only on the constraint matrix. Math. Program. 74(1), 79–120 (1996)

    MathSciNet  MATH  Google Scholar 

  47. Wang, P., Lin, C.: Iteration complexity of feasible descent methods for convex optimization. J. Mach. Learn. Res. 15(1), 1523–1548 (2014)

    MathSciNet  MATH  Google Scholar 

  48. Xia, W., Vera, J., Zuluaga, L.F.: Globally solving non-convex quadratic programs via linear integer programming techniques. INFORMS J. Comput. (2020). https://doi.org/10.1287/ijoc.2018.0883

  49. Zalinescu, C.: Sharp estimates for Hoffman’s constant for systems of linear inequalities and equalities. SIAM J. Optim. 14(2), 517–533 (2003)

    MathSciNet  MATH  Google Scholar 

  50. Zhang, S.: Global error bounds for convex conic problems. SIAM J. Optim. 10(3), 836–851 (2000)

    MathSciNet  MATH  Google Scholar 

  51. Zhou, Z., So, A.: A unified approach to error bounds for structured convex optimization problems. Math. Program. 165(2), 689–728 (2017)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

Javier Peña’s research has been funded by NSF Grant CMMI-1534850.

Author information

Authors and Affiliations

  1. Tepper School of Business, Carnegie Mellon University, Pittsburgh, USA

    Javier Peña

  2. Department of Econometrics and Operations Research, Tilburg University, Tilburg, The Netherlands

    Juan C. Vera

  3. Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, USA

    Luis F. Zuluaga

Authors
  1. Javier Peña
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Juan C. Vera
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Luis F. Zuluaga
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Javier Peña.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Peña, J., Vera, J.C. & Zuluaga, L.F. New characterizations of Hoffman constants for systems of linear constraints. Math. Program. 187, 79–109 (2021). https://doi.org/10.1007/s10107-020-01473-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-020-01473-6

Mathematics Subject Classification

Search

Navigation