{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T13:21:39Z","timestamp":1751808099097,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T00:00:00Z","timestamp":1633910400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,11]],"date-time":"2021-10-11T00:00:00Z","timestamp":1633910400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Sci Comput"],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A new relaxed variant of interior point method for low-rank semidefinite programming problems is proposed in this paper. The method is a step outside of the usual interior point framework. In anticipation to converging to a low-rank primal solution, a special nearly low-rank form of all primal iterates is imposed. To accommodate such a (restrictive) structure, the first order optimality conditions have to be relaxed and are therefore approximated by solving an auxiliary least-squares problem. The relaxed interior point framework opens numerous possibilities how primal and dual approximated Newton directions can be computed. In particular, it admits the application of both the first- and the second-order methods in this context. The convergence of the method is established. A prototype implementation is discussed and encouraging preliminary computational results are reported for solving the SDP-reformulation of matrix-completion problems.<\/jats:p>","DOI":"10.1007\/s10915-021-01654-1","type":"journal-article","created":{"date-parts":[[2021,10,12]],"date-time":"2021-10-12T00:01:53Z","timestamp":1633996913000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["A Relaxed Interior Point Method for Low-Rank Semidefinite Programming Problems with Applications to Matrix Completion"],"prefix":"10.1007","volume":"89","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3691-7836","authenticated-orcid":false,"given":"Stefania","family":"Bellavia","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6270-4666","authenticated-orcid":false,"given":"Jacek","family":"Gondzio","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0183-1204","authenticated-orcid":false,"given":"Margherita","family":"Porcelli","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,10,11]]},"reference":[{"key":"1654_CR1","doi-asserted-by":"crossref","unstructured":"Andersen, M., Dahl, J., Liu, Z., Vandenberghe, L.: Interior-Point Methods for Large-scale Cone Programming, pp.\u00a055\u201383. MIT Press (2011)","DOI":"10.7551\/mitpress\/8996.003.0005"},{"key":"1654_CR2","doi-asserted-by":"crossref","unstructured":"Anjos, M., Lasserre, J.: Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications, International Series in Operational Research and Management Science (2012)","DOI":"10.1007\/978-1-4614-0769-0"},{"key":"1654_CR3","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1093\/imanum\/8.1.141","volume":"8","author":"J Barzilai","year":"1988","unstructured":"Barzilai, J., Borwein, J.: Two point step size gradient methods. IMA J. Numer. Anal. 8, 141\u2013148 (1988)","journal-title":"IMA J. Numer. Anal."},{"key":"1654_CR4","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/s10107-018-1281-5","volume":"178","author":"S Bellavia","year":"2019","unstructured":"Bellavia, S., Gondzio, J., Porcelli, M.: An inexact dual logarithmic barrier method for solving sparse semidefinite programs. Math. Program. 178, 109\u2013143 (2019)","journal-title":"Math. Program."},{"key":"1654_CR5","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1137\/S1052623497328008","volume":"10","author":"SJ Benson","year":"2000","unstructured":"Benson, S.J., Ye, Y., Zhang, X.: Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim. 10, 443\u2013461 (2000)","journal-title":"SIAM J. Optim."},{"key":"1654_CR6","first-page":"2757","volume":"29","author":"N Boumal","year":"2016","unstructured":"Boumal, N., Voroninski, V., Bandeira, A.: The non-convex Burer\u2013Monteiro approach works on smooth semidefinite programs. Adv. Neural Inf. Process. Syst. 29, 2757\u20132765 (2016)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"1654_CR7","doi-asserted-by":"crossref","unstructured":"Boumal, N., Voroninski, V., Bandeira, A.S.: Deterministic guarantees for Burer\u2013Monteiro factorizations of smooth semidefinite programs (2018). arXiv preprint arXiv:1804.02008","DOI":"10.1002\/cpa.21830"},{"key":"1654_CR8","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s10107-002-0352-8","volume":"95","author":"S Burer","year":"2003","unstructured":"Burer, S., Monteiro, R.D.C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95, 329\u2013357 (2003)","journal-title":"Math. Program."},{"key":"1654_CR9","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/s10107-004-0564-1","volume":"103","author":"S Burer","year":"2005","unstructured":"Burer, S., Monteiro, R.D.C.: Local minima and convergence in low-rank semidefinite programming. Math. Program. 103, 427\u2013444 (2005)","journal-title":"Math. Program."},{"key":"1654_CR10","unstructured":"Burkardt, J.: Cities\u2014City Distance Datasets. http:\/\/people.sc.fsu.edu\/~burkardt\/datasets\/cities\/cities.html"},{"key":"1654_CR11","doi-asserted-by":"publisher","first-page":"1956","DOI":"10.1137\/080738970","volume":"20","author":"J-F Cai","year":"2010","unstructured":"Cai, J.-F., Cand\u00e8s, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20, 1956\u20131982 (2010)","journal-title":"SIAM J. Optim."},{"key":"1654_CR12","doi-asserted-by":"publisher","first-page":"925","DOI":"10.1109\/JPROC.2009.2035722","volume":"98","author":"EJ Candes","year":"2010","unstructured":"Candes, E.J., Plan, Y.: Matrix completion with noise. Proc. IEEE 98, 925\u2013936 (2010)","journal-title":"Proc. IEEE"},{"key":"1654_CR13","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","volume":"9","author":"EJ Cand\u00e8s","year":"2009","unstructured":"Cand\u00e8s, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9, 717\u2013772 (2009)","journal-title":"Found. Comput. Math."},{"key":"1654_CR14","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1093\/imanum\/drq039","volume":"32","author":"C Chen","year":"2012","unstructured":"Chen, C., He, B., Yuan, X.: Matrix completion via an alternating direction method. IMA J. Numer. Anal. 32, 227\u2013245 (2012)","journal-title":"IMA J. Numer. Anal."},{"key":"1654_CR15","volume-title":"Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications","author":"E De Klerk","year":"2006","unstructured":"De Klerk, E.: Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications, vol. 65. Springer, Berlin (2006)"},{"key":"1654_CR16","doi-asserted-by":"publisher","first-page":"870","DOI":"10.1137\/S1052623499352632","volume":"11","author":"E de Klerk","year":"2001","unstructured":"de Klerk, E., Peng, J., Roos, C., Terlaky, T.: A scaled Gauss\u2013Newton primal-dual search direction for semidefinite optimization. SIAM J. Optim. 11, 870\u2013888 (2001)","journal-title":"SIAM J. Optim."},{"key":"1654_CR17","doi-asserted-by":"crossref","unstructured":"di\u00a0Serafino, D., Ruggiero, V., Toraldo, G., Zanni, L.: On the Steplength Selection in Gradient Methods for Unconstrained Optimization, Applied Mathematics and Computation, vol. 318, pp.\u00a0176 \u2013 195. Recent Trends in Numerical Computations: Theory and Algorithms (2018)","DOI":"10.1016\/j.amc.2017.07.037"},{"key":"1654_CR18","unstructured":"Fackler, P.L.: Notes on Matrix Calculus. Privately Published (2005)"},{"key":"1654_CR19","doi-asserted-by":"crossref","unstructured":"Fazel, M., Hindi, H., Boyd, S.P., A rank minimization heuristic with application to minimum order system approximation. In: American Control Conference: Proceedings of the 2001, vol. 6, pp. 4734\u20134739 (2001)","DOI":"10.1109\/ACC.2001.945730"},{"key":"1654_CR20","first-page":"235","volume":"79","author":"K Fujisawa","year":"1997","unstructured":"Fujisawa, K., Kojima, M., Nakata, K.: Exploiting sparsity in primal-dual interior-point methods for semidefinite programming. Math. Program. 79, 235\u2013253 (1997)","journal-title":"Math. Program."},{"key":"1654_CR21","doi-asserted-by":"crossref","unstructured":"Gillberg, J., Hansson, A.: Polynomial complexity for a Nesterov\u2013Todd potential reduction method with inexact search directions. In: Proceedings of the 42nd IEEE Conference on Decision and Control, vol.\u00a03, pp.\u00a03824\u20133829. IEEE (2003)","DOI":"10.1109\/CDC.2003.1271745"},{"key":"1654_CR22","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115\u20131145 (1995)","journal-title":"J. ACM"},{"key":"1654_CR23","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/s10589-017-9928-3","volume":"68","author":"GN Grapiglia","year":"2017","unstructured":"Grapiglia, G.N., Sachs, E.W.: On the worst-case evaluation complexity of non-monotone line search algorithms. Comput. Optim. Appl. 68, 555\u2013577 (2017)","journal-title":"Comput. Optim. Appl."},{"key":"1654_CR24","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01580610","volume":"60","author":"O G\u00fcler","year":"1993","unstructured":"G\u00fcler, O., Ye, Y.: Convergence behavior of interior-point algorithms. Math. Program. 60, 215\u2013228 (1993)","journal-title":"Math. Program."},{"key":"1654_CR25","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1145\/360569.360658","volume":"18","author":"MR Hestenes","year":"1975","unstructured":"Hestenes, M.R.: Pseudoinversus and conjugate gradients. Commun. ACM 18, 40\u201343 (1975)","journal-title":"Commun. ACM"},{"key":"1654_CR26","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s10898-017-0590-1","volume":"72","author":"S Huang","year":"2018","unstructured":"Huang, S., Wolkowicz, H.: Low-rank matrix completion using nuclear norm minimization and facial reduction. J. Glob. Optim. 72, 5\u201326 (2018)","journal-title":"J. Glob. Optim."},{"key":"1654_CR27","unstructured":"Ji, H., O\u2019Saben, E., Boudion, A., Li, Y.: March madness prediction: a matrix completion approach. In: Proceedings of Modeling, Simulation, and Visualization Student Capstone Conference, pp.\u00a041\u201348 (2015)"},{"key":"1654_CR28","doi-asserted-by":"publisher","first-page":"2980","DOI":"10.1109\/TIT.2010.2046205","volume":"56","author":"R-H Keshavan","year":"2010","unstructured":"Keshavan, R.-H., Montanari, A., Oh, S.: Matrix completion from a few entries. IEEE Trans. Inf. Theory 56, 2980\u20132998 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1654_CR29","unstructured":"Keshavan, R.-H., Oh, S.: Optspace: a gradient descent algorithm on the Grassmann manifold for matrix completion (2009). arXiv preprint arXiv:0910.5260"},{"key":"1654_CR30","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/s10107-006-0029-9","volume":"109","author":"M Kocvara","year":"2007","unstructured":"Kocvara, M., Stingl, M.: On the solution of large-scale SDP problems by the modified barrier method using iterative solvers. Math. Program. 109, 413\u2013444 (2007)","journal-title":"Math. Program."},{"key":"1654_CR31","first-page":"1514","volume":"8","author":"K Koh","year":"2007","unstructured":"Koh, K., Kim, S.-J., Boyd, S.: An interior-point method for large-scale $$\\ell $$1-regularized logistic regression. J. Mach. Learn. Res. 8, 1514\u20131555 (2007)","journal-title":"J. Mach. Learn. Res."},{"key":"1654_CR32","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1080\/10556780108805808","volume":"15","author":"S Kruk","year":"2001","unstructured":"Kruk, S., Muramatsu, M., Rendl, F., Vanderbei, R.J., Wolkowicz, H.: The Gauss\u2013Newton direction in semidefinite programming. Optim. Methods Softw. 15, 1\u201328 (2001)","journal-title":"Optim. Methods Softw."},{"key":"1654_CR33","doi-asserted-by":"publisher","first-page":"4402","DOI":"10.1109\/TIT.2010.2054251","volume":"56","author":"K Lee","year":"2010","unstructured":"Lee, K., Bresler, Y.: Admira: atomic decomposition for minimum rank approximation. IEEE Trans. Inf. Theory 56, 4402\u20134416 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1654_CR34","first-page":"1","volume":"2","author":"A Lemon","year":"2016","unstructured":"Lemon, A., So, A.M.-C., Ye, Y., et al.: Low-rank semidefinite programming: theory and applications, foundations and trends\u00ae. Optimization 2, 1\u2013156 (2016)","journal-title":"Optimization"},{"key":"1654_CR35","unstructured":"Lin, Z., Chen, M., Ma, Y.: The augmented Lagrange multiplier method for exact recovery of corrupted low-rank matrices (2010). arXiv preprint arXiv:1009.5055"},{"key":"1654_CR36","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1137\/090755436","volume":"31","author":"Z Liu","year":"2009","unstructured":"Liu, Z., Vandenberghe, L.: Interior-point method for nuclear norm approximation with application to system identification. SIAM J. Matrix Anal. Appl. 31, 1235\u20131256 (2009)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1654_CR37","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/s10107-009-0306-5","volume":"128","author":"S Ma","year":"2011","unstructured":"Ma, S., Goldfarb, D., Chen, L.: Fixed point and Bregman iterative methods for matrix rank minimization. Math. Program. 128, 321\u2013353 (2011)","journal-title":"Math. Program."},{"key":"1654_CR38","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1137\/S1052623494266365","volume":"7","author":"M Raydan","year":"1997","unstructured":"Raydan, M.: The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem. SIAM J. Optim. 7, 26\u201333 (1997)","journal-title":"SIAM J. Optim."},{"key":"1654_CR39","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1137\/070697835","volume":"52","author":"B Recht","year":"2010","unstructured":"Recht, B., Fazel, M., Parrilo, P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52, 471\u2013501 (2010)","journal-title":"SIAM Rev."},{"issue":"10","key":"1654_CR40","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1017\/S0962492901000071","volume":"2001","author":"MJ Todd","year":"2001","unstructured":"Todd, M.J.: Semidefinite optimization. Acta Numer. 2001(10), 515\u2013560 (2001)","journal-title":"Acta Numer."},{"key":"1654_CR41","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1137\/S1052623400376378","volume":"12","author":"K-C Toh","year":"2002","unstructured":"Toh, K.-C., Kojima, M.: Solving some large scale semidefinite programs via the conjugate residual method. SIAM J. Optim. 12, 669\u2013691 (2002)","journal-title":"SIAM J. Optim."},{"key":"1654_CR42","first-page":"15","volume":"6","author":"K-C Toh","year":"2010","unstructured":"Toh, K.-C., Yun, S.: An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pac. J. Optim. 6, 15 (2010)","journal-title":"Pac. J. Optim."},{"key":"1654_CR43","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1561\/2400000006","volume":"1","author":"L Vandenberghe","year":"2015","unstructured":"Vandenberghe, L., Andersen, M.S.: Chordal graphs and semidefinite optimization. Found. Trends Optim. 1, 241\u2013433 (2015)","journal-title":"Found. Trends Optim."},{"key":"1654_CR44","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L Vandenberghe","year":"1996","unstructured":"Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38, 49\u201395 (1996)","journal-title":"SIAM Rev."},{"key":"1654_CR45","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s11464-012-0194-5","volume":"7","author":"Y Xu","year":"2012","unstructured":"Xu, Y., Yin, W., Wen, Z., Zhang, Y.: An alternating direction algorithm for matrix completion with nonnegative factors. Front. Math. China 7, 365\u2013384 (2012)","journal-title":"Front. Math. China"},{"key":"1654_CR46","doi-asserted-by":"crossref","unstructured":"Zhang, R.\u00a0Y. , Lavaei, J.: Modified interior-point method for large-and-sparse low-rank semidefinite programs. In: 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pp.\u00a05640\u20135647. IEEE (2017)","DOI":"10.1109\/CDC.2017.8264510"}],"container-title":["Journal of Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10915-021-01654-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10915-021-01654-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10915-021-01654-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T20:39:37Z","timestamp":1725914377000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10915-021-01654-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,11]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["1654"],"URL":"https:\/\/doi.org\/10.1007\/s10915-021-01654-1","relation":{},"ISSN":["0885-7474","1573-7691"],"issn-type":[{"type":"print","value":"0885-7474"},{"type":"electronic","value":"1573-7691"}],"subject":[],"published":{"date-parts":[[2021,10,11]]},"assertion":[{"value":"14 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"46"}}