{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T11:47:48Z","timestamp":1776685668920,"version":"3.51.2"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T00:00:00Z","timestamp":1708387200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T00:00:00Z","timestamp":1708387200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"JSPS KAKENHI","award":["21K11767"],"award-info":[{"award-number":["21K11767"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>An arc-search interior-point method is a type of interior-point method that approximates the central path by an ellipsoidal arc, and it can often reduce the number of iterations. In this work, to further reduce the number of iterations and the computation time for solving linear programming problems, we propose two arc-search interior-point methods using Nesterov\u2019s restarting strategy which is a well-known method to accelerate the gradient method with a momentum term. The first one generates a sequence of iterations in the neighborhood, and we prove that the proposed method converges to an optimal solution and that it is a polynomial-time method. The second one incorporates the concept of the Mehrotra-type interior-point method to improve numerical performance. The numerical experiments demonstrate that the second one reduced the number of iterations and the computational time compared to existing interior-point methods due to the momentum term.\n<\/jats:p>","DOI":"10.1007\/s10589-024-00561-z","type":"journal-article","created":{"date-parts":[[2024,2,20]],"date-time":"2024-02-20T18:02:07Z","timestamp":1708452127000},"page":"643-676","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["An infeasible interior-point arc-search method with Nesterov\u2019s restarting strategy for linear programming problems"],"prefix":"10.1007","volume":"88","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-3504-4065","authenticated-orcid":false,"given":"Einosuke","family":"Iida","sequence":"first","affiliation":[]},{"given":"Makoto","family":"Yamashita","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,2,20]]},"reference":[{"key":"561_CR1","doi-asserted-by":"crossref","unstructured":"Karmarkar, N.: A new polynomial-time algorithm for linear programming. In: Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, pp. 302\u2013311 (1984)","DOI":"10.1145\/800057.808695"},{"key":"561_CR2","doi-asserted-by":"crossref","unstructured":"Kojima, M., Mizuno, S., Yoshise, A.: A primal-dual interior point algorithm for linear programming. In: Progress in Mathematical Programming, pp. 29\u201347. Springer, New York (1989)","DOI":"10.1007\/978-1-4613-9617-8_2"},{"key":"561_CR3","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, 575\u2013601 (1992). https:\/\/doi.org\/10.1137\/0802028","journal-title":"SIAM J. Optim."},{"key":"561_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971453","volume-title":"Primal-Dual Interior-Point Methods","author":"SJ Wright","year":"1997","unstructured":"Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Pittsburgh (1997)"},{"issue":"2","key":"561_CR5","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1287\/moor.15.2.191","volume":"15","author":"RD Monteiro","year":"1990","unstructured":"Monteiro, R.D., Adler, I., Resende, M.G.: A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension. Math. Oper. Res. 15(2), 191\u2013214 (1990)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"561_CR6","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(2), 137\u2013156 (1996)","journal-title":"Comput. Optim. Appl."},{"issue":"1\u20134","key":"561_CR7","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1080\/10556789908805754","volume":"11","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(1\u20134), 275\u2013302 (1999)","journal-title":"Optim. Methods Softw."},{"issue":"2","key":"561_CR8","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1007\/s10998-017-0231-y","volume":"76","author":"B Kheirfam","year":"2018","unstructured":"Kheirfam, B., Chitsaz, M.: Polynomial convergence of two higher order interior-point methods for $$p_*(\\kappa )$$-lcp in a wide neighborhood of the central path. Period. Math. Hung. 76(2), 243\u2013264 (2018)","journal-title":"Period. Math. Hung."},{"key":"561_CR9","doi-asserted-by":"publisher","DOI":"10.1016\/j.compchemeng.2021.107638","volume":"158","author":"TA Espaas","year":"2022","unstructured":"Espaas, T.A., Vassiliadis, V.S.: An interior point framework employing higher-order derivatives of central path-like trajectories: Application to convex quadratic programming. Comput. Chem. Eng. 158, 107638 (2022)","journal-title":"Comput. Chem. Eng."},{"issue":"3","key":"561_CR10","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1137\/0802022","volume":"2","author":"IJ Lustig","year":"1992","unstructured":"Lustig, I.J., Marsten, R.E., Shanno, D.F.: On implementing Mehrotra\u2019s predictor-corrector interior-point method for linear programming. SIAM J. Optim. 2(3), 435\u2013449 (1992)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"561_CR11","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1080\/1055678031000118482","volume":"18","author":"M Yamashita","year":"2003","unstructured":"Yamashita, M., Fujisawa, K., Kojima, M.: Implementation and evaluation of SDPA 6.0 (semidefinite programming algorithm 6.0). Optim. Methods Softw. 18(4), 491\u2013505 (2003)","journal-title":"Optim. Methods Softw."},{"key":"561_CR12","doi-asserted-by":"crossref","unstructured":"Yamashita, M., Fujisawa, K., Fukuda, M., Kobayashi, K., Nakata, K., Nakata, M.: Latest developments in the SDPA family for solving large-scale SDPs. In: Handbook on Semidefinite. Conic and Polynomial Optimization, pp. 687\u2013713. Springer, New York (2012)","DOI":"10.1007\/978-1-4614-0769-0_24"},{"issue":"1","key":"561_CR13","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.ejor.2011.06.020","volume":"215","author":"Y Yang","year":"2011","unstructured":"Yang, Y.: A polynomial arc-search interior-point algorithm for convex quadratic programming. Eur. J. Oper. Res. 215(1), 25\u201338 (2011)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"561_CR14","doi-asserted-by":"publisher","first-page":"781","DOI":"10.1007\/s11590-017-1142-9","volume":"12","author":"Y Yang","year":"2018","unstructured":"Yang, Y., Yamashita, M.: An arc-search $$O(nL)$$ infeasible-interior-point algorithm for linear programming. Optim. Lett. 12(4), 781\u2013798 (2018)","journal-title":"Optim. Lett."},{"key":"561_CR15","unstructured":"Yang, Y.: Constrained LQR design using interior-point arc-search method for convex quadratic programming with box constraints. arXiv preprint arXiv:1304.4685 (2013)"},{"issue":"1","key":"561_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/s11590-016-0997-5","volume":"11","author":"X Yang","year":"2017","unstructured":"Yang, X., Liu, H., Zhang, Y.: An arc-search infeasible-interior-point method for symmetric optimization in a wide neighborhood of the central path. Optim. Lett. 11(1), 135\u2013152 (2017)","journal-title":"Optim. Lett."},{"issue":"5","key":"561_CR17","doi-asserted-by":"publisher","first-page":"1157","DOI":"10.1007\/s11590-019-01414-z","volume":"13","author":"M Zhang","year":"2019","unstructured":"Zhang, M., Yuan, B., Zhou, Y., Luo, X., Huang, Z.: A primal-dual interior-point algorithm with arc-search for semidefinite programming. Optim. Lett. 13(5), 1157\u20131175 (2019)","journal-title":"Optim. Lett."},{"key":"561_CR18","doi-asserted-by":"crossref","unstructured":"Yuan, B., Zhang, M., Huang, Z.: A wide neighborhood primal-dual interior-point algorithm with arc-search for linear complementarity problems. J. Nonlinear Funct. Anal. Article ID 31 (2018)","DOI":"10.23952\/jnfa.2018.31"},{"key":"561_CR19","doi-asserted-by":"publisher","DOI":"10.1007\/s11075-021-01113-w","author":"M Yamashita","year":"2021","unstructured":"Yamashita, M., Iida, E., Yang, Y.: An infeasible interior-point arc-search algorithm for nonlinear constrained optimization. Numer. Algorithms (2021). https:\/\/doi.org\/10.1007\/s11075-021-01113-w","journal-title":"Numer. Algorithms"},{"key":"561_CR20","first-page":"372","volume":"269","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method of solving a convex programming problem with convergence rate $$o(1\/k^2)$$. Soviet Math. Dokl. 269, 372\u2013376 (1983)","journal-title":"Soviet Math. Dokl."},{"issue":"2","key":"561_CR21","first-page":"437","volume":"3","author":"T Dozat","year":"2016","unstructured":"Dozat, T.: Incorporating Nesterov momentum into adam. Nat. Hazards 3(2), 437\u2013453 (2016)","journal-title":"Nat. Hazards"},{"key":"561_CR22","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2019.104807","author":"MS Morshed","year":"2020","unstructured":"Morshed, M.S., Noor-E-Alam, M.: Generalized affine scaling algorithms for linear programming problems. Comput. Oper. Res. (2020). https:\/\/doi.org\/10.1016\/j.cor.2019.104807","journal-title":"Comput. Oper. Res."},{"key":"561_CR23","doi-asserted-by":"crossref","unstructured":"Browne, S., Dongarra, J., Grosse, E., Rowan, T.: The Netlib mathematical software repository. D-lib Magazine 1(9) (1995)","DOI":"10.1045\/september95-browne"},{"key":"561_CR24","doi-asserted-by":"publisher","DOI":"10.1201\/9781003042518","volume-title":"Arc-Search Techniques for Interior-Point Methods","author":"Y Yang","year":"2020","unstructured":"Yang, Y.: Arc-Search Techniques for Interior-Point Methods. CRC Press, Cambridge (2020)"},{"key":"561_CR25","doi-asserted-by":"publisher","first-page":"967","DOI":"10.1007\/s11075-016-0180-1","volume":"74","author":"Y Yang","year":"2017","unstructured":"Yang, Y.: CurveLP-A MATLAB implementation of an infeasible interior-point algorithm for linear programming. Numer. Algorithms 74, 967\u2013996 (2017). https:\/\/doi.org\/10.1007\/s11075-016-0180-1","journal-title":"Numer. Algorithms"},{"key":"561_CR26","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s10589-019-00079-9","volume":"73","author":"L-R Santos","year":"2019","unstructured":"Santos, L.-R., Villas-B\u00f4as, F., Oliveira, A.R., Perin, C.: Optimized choice of parameters in interior-point methods for linear programming. Comput. Optim. Appl. 73, 535\u2013574 (2019)","journal-title":"Comput. Optim. Appl."},{"key":"561_CR27","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. Program. 137, 587\u2013592 (2013)","journal-title":"Math. Program."},{"key":"561_CR28","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"ED Dolan","year":"2002","unstructured":"Dolan, E.D., Mor\u00e9, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201\u2013213 (2002)","journal-title":"Math. Program."},{"issue":"2","key":"561_CR29","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2950048","volume":"43","author":"N Gould","year":"2016","unstructured":"Gould, N., Scott, J.: A note on performance profiles for benchmarking software. ACM Trans. Math. Softw. (TOMS) 43(2), 1\u20135 (2016)","journal-title":"ACM Trans. Math. Softw. (TOMS)"},{"key":"561_CR30","doi-asserted-by":"publisher","unstructured":"Orban, D., contributors: BenchmarkProfiles.jl: A Simple Julia Package to Plot Performance and Data Profiles. https:\/\/github.com\/JuliaSmoothOptimizers\/BenchmarkProfiles.jl (2019). https:\/\/doi.org\/10.5281\/zenodo.4630955","DOI":"10.5281\/zenodo.4630955"},{"key":"561_CR31","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s10589-007-9106-0","volume":"41","author":"M Colombo","year":"2008","unstructured":"Colombo, M., Gondzio, J.: Further development of multiple centrality correctors for interior point methods. Comput. Optim. Appl. 41, 277\u2013305 (2008). https:\/\/doi.org\/10.1007\/s10589-007-9106-0","journal-title":"Comput. Optim. Appl."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-024-00561-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-024-00561-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-024-00561-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T16:08:40Z","timestamp":1715616520000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-024-00561-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,20]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["561"],"URL":"https:\/\/doi.org\/10.1007\/s10589-024-00561-z","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,2,20]]},"assertion":[{"value":"18 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 February 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"We have no conflicts of interest to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}