{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:35:31Z","timestamp":1787340931568,"version":"3.56.0"},"reference-count":65,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2024,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We study the problem of detecting infeasibility of large-scale linear programming problems using the primal-dual hybrid gradient (PDHG) method of Chambolle and Pock [ J. Math. Imaging Vision, 40 (2011), pp. 120\u2013145]. The literature on PDHG has focused chiefly on problems with at least one optimal solution. We show that when the problem is infeasible or unbounded, the iterates diverge at a controlled rate toward a well-defined ray. In turn, the direction of such a ray recovers infeasibility certificates. Based on this fact, we propose a simple way to extract approximate infeasibility certificates from the iterates of PDHG. We study three sequences that converge to certificates: the difference of iterates, the normalized iterates, and the normalized average. All of them are easy to compute and suitable for large-scale problems. We show that the normalized iterates and normalized averages achieve a convergence rate of [Formula: see text]. This rate is general and applies to any fixed-point iteration of a nonexpansive operator. Thus, it is a result of independent interest that goes well beyond our setting. Finally, we show that, under nondegeneracy assumptions, the iterates of PDHG identify the active set of an auxiliary feasible problem in finite time, which ensures that the difference of iterates exhibits eventual linear convergence. These results provide a theoretical justification for infeasibility detection in the newly developed linear programming solver PDLP.<\/jats:p>","DOI":"10.1137\/22m1510467","type":"journal-article","created":{"date-parts":[[2024,1,31]],"date-time":"2024-01-31T04:39:43Z","timestamp":1706675983000},"page":"459-484","source":"Crossref","is-referenced-by-count":9,"title":["Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming"],"prefix":"10.1137","volume":"34","author":[{"given":"David","family":"Applegate","sequence":"first","affiliation":[{"name":"Google Research."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mateo","family":"D\u00edaz","sequence":"additional","affiliation":[{"name":"Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, MD 21218 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haihao","family":"Lu","sequence":"additional","affiliation":[{"name":"Booth School of Business, University of Chicago, Chicago, IL 60637 USA, and Google Research."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Miles","family":"Lubin","sequence":"additional","affiliation":[{"name":"Google Research."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,1,31]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2006.10.006"},{"key":"ref2","volume-title":"Advances in Neural Information Processing Systems","volume":"34","author":"Applegate D.","year":"2021"},{"key":"ref3","unstructured":"D. Applegate, M. D\u00edaz, H. Lu, and M. Lubin, Infeasibility Detection with Primal-Dual Hybrid Gradient for Large-Scale Linear Programming, preprint, arXiv:2102.04592, 2021."},{"key":"ref4","first-page":"1","volume":"4","author":"Bailion J.","year":"1978","journal-title":"Houston J. Math."},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2021.01.003"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-019-01575-y"},{"key":"ref7","unstructured":"K. Basu, A. Ghoting, R. Mazumder, and Y. Pan, ECLIPSE: An extreme-scale linear program solver for web-applications, in Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research 119, H. D. Virtual, III, and A. Singh, eds. PMLR, 2020, pp. 704\u2013714."},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48311-5"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.jat.2004.02.006"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1137\/15M1016989"},{"key":"ref11","unstructured":"H. H. Bauschke and W. M. Moursi, On the Douglas-Rachford Algorithm for Solving Possibly Inconsistent Optimization Problems, preprint, arXiv:2106.11547, 2021."},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-31256-9"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1137\/0727064"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/0725068"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1137\/0804032"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592073"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-010-0251-1"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1017\/S096249291600009X"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1996.6"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1515\/9781400884179"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41589-5_4"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1956-0084194-4"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0730-4"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1007\/BF00939081"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581204"},{"key":"ref26","unstructured":"J. Eckstein and G. Matyasfalvi, Efficient Distributed-Memory Parallel Matrix-Vector Multiplication with Wide or Tall Unstructured Sparse Matrices, preprint, arXiv:1812.00904, 2018."},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/BF01594944"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581092"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0898-1221(76)90003-1"},{"key":"ref30","unstructured":"D. M. Gay, Netlib: Infeasible Linear Programming Test Problems, 2013, http:\/\/netlib.org\/lp\/infeas\/index.html."},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0430-2"},{"key":"ref32","first-page":"41","volume":"9","author":"Glowinski R.","year":"1975","journal-title":"ESAIM Math. Model. Numer. Anal.-Mod\u00e9lisation Math\u00e9matique et Analyse Num\u00e9rique"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1137\/140963467"},{"key":"ref34","unstructured":"J. Lamperski, R. M. Freund, and M. J. Todd, An Oblivious Ellipsoid Algorithm for Solving a System of (In)feasible Linear Inequalities, preprint, arXiv:1910.03114, 2020."},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-008-0261-6"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623401387623"},{"key":"ref37","unstructured":"A. S. Lewis and J. Liang, Partial Smoothness and Constant Rank, preprint, arXiv:1807.03134, 2018."},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-017-1061-z"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1080\/02331934.2018.1426584"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1137\/0716071"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1265-5"},{"key":"ref42","unstructured":"Y. Malitsky, The Primal-Dual Hybrid Gradient Method Reduces to a Primal Method for Linearly Constrained Optimization Problems, preprint, arXiv:1706.02602, 2019."},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-0257-9"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4975-8"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623402412441"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1080\/10556780410001704902"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-005-0630-3"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-019-01524-9"},{"key":"ref49","unstructured":"W. M. Moursi, The Douglas\u2013Rachford Operator in the Possibly Inconsistent Case: Static Properties and Dynamic Behaviour, Ph.D. thesis, University of British Columbia, 2016."},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0686-4"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1321-1"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1137\/20M1366307"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-016-0892-3"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-018-1321-1"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1007\/BF02771588"},{"key":"ref56","doi-asserted-by":"crossref","unstructured":"T. Pock and A. Chambolle, Diagonal preconditioning for first order primal-dual algorithms in convex optimization, in 2011 International Conference on Computer Vision, IEEE, New York, 2011, pp. 1762\u20131769, https:\/\/doi.org\/10.1109\/ICCV.2011.6126441.","DOI":"10.1109\/ICCV.2011.6126441"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588967"},{"key":"ref58","doi-asserted-by":"crossref","unstructured":"A. U. Raghunathan and S. Di Cairano, Infeasibility detection in alternating direction method of multipliers for convex quadratic programs, in 53rd IEEE Conference on Decision and Control, IEEE, New York, 2014, pp. 5819\u20135824.","DOI":"10.1109\/CDC.2014.7040300"},{"key":"ref59","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1203-y"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1515\/9781400873173"},{"key":"ref61","first-page":"27","volume":"293","author":"Shi S.-C.","year":"1981","journal-title":"C. R. Acad. Sci. Paris (Ser. A)"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-020-00179-2"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139106962.008"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-50743-5_16"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1137\/0331048"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1510467","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:56:38Z","timestamp":1787338598000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1510467"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,31]]},"references-count":65,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,31]]}},"alternative-id":["10.1137\/22M1510467"],"URL":"https:\/\/doi.org\/10.1137\/22m1510467","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,31]]}}}