{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T07:56:12Z","timestamp":1777362972815,"version":"3.51.4"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T00:00:00Z","timestamp":1766361600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T00:00:00Z","timestamp":1766361600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000147","name":"Division of Civil, Mechanical and Manufacturing Innovation","doi-asserted-by":"publisher","award":["2246414"],"award-info":[{"award-number":["2246414"]}],"id":[{"id":"10.13039\/100000147","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-24-1-2066"],"award-info":[{"award-number":["N00014-24-1-2066"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2026,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>A Low-rank Spectral Optimization Problem (LSOP) minimizes a linear objective function subject to multiple two-sided linear inequalities intersected with a low-rank and spectral constrained domain. Although solving LSOP is generally NP-hard, its partial convexification (i.e., replacing the domain with its convex hull), termed \u201cLSOP-R,\" is often tractable and yields a high-quality solution. This motivates us to study the strength of LSOP-R. Specifically, we derive rank bounds for any extreme point of LSOP-R in different matrix spaces and prove their tightness. The proposed rank bounds recover two well-known results in the literature from a fresh angle and allow us to derive sufficient conditions under which the relaxation LSOP-R is equivalent to LSOP. To effectively solve LSOP-R, we develop a column generation algorithm with a vector-based convex pricing oracle and a rank-reduction algorithm, which ensures that the output solution always satisfies the theoretical rank bound. Finally, we numerically verify the strength of LSOP-R and the efficacy of the proposed algorithms.<\/jats:p>","DOI":"10.1007\/s10107-025-02316-y","type":"journal-article","created":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T09:24:31Z","timestamp":1766395471000},"page":"651-708","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On the partial convexification for low-rank spectral optimization: rank bounds and algorithms"],"prefix":"10.1007","volume":"216","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1938-377X","authenticated-orcid":false,"given":"Yongchun","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5157-1194","authenticated-orcid":false,"given":"Weijun","family":"Xie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,12,22]]},"reference":[{"key":"2316_CR1","unstructured":"Amor, H.\u00a0B., Desrosiers, J., Frangioni, A.: Stabilization in column generation. Groupe d\u2019\u00e9tudes et de recherche en analyse des d\u00e9cisions, (2004)"},{"issue":"6","key":"2316_CR2","doi-asserted-by":"publisher","first-page":"1167","DOI":"10.1016\/j.dam.2008.06.021","volume":"157","author":"HMB Amor","year":"2009","unstructured":"Amor, H.M.B., Desrosiers, J., Frangioni, A.: On the choice of explicit stabilizing terms in column generation. Discret. Appl. Math. 157(6), 1167\u20131184 (2009)","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"2316_CR3","doi-asserted-by":"publisher","first-page":"514","DOI":"10.1137\/21M1398677","volume":"4","author":"A Askari","year":"2022","unstructured":"Askari, A., d\u2019Aspremont, A., Ghaoui, L.E.: Approximation bounds for sparse programs. SIAM Journal on Mathematics of Data Science 4(2), 514\u2013530 (2022)","journal-title":"SIAM Journal on Mathematics of Data Science"},{"issue":"2","key":"2316_CR4","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1007\/BF02574037","volume":"13","author":"AI Barvinok","year":"1995","unstructured":"Barvinok, A.I.: Problems of distance geometry and convex properties of quadratic maps. Discrete & Computational Geometry 13(2), 189\u2013202 (1995)","journal-title":"Discrete & Computational Geometry"},{"key":"2316_CR5","doi-asserted-by":"crossref","unstructured":"Bedoya, J.\u00a0C., Abdelhadi, A., Liu, C.-C., Dubey, A.: A qcqp and sdp formulation of the optimal power flow including renewable energy resources. In 2019 International Symposium on Systems Engineering (ISSE), pages 1\u20138. IEEE, (2019)","DOI":"10.1109\/ISSE46696.2019.8984430"},{"key":"2316_CR6","doi-asserted-by":"crossref","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM, (2001)","DOI":"10.1137\/1.9780898718829"},{"key":"2316_CR7","doi-asserted-by":"crossref","unstructured":"Bertsimas, D., Cory-Wright, R., Pauphilet, J.: A new perspective on low-rank optimization. Math. Program. 202(1),47 -92 (2023)","DOI":"10.1007\/s10107-023-01933-9"},{"key":"2316_CR8","unstructured":"Bohnenblust, F.: Joint positiveness of matrices. Unpublished manuscript, 48, (1948)"},{"issue":"2","key":"2316_CR9","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.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95(2), 329\u2013357 (2003)","journal-title":"Math. Program."},{"issue":"3","key":"2316_CR10","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.: Local minima and convergence in low-rank semidefinite programming. Math. Program. 103(3), 427\u2013444 (2005)","journal-title":"Math. Program."},{"issue":"1","key":"2316_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-019-01367-2","volume":"181","author":"S Burer","year":"2020","unstructured":"Burer, S., Ye, Y.: Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs. Math. Program. 181(1), 1\u201317 (2020)","journal-title":"Math. Program."},{"issue":"4","key":"2316_CR12","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(4), 1956\u20131982 (2010)","journal-title":"SIAM J. Optim."},{"key":"2316_CR13","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1007\/s101070050106","volume":"86","author":"S Ceria","year":"1999","unstructured":"Ceria, S., Soares, J.: Convex programming for disjunctive convex optimization. Math. Program. 86, 595\u2013614 (1999)","journal-title":"Math. Program."},{"key":"2316_CR14","doi-asserted-by":"crossref","unstructured":"Chakraborty, S., Zhou, J., Balasubramanian, V., Panchanathan, S., Davidson, I., Ye,J.: Active matrix completion. In 2013 IEEE 13th international conference on data mining, pages 81\u201390. IEEE, (2013)","DOI":"10.1109\/ICDM.2013.69"},{"key":"2316_CR15","doi-asserted-by":"crossref","unstructured":"Desrosiers, J., L\u00fcbbecke, M.\u00a0E.: A primer in column generation. In Column generation, pages 1\u201332. Springer, (2005)","DOI":"10.1007\/0-387-25486-2_1"},{"key":"2316_CR16","doi-asserted-by":"crossref","unstructured":"Deza, M.\u00a0M., Laurent, M., Weismantel, R.: Geometry of cuts and metrics, volume\u00a02. Springer, (1997)","DOI":"10.1007\/978-3-642-04295-9"},{"key":"2316_CR17","unstructured":"Drusvyatskiy, D., Kempton, C.: Variational analysis of spectral functions simplified. arXiv preprint arXiv:1506.05170, (2015)"},{"key":"2316_CR18","doi-asserted-by":"crossref","unstructured":"Eltved, A., Burer, S.: Strengthened sdp relaxation for an extended trust region subproblem with an application to optimal power flow. Mathematical Programming, pages 1\u201326, (2022)","DOI":"10.1007\/s10107-021-01737-9"},{"issue":"2","key":"2316_CR19","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1080\/0233193031000079856","volume":"52","author":"R Garc\u00eda","year":"2003","unstructured":"Garc\u00eda, R., Mar\u00edn, A., Patriksson, M.: Column generation algorithms for nonlinear optimization, i: Convergence analysis. Optimization 52(2), 171\u2013200 (2003)","journal-title":"Optimization"},{"key":"2316_CR20","doi-asserted-by":"crossref","unstructured":"Gharanjik, A., Shankar, B., Soltanalian, M., Oftersten, B.: An iterative approach to nonconvex qcqp with applications in signal processing. In 2016 IEEE Sensor Array and Multichannel Signal Processing Workshop (SAM), pages 1\u20135. IEEE, (2016)","DOI":"10.1109\/SAM.2016.7569622"},{"key":"2316_CR21","doi-asserted-by":"crossref","unstructured":"Ghate, A., Sharma, D., Smith, R.\u00a0L.: A shadow simplex method for infinite linear programs. Operations Research, 58(4-part-1):865\u2013877, (2010)","DOI":"10.1287\/opre.1090.0755"},{"key":"2316_CR22","unstructured":"Greub, W.\u00a0H.: Linear algebra, volume\u00a023. Springer Science & Business Media, (2012)"},{"key":"2316_CR23","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1023\/A:1025154322278","volume":"26","author":"IE Grossmann","year":"2003","unstructured":"Grossmann, I.E., Lee, S.: Generalized convex disjunctive programming: Nonlinear convex hull relaxation. Comput. Optim. Appl. 26, 83\u2013100 (2003)","journal-title":"Comput. Optim. Appl."},{"key":"2316_CR24","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s10107-010-0360-z","volume":"124","author":"O G\u00fcnl\u00fck","year":"2010","unstructured":"G\u00fcnl\u00fck, O., Linderoth, J.: Perspective reformulations of mixed integer nonlinear programs with indicator variables. Math. Program. 124, 183\u2013205 (2010)","journal-title":"Math. Program."},{"key":"2316_CR25","unstructured":"Hardy, G.\u00a0H., Littlewood, J.\u00a0E., P\u00f3lya, G., P\u00f3lya, G., et\u00a0al.: Inequalities. Cambridge university press, (1952)"},{"key":"2316_CR26","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1007\/s11590-011-0304-4","volume":"6","author":"J-B Hiriart-Urruty","year":"2012","unstructured":"Hiriart-Urruty, J.-B., Le, H.Y.: Convexifying the set of matrices of bounded rank: applications to the quasiconvexification and convexification of the rank function. Optimization Letters 6, 841\u2013849 (2012)","journal-title":"Optimization Letters"},{"key":"2316_CR27","unstructured":"Josz, C., Fliscounakis, S., Maeght, J., Panciatici,P.: Ac power flow data in matpower and qcqp format: itesla, rte snapshots, and pegase. arXiv preprint arXiv:1603.01533, (2016)"},{"key":"2316_CR28","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1109\/TSIPN.2019.2945631","volume":"6","author":"S Khobahi","year":"2019","unstructured":"Khobahi, S., Soltanalian, M., Jiang, F., Swindlehurst, A.L.: Optimized transmission for parameter estimation in wireless sensor networks. IEEE Transactions on Signal and Information Processing over Networks 6, 35\u201347 (2019)","journal-title":"IEEE Transactions on Signal and Information Processing over Networks"},{"key":"2316_CR29","unstructured":"K\u0131l\u0131n\u00e7-Karzan, F., Wang, A.\u00a0L.: Exactness in sdp relaxations of qcqps: Theory and applications. arXiv preprint arXiv:2107.06885, (2021)"},{"issue":"4","key":"2316_CR30","doi-asserted-by":"publisher","first-page":"2547","DOI":"10.1287\/moor.2021.1219","volume":"47","author":"J Kim","year":"2022","unstructured":"Kim, J., Tawarmalani, M., Richard, J.-P.P.: Convexification of permutation-invariant sets and an application to sparse principal component analysis. Math. Oper. Res. 47(4), 2547\u20132584 (2022)","journal-title":"Math. Oper. Res."},{"key":"2316_CR31","unstructured":"Kulis, B., Sustik, M.\u00a0A., Dhillon, I.\u00a0S.: Low-rank kernel learning with bregman matrix divergences. Journal of Machine Learning Research, 10(2), (2009)"},{"key":"2316_CR32","doi-asserted-by":"crossref","unstructured":"Lau, L.\u00a0C., Ravi, R., Singh, M.: Iterative methods in combinatorial optimization, volume\u00a046. Cambridge University Press, (2011)","DOI":"10.1017\/CBO9780511977152"},{"issue":"3","key":"2316_CR33","doi-asserted-by":"publisher","first-page":"576","DOI":"10.1287\/moor.21.3.576","volume":"21","author":"AS Lewis","year":"1996","unstructured":"Lewis, A.S.: Derivatives of spectral functions. Math. Oper. Res. 21(3), 576\u2013588 (1996)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"2316_CR34","doi-asserted-by":"publisher","first-page":"582","DOI":"10.1287\/ijoc.2022.0372","volume":"37","author":"Y Li","year":"2025","unstructured":"Li, Y., Xie, W.: Exact and approximation algorithms for sparse principal component analysis. INFORMS. J. Comput. 37(3), 582\u2013602 (2025)","journal-title":"INFORMS. J. Comput."},{"issue":"1","key":"2316_CR35","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10107-023-02030-7","volume":"208","author":"Y Li","year":"2024","unstructured":"Li, Y., Xie, W.: Beyond symmetry: Best submatrix selection for the sparse truncated svd. Math. Program. 208(1), 1\u201350 (2024)","journal-title":"Math. Program."},{"key":"2316_CR36","unstructured":"Li,Y., Xie, W.: On the exactness of dantzig-wolfe relaxation for rank constrained optimization problems. arXiv preprint arXiv:2210.16191, (2022)"},{"issue":"6","key":"2316_CR37","doi-asserted-by":"publisher","first-page":"1007","DOI":"10.1287\/opre.1050.0234","volume":"53","author":"ME L\u00fcbbecke","year":"2005","unstructured":"L\u00fcbbecke, M.E., Desrosiers, J.: Selected topics in column generation. Oper. Res. 53(6), 1007\u20131023 (2005)","journal-title":"Oper. Res."},{"key":"2316_CR38","unstructured":"Marshall, A.: Inequalities: Theory of majorization and its applications, (1979)"},{"key":"2316_CR39","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1109\/TIP.2021.3128321","volume":"31","author":"J Miao","year":"2021","unstructured":"Miao, J., Kou, K.I.: Color image recovery using low-rank quaternion matrix completion algorithm. IEEE Trans. Image Process. 31, 190\u2013201 (2021)","journal-title":"IEEE Trans. Image Process."},{"issue":"2","key":"2316_CR40","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1287\/moor.23.2.339","volume":"23","author":"G Pataki","year":"1998","unstructured":"Pataki, G.: On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23(2), 339\u2013358 (1998)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"2316_CR41","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1287\/ijoc.2017.0784","volume":"30","author":"A Pessoa","year":"2018","unstructured":"Pessoa, A., Sadykov, R., Uchoa, E., Vanderbeck, F.: Automation and combination of linear-programming based stabilization techniques in column generation. INFORMS J. Comput. 30(2), 339\u2013360 (2018)","journal-title":"INFORMS J. Comput."},{"key":"2316_CR42","unstructured":"Rockafellar, R.\u00a0T.: Convex analysis. Princeton university press, (1972)"},{"key":"2316_CR43","unstructured":"Samadi, S., Tantipongpipat, U., Morgenstern, J.\u00a0H., Singh, M., Vempala, S.: The price of fair pca: One extra dimension. Advances in neural information processing systems, 31, (2018)"},{"key":"2316_CR44","unstructured":"Tantipongpipat, U., Samadi, S., Singh, M., Morgenstern, J.\u00a0H., Vempala, S.: Multi-criteria dimensionality reduction with applications to fairness. Advances in neural information processing systems, 32, (2019)"},{"key":"2316_CR45","unstructured":"Vinyes,M., Obozinski, G.: Fast column generation for atomic norm regularization. In Artificial Intelligence and Statistics, pages 547\u2013556. PMLR, (2017)"},{"issue":"4","key":"2316_CR46","doi-asserted-by":"publisher","first-page":"3359","DOI":"10.1137\/19M1245414","volume":"30","author":"W Xie","year":"2020","unstructured":"Xie, W., Deng, X.: Scalable algorithms for the sparse ridge regression. SIAM J. Optim. 30(4), 3359\u20133386 (2020)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2316_CR47","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1109\/TSP.2010.2084997","volume":"59","author":"H Yu","year":"2010","unstructured":"Yu, H., Lau, V.K.: Rank-constrained schur-convex optimization with multiple trace\/log-det constraints. IEEE Trans. Signal Process. 59(1), 304\u2013314 (2010)","journal-title":"IEEE Trans. Signal Process."},{"key":"2316_CR48","doi-asserted-by":"crossref","unstructured":"Zhang, D., Hu, Y., Ye, J., Li, X., He, X.: Matrix completion by truncated nuclear norm regularization. In 2012 IEEE Conference on computer vision and pattern recognition, pages 2192\u20132199. IEEE, (2012)","DOI":"10.1109\/CVPR.2012.6247927"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02316-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-025-02316-y","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-025-02316-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T07:12:55Z","timestamp":1777360375000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-025-02316-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,22]]},"references-count":48,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2026,3]]}},"alternative-id":["2316"],"URL":"https:\/\/doi.org\/10.1007\/s10107-025-02316-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,22]]},"assertion":[{"value":"28 July 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"This research has been supported by the National Science Foundation, Office of Naval Research, and the Georgia Tech ARC-ACO fellowship. Authors have no other competing interests to report.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Funding and\/or Conflicts of interests\/Competing interests"}}]}}