{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,23]],"date-time":"2025-05-23T10:31:50Z","timestamp":1747996310658,"version":"3.37.3"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T00:00:00Z","timestamp":1558483200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T00:00:00Z","timestamp":1558483200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100009153","name":"University of Portsmouth","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100009153","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":[[2019,11]]},"DOI":"10.1007\/s10589-019-00110-z","type":"journal-article","created":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T20:03:36Z","timestamp":1558555416000},"page":"583-621","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Interior point method on semi-definite linear complementarity problems using the Nesterov\u2013Todd (NT) search direction: polynomial complexity and local convergence"],"prefix":"10.1007","volume":"74","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0696-4698","authenticated-orcid":false,"given":"Chee-Khian","family":"Sim","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,5,22]]},"reference":[{"key":"110_CR1","doi-asserted-by":"publisher","first-page":"746","DOI":"10.1137\/S1052623496304700","volume":"8","author":"F Alizadeh","year":"1998","unstructured":"Alizadeh, F., Haeberly, J.A., Overton, M.: Primal\u2013dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM J. Optim. 8, 746\u2013768 (1998)","journal-title":"SIAM J. Optim."},{"key":"110_CR2","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s10589-018-0045-8","volume":"72","author":"B Alzalg","year":"2019","unstructured":"Alzalg, B.: A primal\u2013dual interior-point method based on various selections of displacement step for symmetric optimization. Comput. Optim. Appl. 72, 363\u2013390 (2019)","journal-title":"Comput. Optim. Appl."},{"key":"110_CR3","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"key":"110_CR4","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/s10957-004-5150-4","volume":"123","author":"SK Chua","year":"2004","unstructured":"Chua, S.K., Toh, K.-C., Zhao, G.: An analytic center cutting plane method with deep cuts for semidefinite feasibility problems. J. Optim. Theory Appl. 123, 291\u2013318 (2004)","journal-title":"J. Optim. Theory Appl."},{"key":"110_CR5","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/s10107-004-0555-2","volume":"103","author":"JX da\u00a0Cruz\u00a0Neto","year":"2005","unstructured":"da\u00a0Cruz\u00a0Neto, J.X., Ferreira, O.P., Monteiro, R.D.C.: Asymptotic behavior of the central path for a special class of degenerate SDP problems. Math. Program. Ser. A 103, 487\u2013514 (2005)","journal-title":"Math. Program. Ser. A"},{"key":"110_CR6","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1007\/s10589-018-0054-7","volume":"72","author":"L Faybusovich","year":"2019","unstructured":"Faybusovich, L., Zhou, C.: Long-step path-following algorithm for solving symmetric programming problems with nonlinear objective functions. Comput. Optim. Appl. 72, 769\u2013795 (2019)","journal-title":"Comput. Optim. Appl."},{"key":"110_CR7","first-page":"163","volume":"77","author":"P Gahinet","year":"1997","unstructured":"Gahinet, P., Nemirovski, A.: The projective method for solving linear matrix inequalities. Math. Program. Ser. B 77, 163\u2013190 (1997)","journal-title":"Math. Program. Ser. B"},{"key":"110_CR8","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"M Goemans","year":"1995","unstructured":"Goemans, M., Williamson, D.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"110_CR9","doi-asserted-by":"publisher","first-page":"638","DOI":"10.1137\/S1052623493258635","volume":"6","author":"J-L Goffin","year":"1996","unstructured":"Goffin, J.-L., Luo, Z., Ye, Y.: Complexity analysis of an interior cutting plane method for convex feasibility problems. SIAM J. Optim. 6, 638\u2013652 (1996)","journal-title":"SIAM J. Optim."},{"key":"110_CR10","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1016\/j.ejor.2011.02.022","volume":"214","author":"G Gu","year":"2011","unstructured":"Gu, G., Zangiabadi, M., Roos, C.: Full Nesterov\u2013Todd step infeasible interior-point method for symmetric optimization. Eur. J. Oper. Res. 214, 473\u2013484 (2011)","journal-title":"Eur. J. Oper. Res."},{"key":"110_CR11","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1137\/0806020","volume":"6","author":"C Helmberg","year":"1996","unstructured":"Helmberg, C., Rendl, F., Vanderbei, R.J., Wolkowicz, H.: An interior-point method for semidefinite programming. SIAM J. Optim. 6, 342\u2013361 (1996)","journal-title":"SIAM J. Optim."},{"key":"110_CR12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511810817","volume-title":"Matrix Analysis","author":"RA Horn","year":"1985","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985)"},{"key":"110_CR13","first-page":"129","volume":"80","author":"M Kojima","year":"1998","unstructured":"Kojima, M., Shida, M., Shindoh, S.: Local convergence of predictor\u2013corrector infeasible-interior-point algorithms for SDPs and SDLCPs. Math. Program. Ser. A 80, 129\u2013160 (1998)","journal-title":"Math. Program. Ser. A"},{"key":"110_CR14","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1137\/S1052623494269035","volume":"7","author":"M Kojima","year":"1997","unstructured":"Kojima, M., Shindoh, S., Hara, S.: Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM J. Optim. 7, 86\u2013125 (1997)","journal-title":"SIAM J. Optim."},{"key":"110_CR15","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1137\/S1052623403430828","volume":"15","author":"Z Lu","year":"2004","unstructured":"Lu, Z., Monteiro, R.D.C.: Error bounds and limiting behavior of weighted paths associated with the SDP map $${X}^{1\/2}{S}{X}^{1\/2}$$. SIAM J. Optim. 15, 348\u2013374 (2004)","journal-title":"SIAM J. Optim."},{"key":"110_CR16","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1137\/S1052623496299187","volume":"8","author":"Z-Q Luo","year":"1998","unstructured":"Luo, Z.-Q., Sturm, J.F., Zhang, S.: Superlinear convergence of a symmetric primal\u2013dual path following algorithm for semidefinite programming. SIAM J. Optim. 8, 59\u201381 (1998)","journal-title":"SIAM J. Optim."},{"key":"110_CR17","doi-asserted-by":"publisher","first-page":"663","DOI":"10.1137\/S1052623495293056","volume":"7","author":"RDC Monteiro","year":"1997","unstructured":"Monteiro, R.D.C.: Primal\u2013dual path following algorithms for semidefinite programming. SIAM J. Optim. 7, 663\u2013678 (1997)","journal-title":"SIAM J. Optim."},{"key":"110_CR18","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/S1052623496312836","volume":"9","author":"RDC Monteiro","year":"1999","unstructured":"Monteiro, R.D.C., Tsuchiya, T.: Polynomial convergence of a new family of primal\u2013dual algorithms for semidefinite programming. SIAM J. Optim. 9, 551\u2013577 (1999)","journal-title":"SIAM J. Optim."},{"key":"110_CR19","first-page":"281","volume":"81","author":"RDC Monteiro","year":"1998","unstructured":"Monteiro, R.D.C., Zhang, Y.: A unified analysis for a class of long-step primal\u2013dual path-following interior-point algorithms for semidefinite programming. Math. Program. 81, 281\u2013299 (1998)","journal-title":"Math. Program."},{"key":"110_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1287\/moor.22.1.1","volume":"22","author":"Y Nesterov","year":"1997","unstructured":"Nesterov, Y., Todd, M.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22, 1\u201342 (1997)","journal-title":"Math. Oper. Res."},{"key":"110_CR21","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1137\/S1052623495290209","volume":"8","author":"Y Nesterov","year":"1998","unstructured":"Nesterov, Y., Todd, M.: Primal\u2013dual interior-point methods for self-scaled cones. SIAM J. Optim. 8, 324\u2013364 (1998)","journal-title":"SIAM J. Optim."},{"key":"110_CR22","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1137\/140998950","volume":"26","author":"Y Nesterov","year":"2016","unstructured":"Nesterov, Y., Tun\u00e7el, L.: Local superlinear convergence of polynomial-time interior-point methods for hyperbolicity cone optimization problems. SIAM J. Optim. 26, 139\u2013170 (2016)","journal-title":"SIAM J. Optim."},{"key":"110_CR23","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s101070100230","volume":"91","author":"FA Potra","year":"2001","unstructured":"Potra, F.A.: Q-superlinear convergence of the iterates in primal\u2013dual interior-point methods. Math. Program. Ser. A 91, 99\u2013115 (2001)","journal-title":"Math. Program. Ser. A"},{"key":"110_CR24","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1023\/A:1021700210959","volume":"99","author":"FA Potra","year":"1998","unstructured":"Potra, F.A., Sheng, R.: Superlinear convergence of interior-point algorithms for semidefinite programming. J. Optim. Theory Appl. 99, 103\u2013119 (1998)","journal-title":"J. Optim. Theory Appl."},{"key":"110_CR25","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1137\/S1052623495294955","volume":"8","author":"FA Potra","year":"1998","unstructured":"Potra, F.A., Sheng, R.: A superlinearly convergent primal\u2013dual infeasible-interior-point algorithm for semidefinite programming. SIAM J. Optim. 8, 1007\u20131028 (1998)","journal-title":"SIAM J. Optim."},{"key":"110_CR26","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/s10107-003-0463-x","volume":"99","author":"M Prei\u00df","year":"2004","unstructured":"Prei\u00df, M., Stoer, J.: Analysis of infeasible-interior-point paths arising with semidefinite linear complementarity problems. Math. Program. Ser. A 99, 499\u2013520 (2004)","journal-title":"Math. Program. Ser. A"},{"key":"110_CR27","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1137\/040606557","volume":"16","author":"B Rangarajan","year":"2006","unstructured":"Rangarajan, B.: Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim. 16, 1211\u20131229 (2006)","journal-title":"SIAM J. Optim."},{"key":"110_CR28","doi-asserted-by":"publisher","first-page":"483","DOI":"10.1007\/s10589-018-0012-4","volume":"71","author":"PR Rig\u00f3","year":"2018","unstructured":"Rig\u00f3, P.R., Darvay, Z.: Infeasible interior-point method for symmetric optimization using a positive-asymptotic barrier. Comput. Optim. Appl. 71, 483\u2013508 (2018)","journal-title":"Comput. Optim. Appl."},{"key":"110_CR29","doi-asserted-by":"publisher","first-page":"1110","DOI":"10.1137\/050623917","volume":"16","author":"C Roos","year":"2006","unstructured":"Roos, C.: A full-Newton step $${\\cal{O}}(n)$$ infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16, 1110\u20131136 (2006)","journal-title":"SIAM J. Optim."},{"key":"110_CR30","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s10107-003-0380-z","volume":"96","author":"S Schmieta","year":"2003","unstructured":"Schmieta, S., Alizadeh, F.: Extension of primal\u2013dual interior point algorithm to symmetric cones. Math. Program. 96, 409\u2013438 (2003)","journal-title":"Math. Program."},{"key":"110_CR31","unstructured":"Shilon, O.: RandOrthMat. \n                    https:\/\/uk.mathworks.com\/matlabcentral\/fileexchange\/11783-randorthmat\n                    \n                   (2006)"},{"key":"110_CR32","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s10957-008-9480-5","volume":"141","author":"C-K Sim","year":"2009","unstructured":"Sim, C.-K.: On the analyticity of underlying HKM paths for monotone semidefinite linear complementarity problems. J. Optim. Theory Appl. 141, 193\u2013215 (2009)","journal-title":"J. Optim. Theory Appl."},{"key":"110_CR33","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s10957-010-9746-6","volume":"148","author":"C-K Sim","year":"2011","unstructured":"Sim, C.-K.: Asymptotic behavior of underlying NT paths in interior point methods for monotone semidefinite linear complementarity problems. J. Optim. Theory Appl. 148, 79\u2013106 (2011)","journal-title":"J. Optim. Theory Appl."},{"key":"110_CR34","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1137\/090779279","volume":"21","author":"C-K Sim","year":"2011","unstructured":"Sim, C.-K.: Superlinear convergence of an infeasible predictor\u2013corrector path-following interior point algorithm for a semidefinite linear complementarity problem using the Helmberg\u2013Kojima\u2013Monteiro direction. SIAM J. Optim. 21, 102\u2013126 (2011)","journal-title":"SIAM J. Optim."},{"key":"110_CR35","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1007\/s10107-006-0010-7","volume":"110","author":"C-K Sim","year":"2007","unstructured":"Sim, C.-K., Zhao, G.: Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem. Math. Program. Ser. A 110, 475\u2013499 (2007)","journal-title":"Math. Program. Ser. A"},{"key":"110_CR36","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/s10957-007-9280-3","volume":"137","author":"C-K Sim","year":"2008","unstructured":"Sim, C.-K., Zhao, G.: Asymptotic behavior of Helmberg\u2013Kojima\u2013Monteiro (HKM) paths in interior point methods for monotone semidefinite linear complementarity problem: general theory. J. Optim. Theory Appl. 137, 11\u201325 (2008)","journal-title":"J. Optim. Theory Appl."},{"key":"110_CR37","doi-asserted-by":"crossref","unstructured":"Sturm, J.F.: Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones (Updated for Version 1.05) (1998\u20132001)","DOI":"10.1080\/10556789908805766"},{"key":"110_CR38","doi-asserted-by":"publisher","first-page":"332","DOI":"10.1287\/moor.27.2.332.327","volume":"27","author":"J Sun","year":"2002","unstructured":"Sun, J., Toh, K.-C., Zhao, G.: An analytic center cutting plane method for semidefinite feasibility problems. Math. Oper. Res. 27, 332\u2013346 (2002)","journal-title":"Math. Oper. Res."},{"key":"110_CR39","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1137\/S105262349630060X","volume":"8","author":"MJ Todd","year":"1998","unstructured":"Todd, M.J., Toh, K.C., T\u00fct\u00fcnc\u00fc, R.H.: On the Nesterov\u2013Todd direction in semidefinite programming. SIAM J. Optim. 8, 769\u2013796 (1998)","journal-title":"SIAM J. Optim."},{"key":"110_CR40","first-page":"715","volume-title":"Handbook on Semidefinite, Conic and Polynomial Optimization, Vol.\u00a0166 of International Series in Operations Research & Management Science","author":"K-C Toh","year":"2012","unstructured":"Toh, K.-C., Todd, M.J., T\u00fct\u00fcnc\u00fc, R.H.: On the implementation and usage of SDPT3\u2014a Matlab software package for semidefinite-quadratic-linear programming, Version 4.0. In: Anjos, M.F., Lasserre, J.B. (eds.) Handbook on Semidefinite, Conic and Polynomial Optimization, Vol.\u00a0166 of International Series in Operations Research & Management Science, pp. 715\u2013754. Springer, Berlin (2012)"},{"key":"110_CR41","doi-asserted-by":"publisher","first-page":"1126","DOI":"10.1137\/S1052623400370503","volume":"12","author":"K-C Toh","year":"2002","unstructured":"Toh, K.-C., Zhao, G., Sun, J.: A multiple-cut analytic center cutting plane method for semidefinite feasibility problems. SIAM J. Optim. 12, 1126\u20131146 (2002)","journal-title":"SIAM J. Optim."},{"key":"110_CR42","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1080\/10556789808805695","volume":"9","author":"P Tseng","year":"1998","unstructured":"Tseng, P.: Search directions and convergence analysis of some infeasible path-following methods for the monotone semi-definite LCP. Optim. Methods Softw. 9, 245\u2013268 (1998)","journal-title":"Optim. Methods Softw."},{"key":"110_CR43","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/s10957-014-0619-2","volume":"165","author":"GQ Wang","year":"2015","unstructured":"Wang, G.Q., Bai, Y.Q., Gao, X.Y., Wang, D.Z.: Improved complexity analysis of full Nesterov\u2013Todd step interior-point methods for semidefinite optimization. J. Optim. Theory Appl. 165, 242\u2013262 (2015)","journal-title":"J. Optim. Theory Appl."},{"key":"110_CR44","doi-asserted-by":"publisher","first-page":"588","DOI":"10.1007\/s10957-014-0696-2","volume":"166","author":"GQ Wang","year":"2015","unstructured":"Wang, G.Q., Kong, L.C., Tao, J.Y., Lesaja, G.: Improved complexity analysis of full Nesterov\u2013Todd step feasible interior-point method for symmetric optimization. J. Optim. Theory Appl. 166, 588\u2013604 (2015)","journal-title":"J. Optim. Theory Appl."},{"key":"110_CR45","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1137\/S1052623495296115","volume":"8","author":"Y Zhang","year":"1998","unstructured":"Zhang, Y.: On extending some primal\u2013dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8, 365\u2013386 (1998)","journal-title":"SIAM J. Optim."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-019-00110-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-019-00110-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-019-00110-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,20]],"date-time":"2020-05-20T23:24:13Z","timestamp":1590017053000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-019-00110-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,22]]},"references-count":45,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["110"],"URL":"https:\/\/doi.org\/10.1007\/s10589-019-00110-z","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2019,5,22]]},"assertion":[{"value":"26 November 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 May 2019","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}