{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:24:44Z","timestamp":1740122684112,"version":"3.37.3"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T00:00:00Z","timestamp":1733097600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T00:00:00Z","timestamp":1733097600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Several manifold optimization schemes are presented and analyzed for solving a specialized inverse structured symmetric matrix problem with prescribed spectrum. Some entries in the desired matrix are assigned in advance and cannot be altered. The rest of the entries are free, some of them preferably away from zero. The reconstructed matrix must satisfy these requirements and its eigenvalues must be the given ones. This inverse eigenvalue problem is related to the problem of determining the graph, with weights on the undirected edges, of the matrix associated with its sparse pattern. Our optimization schemes are based on considering the eigenvector matrix as the only unknown and iteratively moving on the manifold of orthogonal matrices, forcing the additional structural requirements through a change of variables and a convenient differentiable objective function in the space of square matrices. We propose Riemannian gradient-type methods combined with two different well-known retractions, and with two well-known constrained optimization strategies: penalization and augmented Lagrangian. We also present a block alternating technique that takes advantage of a proper separation of variables. Convergence properties of the penalty alternating approach are established. Finally, we present initial numerical results to demonstrate the effectiveness of our proposals.<\/jats:p>","DOI":"10.1007\/s10589-024-00630-3","type":"journal-article","created":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T03:56:21Z","timestamp":1733111781000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimization schemes on manifolds for structured matrices with fixed eigenvalues"],"prefix":"10.1007","volume":"90","author":[{"given":"Jean-Paul","family":"Chehab","sequence":"first","affiliation":[]},{"given":"Harry","family":"Oviedo","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0417-7981","authenticated-orcid":false,"given":"Marcos","family":"Raydan","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,12,2]]},"reference":[{"key":"630_CR1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400830244","volume-title":"Optimization Algorithms on Matrix Manifolds","author":"PA Absil","year":"2008","unstructured":"Absil, P.A., Mahony, R., Sepulchre, R.: Optimization Algorithms on Matrix Manifolds. Princeton University Press, Princeton (2008). https:\/\/doi.org\/10.1515\/9781400830244"},{"issue":"5","key":"630_CR2","doi-asserted-by":"publisher","first-page":"1675","DOI":"10.1088\/0266-5611\/20\/5\/022","volume":"20","author":"Z-J Bai","year":"2004","unstructured":"Bai, Z.-J., Chan, R.H., Morini, B.: An inexact Cayley transform method for inverse eigenvalue problems. Inverse Problems 20(5), 1675 (2004). https:\/\/doi.org\/10.1088\/0266-5611\/20\/5\/022","journal-title":"Inverse Problems"},{"key":"630_CR3","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1016\/j.cam.2005.06.050","volume":"198","author":"Z-J Bai","year":"2007","unstructured":"Bai, Z.-J., Morini, B., Xu, S.-F.: On the local convergence of an iterative approach for inverse singular value problems. J. Comput. Appl. Math. 198, 344\u2013360 (2007). https:\/\/doi.org\/10.1016\/j.cam.2005.06.050","journal-title":"J. Comput. Appl. Math."},{"key":"630_CR4","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.M.: Two-point step size gradient methods, IMA. J. Numer. Anal. 8, 141\u2013148 (1988). https:\/\/doi.org\/10.1093\/imanum\/8.1.141","journal-title":"J. Numer. Anal."},{"issue":"1","key":"630_CR5","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1137\/13094829X","volume":"25","author":"A Beck","year":"2015","unstructured":"Beck, A.: On the convergence of alternating minimization for convex programming with applications to iteratively reweighted least squares and decomposition schemes. SIAM J. Optim. 25(1), 185\u2013209 (2015). https:\/\/doi.org\/10.1137\/13094829X","journal-title":"SIAM J. Optim."},{"key":"630_CR6","volume-title":"Constrained optimization and Lagrange Multiplier Methods","author":"D Bertsekas","year":"1982","unstructured":"Bertsekas, D.: Constrained optimization and Lagrange Multiplier Methods. Academic Press, New York (1982)"},{"key":"630_CR7","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973365","volume-title":"Practical Augmented Lagrangian Methods for Constrained Optimization","author":"E Birgin","year":"2014","unstructured":"Birgin, E., Mart\u00ednez, J.M.: Practical Augmented Lagrangian Methods for Constrained Optimization. SIAM, Philadelphia (2014)"},{"key":"630_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/9781009166164","volume-title":"An Introduction to Optimization on Smooth Manifolds","author":"N Boumal","year":"2023","unstructured":"Boumal, N.: An Introduction to Optimization on Smooth Manifolds. Cambridge University Press, Cambridge (2023). https:\/\/doi.org\/10.1017\/9781009166164"},{"key":"630_CR9","volume-title":"Spectra of Graphs","author":"D Cvetkovi\u0107","year":"1995","unstructured":"Cvetkovi\u0107, D., Doob, M., Sachs, H.: Spectra of Graphs, 3rd edn. Johann Ambrosius Barth Verlag, Leipzig (1995)","edition":"3"},{"key":"630_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801518","volume-title":"An Introduction to the Theory of Graph Spectra","author":"D Cvetkovi\u0107","year":"2009","unstructured":"Cvetkovi\u0107, D., Rowlinson, P., Simi\u0107, S.L.: An Introduction to the Theory of Graph Spectra. Cambridge University Press, Cambridge (2009). https:\/\/doi.org\/10.1017\/CBO9780511801518"},{"issue":"1","key":"630_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0036144596303984","volume":"40","author":"MT Chu","year":"1998","unstructured":"Chu, M.T.: Inverse eigenvalue problems. SIAM Rev. 40(1), 1\u201339 (1998). https:\/\/doi.org\/10.1137\/S0036144596303984","journal-title":"SIAM Rev."},{"issue":"1","key":"630_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0962492902000014","volume":"1","author":"MT Chu","year":"2002","unstructured":"Chu, M.T., Golub, G.H.: Structured inverse eigenvalue problems. Acta Numer. 1(1), 1\u201371 (2002). https:\/\/doi.org\/10.1017\/S0962492902000014","journal-title":"Acta Numer."},{"key":"630_CR13","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1007\/s10915-015-0048-x","volume":"66","author":"W Deng","year":"2016","unstructured":"Deng, W., Yin, W.: On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66, 889\u2013916 (2016). https:\/\/doi.org\/10.1007\/s10915-015-0048-x","journal-title":"J. Sci. Comput."},{"issue":"4","key":"630_CR14","first-page":"619","volume":"11","author":"J Eckstein","year":"2015","unstructured":"Eckstein, J., Yao, W.: Understanding the convergence of the alternating direction method of multipliers: Theoretical and computational perspectives. Pac. J. Optim. 11(4), 619\u2013644 (2015)","journal-title":"Pac. J. Optim."},{"issue":"2","key":"630_CR15","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1137\/S0895479895290954","volume":"20","author":"A Edelman","year":"1998","unstructured":"Edelman, A., Arias, T., Smith, S.: The geometry of algorithms with orthogonality constraints. SIAM J. Matrix Anal. Appl. 20(2), 303\u2013353 (1998). https:\/\/doi.org\/10.1137\/S0895479895290954","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"630_CR16","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/0166-218X(88)90012-1","volume":"19","author":"H Galina","year":"1988","unstructured":"Galina, H., Syslo, M.M.: Some applications of graph theory to the study of polymer configuration. Discret. Appl. Math. 19, 167\u2013176 (1988). https:\/\/doi.org\/10.1016\/0166-218X(88)90012-1","journal-title":"Discret. Appl. Math."},{"issue":"1\u20132","key":"630_CR17","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s10107-016-1034-2","volume":"162","author":"M Hong","year":"2017","unstructured":"Hong, M., Luo, Z.: On the linear convergence of the alternating direction method of multipliers. Math. Program. 162(1\u20132), 165\u2013199 (2017). https:\/\/doi.org\/10.1007\/s10107-016-1034-2","journal-title":"Math. Program."},{"key":"630_CR18","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s40305-020-00295-9","volume":"8","author":"J Hu","year":"2020","unstructured":"Hu, J., Liu, X., Wen, Z., Yuan, Y.-X.: A brief introduction to manifold optimization. J. Oper. Res. Soc. China 8, 199\u2013248 (2020). https:\/\/doi.org\/10.1007\/s40305-020-00295-9","journal-title":"J. Oper. Res. Soc. China"},{"issue":"1","key":"630_CR19","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1093\/imanum\/drx015","volume":"38","author":"B Iannazzo","year":"2018","unstructured":"Iannazzo, B., Porcelli, M.: The Riemannian Barzilai\u2013Borwein method with nonmonotone line search and the matrix geometric mean computation. IMA J. Numer. Anal. 38(1), 495\u2013517 (2018). https:\/\/doi.org\/10.1093\/imanum\/drx015","journal-title":"IMA J. Numer. Anal."},{"issue":"2","key":"630_CR20","doi-asserted-by":"publisher","first-page":"535","DOI":"10.1007\/s10107-014-0816-7","volume":"153","author":"B Jiang","year":"2015","unstructured":"Jiang, B., Dai, Y.-H.: A framework of constraint preserving update schemes for optimization on Stiefel manifold. Math. Program. 153(2), 535\u2013575 (2015). https:\/\/doi.org\/10.1007\/s10107-014-0816-7","journal-title":"Math. Program."},{"key":"630_CR21","doi-asserted-by":"publisher","DOI":"10.1017\/9781316155158","volume-title":"Eigenvalues, Multiplicities and Graphs","author":"CR Johnson","year":"2018","unstructured":"Johnson, C.R., Saiago, C.M.: Eigenvalues, Multiplicities and Graphs, vol. 211. Cambridge University Press, Cambridge (2018). https:\/\/doi.org\/10.1017\/9781316155158"},{"doi-asserted-by":"crossref","unstructured":"Kovnatsky, A., Glashoff, K., Bronstein, M.: MADMM: a generic algorithm for non-smooth optimization on manifolds. In: Computer Vision-ECCV 2016, 14th European Conference, Amsterdam, The Netherlands, October 11\u201314, 2016, Proceedings, Part V14, pp. 680\u2013696 (2016)","key":"630_CR22","DOI":"10.1007\/978-3-319-46454-1_41"},{"key":"630_CR23","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s10915-013-9740-x","volume":"58","author":"R Lai","year":"2014","unstructured":"Lai, R., Osher, S.: A splitting method for orthogonality constrained problems. J. Sci. Comput. 58, 431\u2013449 (2014). https:\/\/doi.org\/10.1007\/s10915-013-9740-x","journal-title":"J. Sci. Comput."},{"unstructured":"Li, J., Ma, S., Srivastava, T.: A Riemannian ADMM. arXiv preprint arXiv:2211.02163 (2022)","key":"630_CR24"},{"key":"630_CR25","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-74503-9","volume-title":"Linear and Nonlinear Programming","author":"DG Luenberger","year":"1984","unstructured":"Luenberger, D.G.: Linear and Nonlinear Programming. Addison-Wesley, Menlo Park, CA (1984). https:\/\/doi.org\/10.1007\/978-0-387-74503-9"},{"doi-asserted-by":"publisher","unstructured":"Lu, C., Feng, J., Lin, Z., Yan, S.: Nonconvex sparse spectral clustering by alternating direction method of multipliers and its convergence analysis. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32, no. 1. https:\/\/doi.org\/10.1609\/aaai.v32i1.11658 (2018)","key":"630_CR26","DOI":"10.1609\/aaai.v32i1.11658"},{"issue":"2","key":"630_CR27","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1080\/10556788.2017.1415337","volume":"34","author":"H Oviedo","year":"2019","unstructured":"Oviedo, H., Lara, H., Dalmau, O.: A non-monotone linear search algorithm with mixed direction on Stiefel manifold. Optim. Methods Softw. 34(2), 437\u2013457 (2019). https:\/\/doi.org\/10.1080\/10556788.2017.1415337","journal-title":"Optim. Methods Softw."},{"issue":"238","key":"630_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s40314-021-01630-3","volume":"40","author":"H Oviedo","year":"2021","unstructured":"Oviedo, H., Lara, H.: Spectral residual method for nonlinear equations on Riemannian manifolds. Comput. Appl. Math. 40(238), 1\u201323 (2021). https:\/\/doi.org\/10.1007\/s40314-021-01630-3","journal-title":"Comput. Appl. Math."},{"key":"630_CR29","doi-asserted-by":"publisher","first-page":"1107","DOI":"10.1007\/s11075-020-01001-9","volume":"87","author":"H Oviedo","year":"2021","unstructured":"Oviedo, H., Lara, H., Dalmau, O.: Two adaptive scaled gradient projection methods for Stiefel manifold constrained optimization. Numer. Algorithms 87, 1107\u20131127 (2021). https:\/\/doi.org\/10.1007\/s11075-020-01001-9","journal-title":"Numer. Algorithms"},{"issue":"3","key":"630_CR30","doi-asserted-by":"publisher","first-page":"1183","DOI":"10.1007\/s11075-022-01298-8","volume":"91","author":"H Oviedo","year":"2022","unstructured":"Oviedo, H.: Global convergence of Riemannian line search methods with a Zhang-Hager-type condition. Numer. Algorithms 91(3), 1183\u20131203 (2022). https:\/\/doi.org\/10.1007\/s11075-022-01298-8","journal-title":"Numer. Algorithms"},{"issue":"11","key":"630_CR31","doi-asserted-by":"publisher","first-page":"2414","DOI":"10.3390\/math11112414","volume":"11","author":"H Oviedo","year":"2023","unstructured":"Oviedo, H.: Proximal point algorithm with Euclidean distance on the Stiefel manifold. Mathematics 11(11), 2414 (2023). https:\/\/doi.org\/10.3390\/math11112414","journal-title":"Mathematics"},{"issue":"3","key":"630_CR32","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1561\/2400000003","volume":"1","author":"N Parikh","year":"2014","unstructured":"Parikh, N., Boyd, S.: Proximal algorithms. Found. Trends Optim. 1(3), 127\u2013239 (2014). https:\/\/doi.org\/10.1561\/2400000003","journal-title":"Found. Trends Optim."},{"doi-asserted-by":"publisher","unstructured":"Plumbley, M.: Lie group methods for optimization with orthogonality constraints. In: Independent Component Analysis and Blind Signal Separation: Fifth International Conference, ICA 2004, Granada, Spain, September 22\u201324, 2004. Proceedings 5, pp. 1245\u20131252. Springer, Berlin Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30110-3_157","key":"630_CR33","DOI":"10.1007\/978-3-540-30110-3_157"},{"issue":"2","key":"630_CR34","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1080\/10556788.2012.700713","volume":"29","author":"Y Shen","year":"2014","unstructured":"Shen, Y., Wen, Z., Zhang, Y.: Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization. Optim. Methods Softw. 29(2), 239\u2013263 (2014). https:\/\/doi.org\/10.1080\/10556788.2012.700713","journal-title":"Optim. Methods Softw."},{"issue":"18","key":"630_CR35","doi-asserted-by":"publisher","first-page":"3419","DOI":"10.1080\/03081087.2020.1841077","volume":"70","author":"G Steidl","year":"2022","unstructured":"Steidl, G., Winklery, M.: A new constrained optimization model for solving the nonsymmetric stochastic inverse eigenvalue problem. Linear Multilinear Algebra 70(18), 3419\u20133448 (2022). https:\/\/doi.org\/10.1080\/03081087.2020.1841077","journal-title":"Linear Multilinear Algebra"},{"doi-asserted-by":"crossref","unstructured":"Sun, D.L., Fevotte, C.: Alternating direction method of multipliers for non-negative matrix factorization with the beta-divergence. In: 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6201\u20136205 (2014)","key":"630_CR36","DOI":"10.1109\/ICASSP.2014.6854796"},{"key":"630_CR37","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1515\/spma-2019-0020","volume":"7","author":"B Sutton","year":"2019","unstructured":"Sutton, B.: Numerical construction of structured matrices with given eigenvalues. Spec. Matrices 7, 263\u2013271 (2019). https:\/\/doi.org\/10.1515\/spma-2019-0020","journal-title":"Spec. Matrices"},{"key":"630_CR38","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1021\/ci00018a023","volume":"34","author":"N Trinajsti\u0107","year":"1994","unstructured":"Trinajsti\u0107, N., Babi\u0107, D., Nikoli\u0107, S., Plav\u0161i\u0107, D., Ami\u0107, D., Mihali\u0107, Z.: The Laplacian matrix in chemistry. J. Chem. Inf. Comput. Sci. 34, 368\u2013376 (1994). https:\/\/doi.org\/10.1021\/ci00018a023","journal-title":"J. Chem. Inf. Comput. Sci."},{"key":"630_CR39","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511815478","volume-title":"Social networks analysis- methods and applications","author":"S Wasserman","year":"1994","unstructured":"Wasserman, S., Kaust, K.: Social networks analysis- methods and applications. Cambridge University Press, Cambridge (1994). https:\/\/doi.org\/10.1017\/CBO9780511815478"},{"key":"630_CR40","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/s10107-012-0584-1","volume":"142","author":"Z Wen","year":"2013","unstructured":"Wen, Z., Yin, W.: A feasible method for optimization with orthogonality constraints. Math. Program. 142, 397\u2013434 (2013). https:\/\/doi.org\/10.1007\/s10107-012-0584-1","journal-title":"Math. Program."},{"key":"630_CR41","doi-asserted-by":"publisher","DOI":"10.1002\/nla.2221","volume":"26","author":"T-T Yao","year":"2019","unstructured":"Yao, T.-T., Bai, Z.-J., Zhao, Z.: A Riemannian variant of the Fletcher\u2013Reeves conjugate gradient method for stochastic inverse eigenvalue problems with partial eigendata. Numer Linear Algebra Appl. 26, e2221 (2019). https:\/\/doi.org\/10.1002\/nla.2221","journal-title":"Numer Linear Algebra Appl."},{"key":"630_CR42","doi-asserted-by":"publisher","first-page":"1043","DOI":"10.1137\/S1052623403428208","volume":"14","author":"H Zhang","year":"2004","unstructured":"Zhang, H., Hager, W.W.: A nonmonotone line search technique and its application to unconstrained optimization. SIAM J. Optim. 14, 1043\u20131056 (2004). https:\/\/doi.org\/10.1137\/S1052623403428208","journal-title":"SIAM J. Optim."},{"issue":"4","key":"630_CR43","doi-asserted-by":"publisher","first-page":"2015","DOI":"10.1137\/140992576","volume":"54","author":"Z Zhao","year":"2016","unstructured":"Zhao, Z., Jin, X.-Q., Bai, Z.-J.: A geometric nonlinear conjugate gradient method for stochastic inverse eigenvalue problems. SIAM J. Numer. Anal. 54(4), 2015\u20132035 (2016). https:\/\/doi.org\/10.1137\/140992576","journal-title":"SIAM J. Numer. Anal."}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-024-00630-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-024-00630-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-024-00630-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,13]],"date-time":"2025-01-13T12:32:52Z","timestamp":1736771572000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-024-00630-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,2]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["630"],"URL":"https:\/\/doi.org\/10.1007\/s10589-024-00630-3","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"type":"print","value":"0926-6003"},{"type":"electronic","value":"1573-2894"}],"subject":[],"published":{"date-parts":[[2024,12,2]]},"assertion":[{"value":"3 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 November 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"No potential conflict of interest was reported by the authors.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"All authors read and approved the submission of the final manuscript.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}}]}}