{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T11:36:47Z","timestamp":1757590607410,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T00:00:00Z","timestamp":1691539200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T00:00:00Z","timestamp":1691539200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008047","name":"Carnegie Mellon University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008047","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2024,1]]},"abstract":"Abstract<\/jats:title>Let $$A\\in {\\mathbb R}^{m\\times n}\\setminus \\{0\\}$$<\/jats:tex-math>\n \n A<\/mml:mi>\n \u2208<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n \n m<\/mml:mi>\n \u00d7<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msup>\n \\<\/mml:mo>\n \n {<\/mml:mo>\n 0<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$P:=\\{x:Ax\\le 0\\}$$<\/jats:tex-math>\n \n P<\/mml:mi>\n :<\/mml:mo>\n =<\/mml:mo>\n {<\/mml:mo>\n x<\/mml:mi>\n :<\/mml:mo>\n A<\/mml:mi>\n x<\/mml:mi>\n \u2264<\/mml:mo>\n 0<\/mml:mn>\n }<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This paper provides a procedure to compute an upper bound on the following homogeneous Hoffman constant<\/jats:italic>$$\\begin{aligned} H_0(A):= \\sup _{u\\in {\\mathbb R}^n \\setminus P} \\frac{{{\\,\\textrm{dist}\\,}}(u,P)}{{{\\,\\textrm{dist}\\,}}(Au, {\\mathbb R}^m_-)}. \\end{aligned}$$<\/jats:tex-math>\n \n \n \n \n \n \n H<\/mml:mi>\n 0<\/mml:mn>\n <\/mml:msub>\n \n (<\/mml:mo>\n A<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n :<\/mml:mo>\n =<\/mml:mo>\n \n sup<\/mml:mo>\n \n u<\/mml:mi>\n \u2208<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n n<\/mml:mi>\n <\/mml:msup>\n \\<\/mml:mo>\n P<\/mml:mi>\n <\/mml:mrow>\n <\/mml:munder>\n \n \n \n \n dist<\/mml:mtext>\n \n <\/mml:mrow>\n (<\/mml:mo>\n u<\/mml:mi>\n ,<\/mml:mo>\n P<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \n \n \n dist<\/mml:mtext>\n \n <\/mml:mrow>\n (<\/mml:mo>\n A<\/mml:mi>\n u<\/mml:mi>\n ,<\/mml:mo>\n \n \n R<\/mml:mi>\n <\/mml:mrow>\n -<\/mml:mo>\n m<\/mml:mi>\n <\/mml:msubsup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mfrac>\n .<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:disp-formula>In sharp contrast to the intractability of computing more general Hoffman constants, the procedure described in this paper is entirely tractable and easily implementable.<\/jats:p>","DOI":"10.1007\/s10589-023-00514-y","type":"journal-article","created":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T11:02:31Z","timestamp":1691578951000},"page":"323-335","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["An easily computable upper bound on the Hoffman constant for homogeneous inequality systems"],"prefix":"10.1007","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5698-1918","authenticated-orcid":false,"given":"Javier F.","family":"Pe\u00f1a","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,8,9]]},"reference":[{"key":"514_CR1","doi-asserted-by":"crossref","unstructured":"D. Applegate, O. Hinder, H. Lu, M. Lubin: Faster first-order primal-dual methods for linear programming using restarts and sharpness. Math. Program. 1\u201352 (2022)","DOI":"10.1007\/s10107-022-01901-9"},{"issue":"4","key":"514_CR2","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1137\/S1052623400375853","volume":"12","author":"D Az\u00e9","year":"2002","unstructured":"Az\u00e9, D., Corvellec, J.: On the sensitivity analysis of Hoffman constants for systems of linear inequalities. SIAM J. Optim. 12(4), 913\u2013927 (2002)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"514_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-016-1069-4","volume":"164","author":"A Beck","year":"2017","unstructured":"Beck, A., Shtern, S.: Linearly convergent away-step conditional gradient for non-strongly convex functions. Math. Program. 164(1), 1\u201327 (2017)","journal-title":"Math. Program."},{"issue":"2","key":"514_CR4","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1137\/0806015","volume":"6","author":"J Burke","year":"1996","unstructured":"Burke, J., Tseng, P.: A unified analysis of Hoffman\u2019s bound via Fenchel duality. SIAM J. Optim. 6(2), 265\u2013282 (1996)","journal-title":"SIAM J. Optim."},{"key":"514_CR5","doi-asserted-by":"crossref","unstructured":"Burke, J.V., Deng, S.: Weak sharp minima revisited, part III: Error bounds for differentiable convex inclusions. Math. Program. 116(1\u20132), 37\u201356 (2009)","DOI":"10.1007\/s10107-007-0130-8"},{"issue":"2","key":"514_CR6","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1137\/S0895479892237744","volume":"16","author":"O G\u00fcler","year":"1995","unstructured":"G\u00fcler, O., Hoffman, A., Rothblum, U.: Approximations to solutions to systems of linear inequalities. SIAM J. Matrix Anal. Appl. 16(2), 688\u2013696 (1995)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"4","key":"514_CR7","doi-asserted-by":"publisher","first-page":"263","DOI":"10.6028\/jres.049.027","volume":"49","author":"A Hoffman","year":"1952","unstructured":"Hoffman, A.: On approximate solutions of systems of linear inequalities. J. Res. Natl. Bur. Stand. 49(4), 263\u2013265 (1952)","journal-title":"J. Res. Natl. Bur. Stand."},{"issue":"1","key":"514_CR8","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1006\/jcom.1995.1005","volume":"11","author":"L Khachiyan","year":"1995","unstructured":"Khachiyan, L.: On the complexity of approximating extremal determinants in matrices. J. Complex. 11(1), 138\u2013153 (1995)","journal-title":"J. Complex."},{"issue":"2","key":"514_CR9","first-page":"191","volume":"41","author":"D Klatte","year":"1995","unstructured":"Klatte, D., Thiere, G.: Error bounds for solutions of linear equations and inequalities. Z. Oper. Res. 41(2), 191\u2013214 (1995)","journal-title":"Z. Oper. Res."},{"key":"514_CR10","unstructured":"Lacoste-Julien, S., Jaggi, M.: On the global linear convergence of Frank-Wolfe optimization variants. In: Advances in Neural Information Processing Systems (NIPS) (2015)"},{"key":"514_CR11","doi-asserted-by":"publisher","first-page":"641","DOI":"10.1287\/moor.1100.0456","volume":"35","author":"D Leventhal","year":"2010","unstructured":"Leventhal, D., Lewis, A.: Randomized methods for linear constraints: convergence rates and conditioning. Math. Oper. Res. 35, 641\u2013654 (2010)","journal-title":"Math. Oper. Res."},{"key":"514_CR12","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0024-3795(93)90125-8","volume":"187","author":"W Li","year":"1993","unstructured":"Li, W.: The sharp Lipschitz constants for feasible and optimal solutions of a perturbed linear program. Linear Algebra Appl. 187, 15\u201340 (1993)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"514_CR13","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF02096261","volume":"46","author":"Z Luo","year":"1993","unstructured":"Luo, Z., Tseng, P.: Error bounds and convergence analysis of feasible descent methods: a general approach. Ann. Oper. Res. 46(1), 157\u2013178 (1993)","journal-title":"Ann. Oper. Res."},{"issue":"3","key":"514_CR14","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1137\/0325033","volume":"25","author":"O Mangasarian","year":"1987","unstructured":"Mangasarian, O., Shiau, T.-H.: Lipschitz continuity of solutions of linear inequalities, programs and complementarity problems. SIAM J. Control. Optim. 25(3), 583\u2013595 (1987)","journal-title":"SIAM J. Control. Optim."},{"key":"514_CR15","unstructured":"Pe\u00f1a, J., Vera, J., Zuluaga, L.: Equivalence and invariance of the chi and Hoffman constants of a matrix. arXiv preprint arXiv:1905.06366 (2019)"},{"issue":"1","key":"514_CR16","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s10107-020-01473-6","volume":"187","author":"J Pe\u00f1a","year":"2021","unstructured":"Pe\u00f1a, J., Vera, J., Zuluaga, L.: New characterizations of Hoffman constants for systems of linear constraints. Math. Program. 187(1), 79\u2013109 (2021)","journal-title":"Math. Program."},{"key":"514_CR17","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1090\/S0002-9947-1972-0313769-9","volume":"174","author":"S Robinson","year":"1972","unstructured":"Robinson, S.: Normed convex processes. Trans. Am. Math. Soc. 174, 127\u2013140 (1972)","journal-title":"Trans. Am. Math. Soc."},{"key":"514_CR18","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/0024-3795(73)90007-4","volume":"6","author":"S Robinson","year":"1973","unstructured":"Robinson, S.: Bounds for error in the solution set of a perturbed linear program. Linear Algebra Appl. 6, 69\u201381 (1973)","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"514_CR19","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1287\/moor.1.2.130","volume":"1","author":"S Robinson","year":"1976","unstructured":"Robinson, S.: Regularity and stability for convex multivalued functions. Math. Oper. Res. 1(2), 130\u2013143 (1976)","journal-title":"Math. Oper. Res."},{"key":"514_CR20","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0024-3795(89)90594-6","volume":"112","author":"G Stewart","year":"1989","unstructured":"Stewart, G.: On scaled projections and pseudoinverses. Linear Algebra Appl. 112, 189\u2013193 (1989)","journal-title":"Linear Algebra Appl."},{"issue":"6","key":"514_CR21","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1287\/opre.38.6.1006","volume":"38","author":"M Todd","year":"1990","unstructured":"Todd, M.: A Dantzig-Wolfe-like variant of Karmarkar\u2019s interior-point linear programming algorithm. Oper. Res. 38(6), 1006\u20131018 (1990)","journal-title":"Oper. Res."},{"issue":"3","key":"514_CR22","doi-asserted-by":"publisher","first-page":"438","DOI":"10.21136\/CMJ.1975.101337","volume":"25","author":"C Ursescu","year":"1975","unstructured":"Ursescu, C.: Multifunctions with convex closed graph. Czechoslov. Math. J. 25(3), 438\u2013441 (1975)","journal-title":"Czechoslov. Math. J."},{"issue":"1","key":"514_CR23","first-page":"1523","volume":"15","author":"P Wang","year":"2014","unstructured":"Wang, P., Lin, C.: Iteration complexity of feasible descent methods for convex optimization. J. Mach. Learn. Res. 15(1), 1523\u20131548 (2014)","journal-title":"J. Mach. Learn. Res."},{"issue":"2","key":"514_CR24","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1137\/S1052623402403505","volume":"14","author":"C Zalinescu","year":"2003","unstructured":"Zalinescu, C.: Sharp estimates for Hoffman\u2019s constant for systems of linear inequalities and equalities. SIAM J. Optim. 14(2), 517\u2013533 (2003)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"514_CR25","doi-asserted-by":"publisher","first-page":"391","DOI":"10.1007\/s10898-004-7020-x","volume":"30","author":"X Zheng","year":"2004","unstructured":"Zheng, X., Ng, K.: Hoffman\u2019s least error bounds for systems of linear inequalities. J. Global Optim. 30(4), 391\u2013403 (2004)","journal-title":"J. Global Optim."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00514-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-023-00514-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00514-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,4]],"date-time":"2024-01-04T12:05:27Z","timestamp":1704369927000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-023-00514-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,9]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["514"],"URL":"https:\/\/doi.org\/10.1007\/s10589-023-00514-y","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2023,8,9]]},"assertion":[{"value":"7 February 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 July 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}