{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,17]],"date-time":"2025-05-17T12:44:43Z","timestamp":1747485883299,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T00:00:00Z","timestamp":1686873600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T00:00:00Z","timestamp":1686873600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004270","name":"Royal Institute of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004270","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":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The focus in this work is on interior-point methods for inequality-constrained quadratic programs, and particularly on the system of nonlinear equations to be solved for each value of the barrier parameter. Newton iterations give high quality solutions, but we are interested in modified Newton systems that are computationally less expensive at the expense of lower quality solutions. We propose a structured modified Newton approach where each modified Jacobian is composed of a previous Jacobian, plus one low-rank update matrix per succeeding iteration. Each update matrix is, for a given rank, chosen such that the distance to the Jacobian at the current iterate is minimized, in both 2-norm and Frobenius norm. The approach is structured in the sense that it preserves the nonzero pattern of the Jacobian. The choice of update matrix is supported by results in an ideal theoretical setting. We also produce numerical results with a basic interior-point implementation to investigate the practical performance within and beyond the theoretical framework. In order to improve performance beyond the theoretical framework, we also motivate and construct two heuristics to be added to the method.<\/jats:p>","DOI":"10.1007\/s10589-023-00486-z","type":"journal-article","created":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T13:02:32Z","timestamp":1686920552000},"page":"1-48","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["A structured modified Newton approach for solving systems of nonlinear equations arising in interior-point methods for quadratic programming"],"prefix":"10.1007","volume":"86","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1764-5449","authenticated-orcid":false,"given":"David","family":"Ek","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6252-7815","authenticated-orcid":false,"given":"Anders","family":"Forsgren","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,6,16]]},"reference":[{"issue":"1","key":"486_CR1","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1137\/120890600","volume":"24","author":"C Greif","year":"2014","unstructured":"Greif, C., Moulding, E., Orban, D.: Bounds on eigenvalues of matrices arising from interior-point methods. SIAM J. Optim. 24(1), 49\u201383 (2014). https:\/\/doi.org\/10.1137\/120890600","journal-title":"SIAM J. Optim."},{"issue":"5","key":"486_CR2","doi-asserted-by":"publisher","first-page":"776","DOI":"10.1002\/nla.2054","volume":"23","author":"B Morini","year":"2016","unstructured":"Morini, B., Simoncini, V., Tani, M.: Spectral estimates for unreduced symmetric KKT systems arising from interior point methods. Numer. Linear Algebra Appl. 23(5), 776\u2013800 (2016). https:\/\/doi.org\/10.1002\/nla.2054","journal-title":"Numer. Linear Algebra Appl."},{"issue":"2","key":"486_CR3","doi-asserted-by":"publisher","first-page":"666","DOI":"10.1137\/060650210","volume":"18","author":"A Forsgren","year":"2007","unstructured":"Forsgren, A., Gill, P.E., Griffin, J.D.: Iterative solution of augmented systems arising in interior methods. SIAM J. Optim. 18(2), 666\u2013690 (2007)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"486_CR4","doi-asserted-by":"publisher","first-page":"525","DOI":"10.1137\/S0036144502414942","volume":"44","author":"A Forsgren","year":"2002","unstructured":"Forsgren, A., Gill, P.E., Wright, M.H.: Interior methods for nonlinear optimization. SIAM Rev. 44(4), 525\u20135972003 (2002). https:\/\/doi.org\/10.1137\/S0036144502414942","journal-title":"SIAM Rev."},{"key":"486_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10589-017-9907-8","volume":"68","author":"B Morini","year":"2017","unstructured":"Morini, B., Simoncini, V., Tani, M.: A comparison of reduced and unreduced KKT systems arising from interior point methods. Comput. Optim. Appl. 68, 1\u201327 (2017)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"486_CR6","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s10589-019-00102-z","volume":"74","author":"J Gondzio","year":"2019","unstructured":"Gondzio, J., Sobral, F.N.C.: Quasi-Newton approaches to interior point methods for quadratic problems. Comput. Optim. Appl. 74(1), 93\u2013120 (2019). https:\/\/doi.org\/10.1007\/s10589-019-00102-z","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"486_CR7","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1137\/S1052623498347438","volume":"12","author":"SJ Wright","year":"2001","unstructured":"Wright, S.J.: Effects of finite-precision arithmetic on interior-point methods for nonlinear programming. SIAM J. Optim. 12(1), 36\u201378 (2001). https:\/\/doi.org\/10.1137\/S1052623498347438","journal-title":"SIAM J. Optim."},{"issue":"1","key":"486_CR8","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1137\/S1052623497322279","volume":"9","author":"MH Wright","year":"1999","unstructured":"Wright, M.H.: Ill-conditioning and computational error in interior methods for nonlinear programming. SIAM J. Optim. 9(1), 84\u2013111 (1999). https:\/\/doi.org\/10.1137\/S1052623497322279","journal-title":"SIAM J. Optim."},{"issue":"1","key":"486_CR9","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/S0895479894271093","volume":"18","author":"S Wright","year":"1997","unstructured":"Wright, S.: Stability of augmented system factorizations in interior-point methods. SIAM J. Matrix Anal. Appl. 18(1), 191\u2013222 (1997). https:\/\/doi.org\/10.1137\/S0895479894271093","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"4","key":"486_CR10","doi-asserted-by":"publisher","first-page":"1287","DOI":"10.1137\/S0895479893260498","volume":"16","author":"SJ Wright","year":"1995","unstructured":"Wright, S.J.: Stability of linear equations solvers in interior-point methods. SIAM J. Matrix Anal. Appl. 16(4), 1287\u20131307 (1995). https:\/\/doi.org\/10.1137\/S0895479893260498","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"1","key":"486_CR11","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1137\/S0895479894270658","volume":"17","author":"A Forsgren","year":"1996","unstructured":"Forsgren, A., Gill, P.E., Shinnerl, J.R.: Stability of symmetric ill-conditioned systems arising in interior methods for constrained optimization. SIAM J. Matrix Anal. Appl. 17(1), 187\u2013211 (1996). https:\/\/doi.org\/10.1137\/S0895479894270658","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"2","key":"486_CR12","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/s10589-008-9226-1","volume":"45","author":"M D\u2019Apuzzo","year":"2010","unstructured":"D\u2019Apuzzo, M., De Simone, V., di Serafino, D.: On mutual impact of numerical linear algebra and large-scale optimization with focus on interior point methods. Comput. Optim. Appl. 45(2), 283\u2013310 (2010). https:\/\/doi.org\/10.1007\/s10589-008-9226-1","journal-title":"Comput. Optim. Appl."},{"issue":"2","key":"486_CR13","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1007\/s10957-017-1170-8","volume":"175","author":"B Morini","year":"2017","unstructured":"Morini, B., Simoncini, V.: Stability and accuracy of inexact interior point methods for convex quadratic programming. J. Optim. Theory Appl. 175(2), 450\u2013477 (2017). https:\/\/doi.org\/10.1007\/s10957-017-1170-8","journal-title":"J. Optim. Theory Appl."},{"key":"486_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-1-4613-9617-8_1","volume-title":"Progress in Mathematical Programming: Interior-Point and Related Methods","author":"CC Gonzaga","year":"1989","unstructured":"Gonzaga, C.C.: An algorithm for solving linear programming problems in $$O(n^3L)$$ operations. In: Megiddo, N. (ed.) Progress in Mathematical Programming: Interior-Point and Related Methods, pp. 1\u201328. Springer, New York (1989). https:\/\/doi.org\/10.1007\/978-1-4613-9617-8_1"},{"issue":"1","key":"486_CR15","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\u2013dual regularized interior-point method for convex quadratic programs. Math. Program. Comput. 4(1), 71\u2013107 (2012). https:\/\/doi.org\/10.1007\/s12532-012-0035-2","journal-title":"Math. Program. Comput."},{"issue":"1\u20134","key":"486_CR16","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. Methods Softw. 11\/12(1\u20134), 275\u2013302 (1999). https:\/\/doi.org\/10.1080\/10556789908805754","journal-title":"Optim. Methods Softw."},{"key":"486_CR17","unstructured":"Saunders, M., Tomlin, J.: Solving regularized linear programs using barrier methods and KKT systems. SOL Report 96-4, Systems Optimization Laboratory, Dept. of Operations Research, Stanford University, Stanford, CA94306, USA (1996)"},{"issue":"1\u20134","key":"486_CR18","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. Methods Softw. 11\/12(1\u20134), 671\u2013681 (1999). https:\/\/doi.org\/10.1080\/10556789908805768","journal-title":"Optim. Methods Softw."},{"issue":"1","key":"486_CR19","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1007\/s10589-021-00265-8","volume":"79","author":"D Ek","year":"2021","unstructured":"Ek, D., Forsgren, A.: Approximate solution of system of equations arising in interior-point methods for bound-constrained optimization. Comput. Optim. Appl. 79(1), 155\u2013191 (2021). https:\/\/doi.org\/10.1007\/s10589-021-00265-8","journal-title":"Comput. Optim. Appl."},{"key":"486_CR20","doi-asserted-by":"crossref","unstructured":"Griva, I., Nash, S., Sofer, A.: Linear and Nonlinear Optimization: Second Edition, p. 742. Society for Industrial and Applied Mathematics (2009)","DOI":"10.1137\/1.9780898717730"},{"key":"486_CR21","first-page":"664","volume-title":"Numerical Optimization. Springer Series in Operations Research and Financial Engineering","author":"J Nocedal","year":"2006","unstructured":"Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research and Financial Engineering, 2nd edn., p. 664. Springer, New York (2006)","edition":"2"},{"key":"486_CR22","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719468","volume-title":"Iterative Solution of Nonlinear Equations in Several Variables","author":"JM Ortega","year":"2000","unstructured":"Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Society for Industrial and Applied Mathematics, Philadelphia (2000)"},{"key":"486_CR23","unstructured":"Byrd, R.H., Liu, G., Nocedal, J.: On the local behavior of an interior point method for nonlinear programming. In: Numerical Analysis 1997, pp. 37\u201356. Addison Wesley Longman (1998)"},{"issue":"2","key":"486_CR24","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1137\/0719025","volume":"19","author":"RS Dembo","year":"1982","unstructured":"Dembo, R.S., Eisenstat, S.C., Steihaug, T.: Inexact Newton methods. SIAM J. Numer. Anal. 19(2), 400\u2013408 (1982). https:\/\/doi.org\/10.1137\/0719025","journal-title":"SIAM J. Numer. Anal."},{"issue":"1","key":"486_CR25","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1023\/A:1022663100715","volume":"96","author":"S Bellavia","year":"1998","unstructured":"Bellavia, S.: Inexact interior-point method. J. Optim. Theory Appl. 96(1), 109\u2013121 (1998). https:\/\/doi.org\/10.1023\/A:1022663100715","journal-title":"J. Optim. Theory Appl."},{"issue":"1","key":"486_CR26","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s10589-011-9406-2","volume":"52","author":"P Armand","year":"2012","unstructured":"Armand, P., Benoist, J., Dussault, J.-P.: Local path-following property of inexact interior methods in nonlinear programming. Comput. Optim. Appl. 52(1), 209\u2013238 (2012). https:\/\/doi.org\/10.1007\/s10589-011-9406-2","journal-title":"Comput. Optim. Appl."},{"issue":"3","key":"486_CR27","doi-asserted-by":"publisher","first-page":"1510","DOI":"10.1137\/120886017","volume":"23","author":"J Gondzio","year":"2013","unstructured":"Gondzio, J.: Convergence analysis of an inexact feasible interior point method for convex quadratic programming. SIAM J. Optim. 23(3), 1510\u20131527 (2013). https:\/\/doi.org\/10.1137\/120886017","journal-title":"SIAM J. Optim."},{"issue":"89","key":"486_CR28","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0024-3795(87)90112-1","volume":"88","author":"PE Gill","year":"1987","unstructured":"Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: Maintaining $$LU$$ factors of a general sparse matrix. Linear Algebra Appl. 88(89), 239\u2013270 (1987). https:\/\/doi.org\/10.1016\/0024-3795(87)90112-1","journal-title":"Linear Algebra Appl."},{"key":"486_CR29","unstructured":"Deng, L.: Multiple-Rank Updates to Matrix Factorizations for Nonlinear Analysis and Circuit Design, p. 128. ProQuest LLC, Ann Arbor, MI (2010). Thesis (Ph.D.), Stanford University. http:\/\/gateway.proquest.com\/openurl?url_ver=Z39.88-2004 &rft_val_fmt=info:ofi\/fmt:kev:mtx:dissertation &res_dat=xri:pqm &rft_dat=xri:pqdiss:28168946"},{"key":"486_CR30","first-page":"161","volume":"26","author":"P Stange","year":"2007","unstructured":"Stange, P., Griewank, A., Bollh\u00f6fer, M.: On the efficient update of rectangular LU-factorizations subject to low rank modifications. Electron. Trans. Numer. Anal. 26, 161\u2013177 (2007)","journal-title":"Electron. Trans. Numer. Anal."},{"key":"486_CR31","doi-asserted-by":"publisher","first-page":"505","DOI":"10.2307\/2005923","volume":"28","author":"PE Gill","year":"1974","unstructured":"Gill, P.E., Golub, G.H., Murray, W., Saunders, M.A.: Methods for modifying matrix factorizations. Math. Comp. 28, 505\u2013535 (1974). https:\/\/doi.org\/10.2307\/2005923","journal-title":"Math. Comp."},{"key":"486_CR32","first-page":"756","volume-title":"Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences","author":"GH Golub","year":"2013","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix Computations. Johns Hopkins Studies in the Mathematical Sciences, 4th edn., p. 756. Johns Hopkins University Press, Baltimore (2013)","edition":"4"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00486-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-023-00486-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-023-00486-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,25]],"date-time":"2023-07-25T11:15:38Z","timestamp":1690283738000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-023-00486-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,16]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["486"],"URL":"https:\/\/doi.org\/10.1007\/s10589-023-00486-z","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2023,6,16]]},"assertion":[{"value":"1 April 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 June 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 authors have no competing interests to declare that are relevant to the content of this manuscript.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}