{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:04Z","timestamp":1740109324334,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,6,15]],"date-time":"2023-06-15T00:00:00Z","timestamp":1686787200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,6,15]],"date-time":"2023-06-15T00:00:00Z","timestamp":1686787200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["05M18OCA"],"award-info":[{"award-number":["05M18OCA"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["CRC 1410"],"award-info":[{"award-number":["CRC 1410"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The conic bundle implementation of the spectral bundle method for large scale semidefinite programming solves in each iteration a semidefinite quadratic subproblem by an interior point approach. For larger cutting model sizes the limiting operation is collecting and factorizing a Schur complement of the primal-dual KKT system. We explore possibilities to improve on this by an iterative approach that exploits structural low rank properties. Two preconditioning approaches are proposed and analyzed. Both might be of interest for rank structured positive definite systems in general. The first employs projections onto random subspaces, the second projects onto a subspace that is chosen deterministically based on structural interior point properties. For both approaches theoretic bounds are derived for the associated condition number. In the instances tested the deterministic preconditioner provides surprisingly efficient control on the actual condition number. The results suggest that for large scale instances the iterative solver is usually the better choice if precision requirements are moderate or if the size of the Schur complemented system clearly exceeds the active dimension within the subspace giving rise to the cutting model of the bundle method.<\/jats:p>","DOI":"10.1007\/s10107-023-01986-w","type":"journal-article","created":{"date-parts":[[2023,6,15]],"date-time":"2023-06-15T16:02:17Z","timestamp":1686844937000},"page":"559-615","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A preconditioned iterative interior point approach to the conic bundle subproblem"],"prefix":"10.1007","volume":"205","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5288-8000","authenticated-orcid":false,"given":"Christoph","family":"Helmberg","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,6,15]]},"reference":[{"key":"1986_CR1","doi-asserted-by":"crossref","unstructured":"Achlioptas, D.: Database friendly random projections. In: Proceedings of 20th ACM Symposium on Principles of Database Systems, Santa Barabara, CA, pp. 274\u2013281 (2001)","DOI":"10.1145\/375551.375608"},{"issue":"3","key":"1986_CR2","doi-asserted-by":"publisher","first-page":"746","DOI":"10.1137\/S1052623496304700","volume":"8","author":"F Alizadeh","year":"1998","unstructured":"Alizadeh, F., Haeberly, J.-P.A., Overton, M.L.: Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM J. Optim. 8(3), 746\u2013768 (1998)","journal-title":"SIAM J. Optim."},{"key":"1986_CR3","series-title":"International Series in Operations Research & Management Science","volume-title":"Handbook of Semidefinite, Conic and Polynomial Optimization","year":"2012","unstructured":"Anjos, M.F., Lasserre, J.B. (eds.): Handbook of Semidefinite, Conic and Polynomial Optimization. International Series in Operations Research & Management Science, vol. 166. Springer, Berlin (2012)"},{"key":"1986_CR4","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/3-540-36626-1_4","volume-title":"Optimisation, Econometric and Financial Analysis","author":"F Babonneau","year":"2007","unstructured":"Babonneau, F., Beltran, C., Haurie, A., Tadonki, C., Vial, J.-P.: Proximal-ACCPM: a versatile oracle based optimisation method. In: Kontoghiorghes, E.J., Gatu, C. (eds.) Optimisation, Econometric and Financial Analysis, pp. 67\u201389. Springer, Berlin (2007)"},{"issue":"2","key":"1986_CR5","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1137\/S1052623497328008","volume":"10","author":"S Benson","year":"2000","unstructured":"Benson, S., Ye, Y., Zhang, X.: Solving large-scale sparse semidefinite programs for combinatorial optimization. SIAM J. Optim. 10(2), 443\u2013461 (2000)","journal-title":"SIAM J. Optim."},{"key":"1986_CR6","volume-title":"Numerical Optimization","author":"JF Bonnans","year":"2006","unstructured":"Bonnans, J.F., Gilbert, J.C., Lemar\u00e9chal, C., Sagastiz\u00e1bal, C.A.: Numerical Optimization, 2nd edn. Springer, Berlin (2006)","edition":"2"},{"key":"1986_CR7","doi-asserted-by":"crossref","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004). Reprinted 2007 with corrections","DOI":"10.1017\/CBO9780511804441"},{"key":"1986_CR8","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1007\/s10107-002-0352-8","volume":"94","author":"S Burer","year":"2003","unstructured":"Burer, S., Monteiro, R.D.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 94, 329\u2013357 (2003)","journal-title":"Math. Program."},{"issue":"1","key":"1986_CR9","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1002\/rsa.10073","volume":"22","author":"S Dasgupta","year":"2002","unstructured":"Dasgupta, S., Gupta, A.: An elementary proof of a theorem of Johnson and Lindenstrauss. Random Struct. Algorithms 22(1), 60\u201365 (2002). https:\/\/doi.org\/10.1002\/rsa.10073","journal-title":"Random Struct. Algorithms"},{"key":"1986_CR10","unstructured":"Ding, L., Grimmer, B.: Revisit of spectral bundle methods: Primal-dual (sub)linear convergence rates (2020). arXiv:2008.07067"},{"issue":"2","key":"1986_CR11","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s101070100263","volume":"91","author":"E Dolan","year":"2002","unstructured":"Dolan, E., Mor\u00e9, J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201\u2013213 (2002)","journal-title":"Math. Program."},{"key":"1986_CR12","doi-asserted-by":"crossref","unstructured":"Elman, H.C., Silvester, D.J., Wathen, A.J.: Finite Elements and Fast Iterative Solvers: With Applications in Incompressible Fluid Dynamics. Oxford University Press, Oxford (2005). Reprinted 2006","DOI":"10.1093\/oso\/9780198528678.001.0001"},{"issue":"1\u20132","key":"1986_CR13","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1007\/s10107-012-0610-3","volume":"143","author":"F Fischer","year":"2014","unstructured":"Fischer, F., Helmberg, C.: Dynamic graph generation for the shortest path problem in time expanded networks. Math. Program. 143(1\u20132), 257\u2013297 (2014)","journal-title":"Math. Program."},{"issue":"2","key":"1986_CR14","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1137\/120865987","volume":"24","author":"F Fischer","year":"2014","unstructured":"Fischer, F., Helmberg, C.: A parallel bundle framework for asynchronous subspace optimisation of nonsmooth convex functions. SIAM J. Optim. 24(2), 795\u2013822 (2014)","journal-title":"SIAM J. Optim."},{"key":"1986_CR15","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":"1986_CR16","unstructured":"Habibi, S., Kavand, A., Kocvara, M., Stingl, M.: Barrier and penalty methods for low-rank semidefinite programming with application to truss topology design (2021). arXiv:2105.08529"},{"issue":"2","key":"1986_CR17","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1137\/090771806","volume":"53","author":"N Halko","year":"2011","unstructured":"Halko, N., Martinsson, P.G., Tropp, J.A.: Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Rev. 53(2), 217\u2013288 (2011)","journal-title":"SIAM Rev."},{"key":"1986_CR18","series-title":"MPS-SIAM Series on Optimization","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1137\/1.9780898718805.ch15","volume-title":"The Sharpest Cut","author":"C Helmberg","year":"2004","unstructured":"Helmberg, C.: A cutting plane algorithm for large scale semidefinite relaxations. In: Gr\u00f6tschel, M. (ed.) The Sharpest Cut. MPS-SIAM Series on Optimization, pp. 233\u2013256. SIAM\/MPS, Philadelphia (2004)"},{"key":"1986_CR19","unstructured":"Helmberg, C.: ConicBundle v1.a.2. Fakult\u00e4t f\u00fcr Mathematik, Technische Universit\u00e4t Chemnitz (2021). http:\/\/www.tu-chemnitz.de\/~helmberg\/ConicBundle"},{"key":"1986_CR20","unstructured":"Helmberg, C.: Supplement scientific data to publicaton \u201cA preconditioned iterative interior point approach to the conic bundle subproblem\". TU Chemnitz (2023). https:\/\/tucid.tu-chemnitz.de\/data\/7bd7800c66774f7b954c105673e8e383 (persistent id)"},{"issue":"2","key":"1986_CR21","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/s101070100270","volume":"93","author":"C Helmberg","year":"2002","unstructured":"Helmberg, C., Kiwiel, K.C.: A spectral bundle method with bounds. Math. Program. 93(2), 173\u2013194 (2002)","journal-title":"Math. Program."},{"key":"1986_CR22","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1080\/03081089508818381","volume":"39","author":"C Helmberg","year":"1995","unstructured":"Helmberg, C., Mohar, B., Poljak, S., Rendl, F.: A spectral approach to bandwidth and separator problems in graphs. Linear Multilinear Algebra 39, 73\u201390 (1995)","journal-title":"Linear Multilinear Algebra"},{"issue":"4","key":"1986_CR23","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1080\/10556788.2013.858155","volume":"29","author":"C Helmberg","year":"2014","unstructured":"Helmberg, C., Overton, M.L., Rendl, F.: The spectral bundle method with second-order information. Optim. Methods Softw. 29(4), 855\u2013876 (2014)","journal-title":"Optim. Methods Softw."},{"key":"1986_CR24","unstructured":"Helmberg, C., Pichler, A.: Dynamic scaling and submodel selection in bundle methods for convex optimization. Preprint 2017, Fakult\u00e4t f\u00fcr Mathematik, Technische Universit\u00e4t Chemnitz, Chemnitz (2017)"},{"issue":"3","key":"1986_CR25","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/BF01580072","volume":"82","author":"C Helmberg","year":"1998","unstructured":"Helmberg, C., Rendl, F.: Solving quadratic (0,1)-problems by semidefinite programs and cutting planes. Math. Program. 82(3), 291\u2013315 (1998)","journal-title":"Math. Program."},{"issue":"3","key":"1986_CR26","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1137\/S1052623497328987","volume":"10","author":"C Helmberg","year":"2000","unstructured":"Helmberg, C., Rendl, F.: A spectral bundle method for semidefinite programming. SIAM J. Optim. 10(3), 673\u2013696 (2000)","journal-title":"SIAM J. Optim."},{"key":"1986_CR27","series-title":"Series on Optimization and Its Applications","doi-asserted-by":"crossref","DOI":"10.1142\/q0252","volume-title":"The Moment-SOS Hierarchy","author":"D Henrion","year":"2020","unstructured":"Henrion, D., Korda, M., Lasserre, H.B.: The Moment-SOS Hierarchy. Series on Optimization and Its Applications, vol. 4. World Scientific, Singapore (2020)"},{"issue":"1","key":"1986_CR28","doi-asserted-by":"publisher","first-page":"A59","DOI":"10.1137\/18M1182802","volume":"41","author":"NJ Higham","year":"2019","unstructured":"Higham, N.J., Mary, T.: A new preconditioner that exploits low-rank approximations to factorization error. SIAM J. Sci. Comput. 41(1), A59\u2013A82 (2019)","journal-title":"SIAM J. Sci. Comput."},{"key":"1986_CR29","volume-title":"Convex Analysis and Minimization Algorithms I. Grundlehren der Mathematischen Wissenschaften","author":"J-B Hiriart-Urruty","year":"1993","unstructured":"Hiriart-Urruty, J.-B., Lemar\u00e9chal, C.: Convex Analysis and Minimization Algorithms I. Grundlehren der Mathematischen Wissenschaften, vol. 305. Springer, Berlin (1993)"},{"key":"1986_CR30","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":"1986_CR31","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/s10107-010-0402-6","volume":"129","author":"S Kim","year":"2011","unstructured":"Kim, S., Kojima, M., Mevissen, M., Yamashita, M.: Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion. Math. Program. 129, 33\u201368 (2011)","journal-title":"Math. Program."},{"issue":"2\u20133","key":"1986_CR32","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(2\u20133), 413\u2013444 (2007)","journal-title":"Math. Program."},{"key":"1986_CR33","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1137\/S1052623495290209","volume":"8","author":"Y Nesterov","year":"1998","unstructured":"Nesterov, Y., Todd, M.J.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8, 324\u2013364 (1998)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"1986_CR34","doi-asserted-by":"publisher","first-page":"1029","DOI":"10.1137\/S1052623400374148","volume":"13","author":"MR Oskoorouchi","year":"2003","unstructured":"Oskoorouchi, M.R., Goffin, J.-L.: The analytic center cutting plane method with semidefinite cuts. SIAM J. Optim. 13(4), 1029\u20131053 (2003)","journal-title":"SIAM J. Optim."},{"key":"1986_CR35","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1006\/jcss.2000.1711","volume":"61","author":"CH Papadimitriou","year":"2000","unstructured":"Papadimitriou, C.H., Raghavan, P., Tamaki, H., Vempala, S.: Latent semantic indexing: a probabilistic analysis. J. Comput. Syst. Sci. 61, 217\u2013235 (2000). https:\/\/doi.org\/10.1006\/jcss.2000.1711","journal-title":"J. Comput. Syst. Sci."},{"key":"1986_CR36","unstructured":"Rinaldi, G.: A rudimental graph generator by JRT (1993). https:\/\/www.tu-chemnitz.de\/~helmberg\/rudy.tar.gz"},{"key":"1986_CR37","doi-asserted-by":"publisher","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"RT Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)"},{"issue":"3","key":"1986_CR38","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(3), 769\u2013796 (1998)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1986_CR39","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s10107-006-0088-y","volume":"112","author":"K-C Toh","year":"2008","unstructured":"Toh, K.-C.: An inexact primal-dual path following algorithm for convex quadratic SDP. Math. Program. 112(1), 221\u2013254 (2008)","journal-title":"Math. Program."},{"key":"1986_CR40","series-title":"International Series in Operations Research and Management Science","volume-title":"Handbook of Semidefinite Programming","year":"2000","unstructured":"Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook of Semidefinite Programming. International Series in Operations Research and Management Science, vol. 27. Kluwer Academic Publishers, Boston (2000)"},{"key":"1986_CR41","doi-asserted-by":"crossref","unstructured":"Zhang, R.Y., Lavaei, J.: Modified interior-point method for large-and-sparse low-rank semidefinite programs. In: 2017 IEE 56th Conference on Decision and Control (CDC), pp. 5640\u20135647. Melbourne, Australia, December 12\u201315 (2017)","DOI":"10.1109\/CDC.2017.8264510"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01986-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-01986-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01986-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T14:15:30Z","timestamp":1712412930000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-01986-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,15]]},"references-count":41,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1986"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-01986-w","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2023,6,15]]},"assertion":[{"value":"25 October 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 May 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 June 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}