{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T16:17:27Z","timestamp":1774973847332,"version":"3.50.1"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T00:00:00Z","timestamp":1604880000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T00:00:00Z","timestamp":1604880000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000848","name":"University of Edinburgh","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000848","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":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we combine an infeasible Interior Point Method (IPM) with the Proximal Method of Multipliers (PMM). The resulting algorithm (IP-PMM) is interpreted as a primal-dual regularized IPM, suitable for solving linearly constrained convex quadratic programming problems. We apply few iterations of the interior point method to each sub-problem of the proximal method of multipliers. Once a satisfactory solution of the PMM sub-problem is found, we update the PMM parameters, form a new IPM neighbourhood and repeat this process. Given this framework, we prove polynomial complexity of the algorithm, under standard assumptions. To our knowledge, this is the first polynomial complexity result for a primal-dual regularized IPM. The algorithm is guided by the use of a single penalty parameter; that of the logarithmic barrier. In other words, we show that IP-PMM inherits the polynomial complexity of IPMs, as well as the strict convexity of the PMM sub-problems. The updates of the penalty parameter are controlled by IPM, and hence are well-tuned, and do not depend on the problem solved. Furthermore, we study the behavior of the method when it is applied to an infeasible problem, and identify a necessary condition for infeasibility. The latter is used to construct an infeasibility detection mechanism. Subsequently, we provide a robust implementation of the presented algorithm and test it over a set of small to large scale linear and convex quadratic programming problems. The numerical results demonstrate the benefits of using regularization in IPMs as well as the reliability of the method.<\/jats:p>","DOI":"10.1007\/s10589-020-00240-9","type":"journal-article","created":{"date-parts":[[2020,11,9]],"date-time":"2020-11-09T18:04:52Z","timestamp":1604945092000},"page":"307-351","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["An interior point-proximal method of multipliers for convex quadratic programming"],"prefix":"10.1007","volume":"78","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7903-9335","authenticated-orcid":false,"given":"Spyridon","family":"Pougkakiotis","sequence":"first","affiliation":[]},{"given":"Jacek","family":"Gondzio","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,11,9]]},"reference":[{"key":"240_CR1","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1080\/10556789908805754","volume":"11 & 12","author":"A Altman","year":"1999","unstructured":"Altman, A., Gondzio, J.: Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization. Optim. Meth. Soft. 11 & 12, 275\u2013302 (1999)","journal-title":"Optim. Meth. Soft."},{"issue":"1&2","key":"240_CR2","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/s10107-011-0498-3","volume":"137","author":"P Armand","year":"2013","unstructured":"Armand, P., Benoist, J.: Uniform boundedness of the inverse of a Jacobian matrix arising in regularized interior-point methods. Math. Prog. 137(1&2), 587\u2013592 (2013)","journal-title":"Math. Prog."},{"key":"240_CR3","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/s10957-017-1071-x","volume":"173","author":"P Armand","year":"2017","unstructured":"Armand, P., Omheni, R.: A mixed logarithmic barrier-augmented Lagrangian method for nonlinear optimization. J. Optim. Theory and Appl. 173, 523\u2013547 (2017)","journal-title":"J. Optim. Theory and Appl."},{"issue":"5","key":"240_CR4","doi-asserted-by":"publisher","first-page":"991","DOI":"10.1080\/10556788.2018.1528250","volume":"34","author":"P Armand","year":"2019","unstructured":"Armand, P., Tran, N.N.: Rapid infeasibility detection in a mixed logarithmic barrier-augmented Lagrangian method for nonlinear optimization. Optim. Meth. Soft. 34(5), 991\u20131013 (2019)","journal-title":"Optim. Meth. Soft."},{"issue":"2","key":"240_CR5","doi-asserted-by":"publisher","first-page":"1613","DOI":"10.1137\/16M1088570","volume":"28","author":"S Arreckx","year":"2018","unstructured":"Arreckx, S., Orban, D.: A regularized factorization-free method for equality-constrained optimization. SIAM J. Optim. 28(2), 1613\u20131639 (2018)","journal-title":"SIAM J. Optim."},{"key":"240_CR6","unstructured":"Bertsekas, P.D.: Constrained Optimization and Lagrange Multiplier Methods. Athena Scientific (1996)"},{"key":"240_CR7","unstructured":"Bertsekas, P.D., Nedic, A., Ozdaglar, E.: Convex Analysis and Optimization. Athena Scientific (2003)"},{"key":"240_CR8","unstructured":"Bertsekas, P.D., Tsitsiklis, N.J.: Parallel and Distributed Computation: Numerical Methods. Athena Scientific (1997)"},{"issue":"3","key":"240_CR9","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/BF00940051","volume":"73","author":"Y Censor","year":"1992","unstructured":"Censor, Y., Zenios, A.: Proximal minimization algorithm with D-functions. J. Optim. Theory Appl. 73(3), 451\u2013464 (1992)","journal-title":"J. Optim. Theory Appl."},{"key":"240_CR10","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"DE Dolan","year":"2002","unstructured":"Dolan, D.E., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Math. Prog. Ser. A. 91, 201\u2013213 (2002)","journal-title":"Math. Prog. Ser. A."},{"key":"240_CR11","doi-asserted-by":"crossref","unstructured":"Eckstein, J.: nonlinear proximal point algorithms using Bregman functions, with applications to convex programming. Math. Oper. Res. 18(1) (1993)","DOI":"10.1287\/moor.18.1.202"},{"issue":"1","key":"240_CR12","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s12532-012-0035-2","volume":"4","author":"MP Friedlander","year":"2012","unstructured":"Friedlander, M.P., Orban, D.: A primal-dual regularized interior-point method for convex quadratic programs. Math. Prog. Comput. 4(1), 71\u2013107 (2012)","journal-title":"Math. Prog. Comput."},{"issue":"4","key":"240_CR13","doi-asserted-by":"publisher","first-page":"649","DOI":"10.1137\/0802032","volume":"2","author":"O G\u00fcler","year":"1992","unstructured":"G\u00fcler, O.: New proximal point algorithms for convex minimization. SIAM J. Optim. 2(4), 649\u2013664 (1992)","journal-title":"SIAM J. Optim."},{"key":"240_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10589-010-9339-1","volume":"51","author":"EP Gill","year":"2012","unstructured":"Gill, E.P., Robinson, P.D.: A primal-dual augmented Lagrangian. Comput. Optim. Appl. 51, 1\u201325 (2012)","journal-title":"Comput. Optim. Appl."},{"key":"240_CR15","unstructured":"GLPK. https:\/\/www.gnu.org\/software\/glpk\/ (2018)"},{"key":"240_CR16","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1007\/BF00249643","volume":"6","author":"J Gondzio","year":"1996","unstructured":"Gondzio, J.: Multiple centrality corrections in a primal-dual method for linear programming. Comput. Optim. Appl. 6, 137\u2013156 (1996)","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"240_CR17","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1016\/j.ejor.2011.09.017","volume":"218","author":"J Gondzio","year":"2013","unstructured":"Gondzio, J.: Interior point methods 25 years later. Eur. J. Oper. Res. 218(3), 587\u2013601 (2013)","journal-title":"Eur. J. Oper. Res."},{"key":"240_CR18","doi-asserted-by":"crossref","unstructured":"Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. (4), 303\u2013320 (1969)","DOI":"10.1007\/BF00927673"},{"issue":"3","key":"240_CR19","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/BF02193058","volume":"85","author":"AN Iusem","year":"1995","unstructured":"Iusem, A.N.: Some properties of generalized proximal point methods for quadratic and linear programming. J. Optim. Theory Appl. 85(3), 593\u2013612 (1995)","journal-title":"J. Optim. Theory Appl."},{"key":"240_CR20","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/BF01582151","volume":"61","author":"M Kojima","year":"1993","unstructured":"Kojima, M., Megiddo, N., Mizuno, S.: A primal-dual infeasible-interior-point algorithm for linear programming. Math. Prog. 61, 263\u2013280 (1993)","journal-title":"Math. Prog."},{"issue":"1\u20132","key":"240_CR21","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s10107-015-0861-x","volume":"155","author":"G Lan","year":"2016","unstructured":"Lan, G., Monteiro, R.D.C.: Iteration-complexity of first-order augmented Lagrangian methods for convex programming. Math. Prog. 155(1\u20132), 511\u2013547 (2016)","journal-title":"Math. Prog."},{"key":"240_CR22","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1080\/10556789908805768","volume":"11 & 12","author":"I Maros","year":"1999","unstructured":"Maros, I., M\u00e9sz\u00e1ros, C.: A repository of convex quadratic programming problems. Optim. Meth. Soft. 11 & 12, 671\u2013681 (1999)","journal-title":"Optim. Meth. Soft."},{"issue":"4","key":"240_CR23","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1137\/0802028","volume":"2","author":"S Mehrotra","year":"1992","unstructured":"Mehrotra, S.: On the implementation of a primal-dual interior-point method. SIAM J. Optim. 2(4), 575\u2013601 (1992)","journal-title":"SIAM J. Optim."},{"key":"240_CR24","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/s10107980020a","volume":"84","author":"S Mizuno","year":"1999","unstructured":"Mizuno, S., Jarre, F.: Global and polynomial-time convergence of an infeasible-interior-point algorithm using inexact computation. Math. Prog. 84, 105\u2013122 (1999)","journal-title":"Math. Prog."},{"key":"240_CR25","doi-asserted-by":"crossref","unstructured":"Nesterov, Y., Nemirovski, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM (1993)","DOI":"10.1137\/1.9781611970791"},{"issue":"2","key":"240_CR26","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s10107980009a","volume":"82","author":"Y Nesterov","year":"1999","unstructured":"Nesterov, Y., Todd, M.J., Ye, Y.: Infeasible-start primal-dual methods and infeasibility detectors for nonlinear programming problems. Math. Prog. 82(2), 227\u2013267 (1999)","journal-title":"Math. Prog."},{"key":"240_CR27","unstructured":"Netlib. http:\/\/netlib.org\/lp (2011)"},{"issue":"1","key":"240_CR28","first-page":"123","volume":"3","author":"N Parikh","year":"2014","unstructured":"Parikh, N., Boyd, S.: Proximal algorithms. Found. Trends Optim. 3(1), 123\u2013231 (2014)","journal-title":"Found. Trends Optim."},{"issue":"3","key":"240_CR29","doi-asserted-by":"publisher","first-page":"905","DOI":"10.1007\/s10957-019-01491-1","volume":"181","author":"S Pougkakiotis","year":"2019","unstructured":"Pougkakiotis, S., Gondzio, J.: Dynamic non-diagonal regularization in interior point methods for linear and convex quadratic programming. J. Optim. Theory Appl. 181(3), 905\u2013945 (2019)","journal-title":"J. Optim. Theory Appl."},{"key":"240_CR30","unstructured":"Powell, M.J.D.: A method for nonlinear constraints in minimization problems. Optimization (4), 283\u2013298 (1969)"},{"issue":"2","key":"240_CR31","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1287\/moor.1.2.97","volume":"1","author":"RT Rockafellar","year":"1976","unstructured":"Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97\u2013116 (1976)","journal-title":"Math. Oper. Res."},{"key":"240_CR32","doi-asserted-by":"crossref","unstructured":"Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5) (1976)","DOI":"10.1137\/0314056"},{"key":"240_CR33","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press (1996)"},{"issue":"1","key":"240_CR34","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1137\/0805005","volume":"5","author":"R Vanderbei","year":"1995","unstructured":"Vanderbei, R.: Symmetric quasidefinite matrices. SIAM J. Optim. 5(1), 100\u2013113 (1995)","journal-title":"SIAM J. Optim."},{"issue":"3\u20134","key":"240_CR35","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1080\/01630560701277930","volume":"28","author":"Y Wang","year":"2007","unstructured":"Wang, Y., Fei, P.: An infeasible Mizuno-Todd-Ye type algorithm for convex quadratic programming with polynomial complexity. Numer. Funct. Anal. Optim. 28(3\u20134), 487\u2013502 (2007)","journal-title":"Numer. Funct. Anal. Optim."},{"key":"240_CR36","doi-asserted-by":"crossref","unstructured":"Wright, S.J.: Primal-Dual Interior Point Methods. SIAM (1997)","DOI":"10.1137\/1.9781611971453"},{"issue":"1","key":"240_CR37","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1137\/0804012","volume":"4","author":"Y Zhang","year":"1994","unstructured":"Zhang, Y.: On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM J. Optim. 4(1), 208\u2013227 (1994)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"240_CR38","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1023\/B:COAP.0000013059.84424.af","volume":"27","author":"G Zhou","year":"2004","unstructured":"Zhou, G., Toh, K.C., Zhao, G.: Convergence analysis of an infeasible interior point algorithm based on a regularized central path for linear complementarity problems. Comput. Optim. Appl. 27(3), 269\u2013283 (2004)","journal-title":"Comput. Optim. Appl."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-020-00240-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-020-00240-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-020-00240-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,11]],"date-time":"2021-02-11T19:08:55Z","timestamp":1613070535000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-020-00240-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,11,9]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["240"],"URL":"https:\/\/doi.org\/10.1007\/s10589-020-00240-9","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,11,9]]},"assertion":[{"value":"28 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 November 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}