{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T11:59:52Z","timestamp":1770897592340,"version":"3.50.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"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 Optim Theory Appl"],"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this paper we generalize the Interior Point-Proximal Method of Multipliers (IP-PMM) presented in Pougkakiotis and Gondzio (Comput Optim Appl 78:307\u2013351, 2021.<jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"doi\" xlink:href=\"https:\/\/doi.org\/10.1007\/s10589-020-00240-9\">10.1007\/s10589-020-00240-9<\/jats:ext-link>) for the solution of linear positive Semi-Definite Programming (SDP) problems, allowing inexactness in the solution of the associated Newton systems. In particular, we combine an infeasible Interior Point Method (IPM) with the Proximal Method of Multipliers (PMM) and interpret the algorithm (IP-PMM) as a primal-dual regularized IPM, suitable for solving SDP problems. We apply some iterations of an IPM to each sub-problem of the PMM until a satisfactory solution is found. We then update the PMM parameters, form a new IPM neighbourhood, and repeat this process. Given this framework, we prove polynomial complexity of the algorithm, under mild assumptions, and without requiring exact computations for the Newton directions. We furthermore provide a necessary condition for lack of strong duality, which can be used as a basis for constructing detection mechanisms for identifying pathological cases within IP-PMM.<\/jats:p>","DOI":"10.1007\/s10957-021-01954-4","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T12:02:36Z","timestamp":1635422556000},"page":"97-129","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["An Interior Point-Proximal Method of Multipliers for Linear Positive Semi-Definite Programming"],"prefix":"10.1007","volume":"192","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":[[2021,10,28]]},"reference":[{"issue":"1\u20134","key":"1954_CR1","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). https:\/\/doi.org\/10.1080\/10556789908805754","journal-title":"Optim. Methods Softw."},{"key":"1954_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. Program. 137, 587\u2013592 (2013). https:\/\/doi.org\/10.1007\/s10107-011-0498-3","journal-title":"Math. Program."},{"key":"1954_CR3","series-title":"International Series in Operations Research & Management Science","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/978-1-4615-4381-7_14","volume-title":"Handbook of Semidefinite Programming: Theory, Algorithms and Applications","author":"V Balakrishnan","year":"2000","unstructured":"Balakrishnan, V., Wang, F.: Handbook of Semidefinite Programming. In: Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.) Handbook of Semidefinite Programming: Theory, Algorithms and Applications. International Series in Operations Research&amp; Management Science, vol. 27, pp. 421\u2013441. Springer, Boston (2000). https:\/\/doi.org\/10.1007\/978-1-4615-4381-7_14"},{"key":"1954_CR4","doi-asserted-by":"publisher","unstructured":"Bellavia, S., Gondzio, J., Porcelli, M.: A relaxed interior point method for low-rank semidefinite programming problems. J. Sci. Comput. (2019). https:\/\/doi.org\/10.1007\/s10915-021-01654-1","DOI":"10.1007\/s10915-021-01654-1"},{"key":"1954_CR5","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). https:\/\/doi.org\/10.1007\/s10107-018-1281-5","journal-title":"Math. Program."},{"issue":"4","key":"1954_CR6","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1287\/moor.23.4.769","volume":"23","author":"A Ben-Tal","year":"1998","unstructured":"Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23(4), 769\u2013805 (1998). https:\/\/doi.org\/10.1287\/moor.23.4.769","journal-title":"Math. Oper. Res."},{"issue":"4","key":"1954_CR7","doi-asserted-by":"publisher","first-page":"e2361","DOI":"10.1002\/nla.2361","volume":"28","author":"L Bergamaschi","year":"2021","unstructured":"Bergamaschi, L., Gondzio, J., Mart\u00ednez, A., Pearson, J.W., Pougkakiotis, S.: A new preconditioning approach for an interior point-proximal method of multipliers for linear and convex quadratic programming. Numer. Linear Algebra Appl. 28(4), e2361 (2021). https:\/\/doi.org\/10.1002\/nla.2361","journal-title":"Numer. Linear Algebra Appl."},{"key":"1954_CR8","doi-asserted-by":"crossref","unstructured":"De\u00a0Simone, V., di\u00a0Serafino, D., Gondzio, J., Pougkakiotis, S., Viola, M.: Sparse approximations with interior point methods. arXiv:2102.13608v2 [math.OC] (2021)","DOI":"10.1137\/21M1401103"},{"issue":"1","key":"1954_CR9","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1080\/10556788.2016.1235708","volume":"32","author":"A Dehghani","year":"2017","unstructured":"Dehghani, A., Goffin, J.L., Orban, D.: A Primal-dual regularized interior-point method for semidefinite programming. Optim. Methods Softw. 32(1), 193\u2013219 (2017). https:\/\/doi.org\/10.1080\/10556788.2016.1235708","journal-title":"Optim. Methods Softw."},{"key":"1954_CR10","doi-asserted-by":"crossref","unstructured":"Gondzio, J., Pougkakiotis, S., Pearson, J.W.: General-purpose preconditioning for regularized interior point methods. arXiv:2107.06822 [math.OC] (2021)","DOI":"10.1007\/s10589-022-00424-5"},{"key":"1954_CR11","doi-asserted-by":"publisher","first-page":"462","DOI":"10.1137\/S105262349731950X","volume":"10","author":"M Gu","year":"2000","unstructured":"Gu, M.: Primal-dual interior-point methods for semidefinite progamming in finite precision. SIAM J. Optim. 10, 462\u2013502 (2000). https:\/\/doi.org\/10.1137\/S105262349731950X","journal-title":"SIAM J. Optim."},{"key":"1954_CR12","unstructured":"Jiang, X., Vandenberghe, L.: Bregman primal-dual first-order method and application to sparse semidefinite programming. http:\/\/www.optimization-online.org\/DB_HTML\/2020\/03\/7702.html (2020)"},{"issue":"1","key":"1954_CR13","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1109\/TPWRS.2011.2160974","volume":"27","author":"J Lavaei","year":"2012","unstructured":"Lavaei, J., Low, S.H.: Zero duality gap in optimal power flow problem. IEEE Trans. Power Syst. 27(1), 92\u2013107 (2012). https:\/\/doi.org\/10.1109\/TPWRS.2011.2160974","journal-title":"IEEE Trans. Power Syst."},{"key":"1954_CR14","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s10107-017-1136-5","volume":"167","author":"M Liu","year":"2018","unstructured":"Liu, M., Pataki, G.: Exact duals and short certificates of infeasibility and weak infeasibility in conic linear programming. Math. Program. 167, 435\u2013480 (2018). https:\/\/doi.org\/10.1007\/s10107-017-1136-5","journal-title":"Math. Program."},{"key":"1954_CR15","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. Program. 84, 105\u2013122 (1999). https:\/\/doi.org\/10.1007\/s10107980020a","journal-title":"Math. Program."},{"key":"1954_CR16","unstructured":"MOSEK: The MOSEK Optimization Software. http:\/\/www.mosek.com, v9.2 (2020)"},{"key":"1954_CR17","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611970791","volume-title":"Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms","author":"Y Nesterov","year":"1994","unstructured":"Nesterov, Y., Nemirovskii, A.S.: Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms. SIAM Publications, Philadelphia (1994). https:\/\/doi.org\/10.1137\/1.9781611970791"},{"key":"1954_CR18","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, 905\u2013945 (2019). https:\/\/doi.org\/10.1007\/s10957-019-01491-1","journal-title":"J. Optim. Theory Appl."},{"key":"1954_CR19","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10589-020-00240-9","volume":"78","author":"S Pougkakiotis","year":"2021","unstructured":"Pougkakiotis, S., Gondzio, J.: An interior point-proximal method of multipliers for convex quadratic programming. Comput. Optim. Appl. 78, 307\u2013351 (2021). https:\/\/doi.org\/10.1007\/s10589-020-00240-9","journal-title":"Comput. Optim. Appl."},{"issue":"2","key":"1954_CR20","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). https:\/\/doi.org\/10.1287\/moor.1.2.97","journal-title":"Math. Oper. Res."},{"issue":"5","key":"1954_CR21","doi-asserted-by":"publisher","first-page":"877","DOI":"10.1137\/0314056","volume":"14","author":"RT Rockafellar","year":"1976","unstructured":"Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5), 877\u2013898 (1976). https:\/\/doi.org\/10.1137\/0314056","journal-title":"SIAM J. Control Optim."},{"key":"1954_CR22","doi-asserted-by":"publisher","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"RT Rockafellar","year":"1996","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1996). https:\/\/doi.org\/10.1515\/9781400873173"},{"key":"1954_CR23","unstructured":"Saunders, M., Tomlin, J.A.: Solving regularized linear programs using barrier methods and KKT systems. Technical Report SOL 96-4, Systems Optimization Laboratory, Department of Operational Research, Stanford University, Stanford, CA 94305, USA (1996)"},{"key":"1954_CR24","series-title":"International Series in Operations Research & Management Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/978-1-4615-4381-7_4","volume-title":"Handbook of Semidefinite Programming: Theory, Algorithms and Applications","author":"A Shapiro","year":"2000","unstructured":"Shapiro, A., Scheinberg, K.: Duality and optimality conditions. In: Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.) Handbook of Semidefinite Programming: Theory, Algorithms and Applications. International Series in Operations Research&amp; Management Science, vol. 27, pp. 67\u2013110. Springer, Boston (2000)"},{"key":"1954_CR25","doi-asserted-by":"publisher","DOI":"10.1080\/02331934.2020.1823387","author":"M Souto","year":"2020","unstructured":"Souto, M., Garcia, J.D., Veiga, A.: Exploiting low-rank structure in semidefinite programming by approximate operator splitting. Optimization (2020). https:\/\/doi.org\/10.1080\/02331934.2020.1823387","journal-title":"Optimization"},{"key":"1954_CR26","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1080\/10556789908805745","volume":"11","author":"MJ Todd","year":"1999","unstructured":"Todd, M.J.: A study of search directions in primal-dual interior-point methods for semidefinite programming. Optim. Methods Softw. 11, 545\u2013581 (1999). https:\/\/doi.org\/10.1080\/10556789908805745","journal-title":"Optim. Methods Softw."},{"issue":"3","key":"1954_CR27","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1016\/S0168-9274(98)00098-1","volume":"29","author":"L Vandenberghe","year":"1999","unstructured":"Vandenberghe, L., Boyd, S.: Applications of semidefinite programming. Appl. Numer. Math. 29(3), 283\u2013299 (1999). https:\/\/doi.org\/10.1016\/S0168-9274(98)00098-1","journal-title":"Appl. Numer. Math."},{"key":"1954_CR28","doi-asserted-by":"publisher","first-page":"2093","DOI":"10.1007\/s00158-019-02312-9","volume":"60","author":"AG Weldeyesus","year":"2019","unstructured":"Weldeyesus, A.G., Gondzio, J., He, L., Gilbert, M., Sheperd, P., Tyas, A.: Adaptive solution of truss layout optimization problems with global stability constraints. Struct. Multidiscip. Optim. 60, 2093\u20132111 (2019). https:\/\/doi.org\/10.1007\/s00158-019-02312-9","journal-title":"Struct. Multidiscip. Optim."},{"key":"1954_CR29","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-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8, 365\u2013386 (1998). https:\/\/doi.org\/10.1137\/S1052623495296115","journal-title":"SIAM J. Optim."},{"issue":"4","key":"1954_CR30","doi-asserted-by":"publisher","first-page":"1737","DOI":"10.1137\/080718206","volume":"20","author":"XY Zhao","year":"2010","unstructured":"Zhao, X.Y., Sun, D., Toh, K.C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Optim. 20(4), 1737\u20131765 (2010). https:\/\/doi.org\/10.1137\/080718206","journal-title":"SIAM J. Optim."},{"issue":"A","key":"1954_CR31","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1007\/s10107-003-0431-5","volume":"99","author":"G Zhou","year":"2004","unstructured":"Zhou, G., Toh, K.C.: Polynomiality of an inexact infeasible interior point algorithm for semidefinite programming. Math. Program. 99(A), 261\u2013282 (2004). https:\/\/doi.org\/10.1007\/s10107-003-0431-5","journal-title":"Math. Program."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-021-01954-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-021-01954-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-021-01954-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,14]],"date-time":"2023-01-14T01:08:44Z","timestamp":1673658524000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-021-01954-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,28]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,1]]}},"alternative-id":["1954"],"URL":"https:\/\/doi.org\/10.1007\/s10957-021-01954-4","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,28]]},"assertion":[{"value":"27 October 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}