{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T00:13:04Z","timestamp":1758845584708,"version":"3.37.3"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,10,27]],"date-time":"2020-10-27T00:00:00Z","timestamp":1603756800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,10,27]],"date-time":"2020-10-27T00:00:00Z","timestamp":1603756800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"RFBR grant","award":["19-04-01227","20-01-00469"],"award-info":[{"award-number":["19-04-01227","20-01-00469"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We address the problems of minimizing and of maximizing the spectral radius over a compact family of non-negative matrices. Those problems being hard in general can be efficiently solved for some special families. We consider the so-called product families, where each matrix is composed of rows chosen independently from given sets. A recently introduced greedy method works very fast. However, it is applicable mostly for strictly positive matrices. For sparse matrices, it often diverges and gives a wrong answer. We present the \u201cselective greedy method\u201d that works equally well for all non-negative product families, including sparse ones. For this method, we prove a quadratic rate of convergence and demonstrate its efficiency in numerical examples. The numerical examples are realised for two cases: finite uncertainty sets and polyhedral uncertainty sets given by systems of linear inequalities. In dimensions up to 2000, the matrices with minimal\/maximal spectral radii in product families are found within a few iterations. Applications to dynamical systems and to the graph theory are considered.<\/jats:p>","DOI":"10.1007\/s10107-020-01585-z","type":"journal-article","created":{"date-parts":[[2020,10,27]],"date-time":"2020-10-27T12:06:45Z","timestamp":1603800405000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["The greedy strategy for optimizing the Perron eigenvalue"],"prefix":"10.1007","volume":"193","author":[{"given":"Aleksandar","family":"Cvetkovi\u0107","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1862-2046","authenticated-orcid":false,"given":"Vladimir Yu.","family":"Protasov","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,10,27]]},"reference":[{"key":"1585_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-019-09925-z","volume-title":"The operator approach to entropy games","author":"M Akian","year":"2019","unstructured":"Akian, M., Gaubert, S., Grand-Cl\u00e9ment, J., Guillaud, J.: The operator approach to entropy games. Syst, Theory Comput (2019). https:\/\/doi.org\/10.1007\/s00224-019-09925-z"},{"key":"1585_CR2","unstructured":"Altman, E.: Constrained Markov Decision Process. INRIA (2004)"},{"key":"1585_CR3","doi-asserted-by":"crossref","unstructured":"Anderson, J.: Distance to the nearest stable Metzler matrix. arXiv:1709.02461v1 (2017)","DOI":"10.1109\/CDC.2017.8264649"},{"key":"1585_CR4","unstructured":"Asarin, E., Cervelle, J., Degorre, A., Dima, C., Horn, F., Kozyakin, V.: Entropy games and matrix multiplication games. In: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), February 2016, Orl\u00e9ans, France, pp. 11:1\u201311:14"},{"key":"1585_CR5","volume-title":"An Introduction to Numerical Analysis","author":"KE Atkinson","year":"1989","unstructured":"Atkinson, K.E.: An Introduction to Numerical Analysis. Wiley, Hoboken (1989)"},{"issue":"3","key":"1585_CR6","doi-asserted-by":"publisher","first-page":"865","DOI":"10.1137\/080723764","volume":"31","author":"VD Blondel","year":"2009","unstructured":"Blondel, V.D., Nesterov, Y.: Polynomial-time computation of the joint spectral radius for some sets of nonnegative matrices. SIAM J. Matrix Anal. Appl. 31(3), 865\u2013876 (2009)","journal-title":"SIAM J. Matrix Anal. Appl."},{"key":"1585_CR7","volume-title":"Nonnegative Matrices in the Mathematical Sciences","author":"A Berman","year":"1979","unstructured":"Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Sciences. Acedemic Press, Now York (1979)"},{"key":"1585_CR8","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/0024-3795(85)90092-8","volume":"65","author":"RA Brualdi","year":"1985","unstructured":"Brualdi, R.A., Hoffman, A.J.: On the spectral radius of (0, 1)-matrices. Linear Algorithm Appl. 65, 133\u2013146 (1985)","journal-title":"Linear Algorithm Appl."},{"key":"1585_CR9","doi-asserted-by":"publisher","first-page":"1231","DOI":"10.2307\/2171729","volume":"63","author":"DG Cantor","year":"1995","unstructured":"Cantor, D.G., Lippman, S.A.: Optimal investment selection with a multiple of projects. Econometrica 63, 1231\u20131240 (1995)","journal-title":"Econometrica"},{"key":"1585_CR10","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/j.dam.2014.01.007","volume":"169","author":"BC Cs\u00e1ji","year":"2014","unstructured":"Cs\u00e1ji, B.C., Jungers, R.M., Blondel, V.D.: PageRank optimization by edge selection. Discret. Appl. Math. 169, 73\u201387 (2014)","journal-title":"Discret. Appl. Math."},{"key":"1585_CR11","volume-title":"Spectra of Graphs: Theory and Application","author":"D Cvetkovi\u0107","year":"1980","unstructured":"Cvetkovi\u0107, D., Doob, M., Sachs, H.: Spectra of Graphs: Theory and Application. Academic Press, New York (1980)"},{"key":"1585_CR12","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/j.laa.2014.05.010","volume":"455","author":"GM Engel","year":"2014","unstructured":"Engel, G.M., Schneider, H., Sergeev, S.: On sets of eigenvalues of matrices with prescribed row sums and prescribed graph. Linear Algorithm Appl. 455, 187\u2013209 (2014)","journal-title":"Linear Algorithm Appl."},{"issue":"4","key":"1585_CR13","doi-asserted-by":"publisher","first-page":"2193","DOI":"10.1137\/11083808X","volume":"50","author":"L Fainshil","year":"2012","unstructured":"Fainshil, L., Margaliot, M.: A maximum principle for the stability analysis of positive bilinear control systems with applications to positive linear switched systems. SIAM J. Control Optim. 50(4), 2193\u20132215 (2012)","journal-title":"SIAM J. Control Optim."},{"issue":"1","key":"1585_CR14","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1109\/TAC.2012.2226103","volume":"58","author":"O Fercoq","year":"2013","unstructured":"Fercoq, O., Akian, M., Bouhtou, M., Gaubert, S.: Ergodic control and polyhedral approaches to PageRank optimization. IEEE Trans. Autom. Control 58(1), 134\u2013148 (2013)","journal-title":"IEEE Trans. Autom. Control"},{"key":"1585_CR15","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/0024-3795(85)90068-0","volume":"69","author":"S Friedland","year":"1985","unstructured":"Friedland, S.: The maximal eigenvalue of 0\u20131 matrices with prescribed number of ones. Linear Algorithm Appl. 69, 33\u201369 (1985)","journal-title":"Linear Algorithm Appl."},{"key":"1585_CR16","volume-title":"The Theory of Matrices","author":"FR Gantmacher","year":"2013","unstructured":"Gantmacher, F.R.: The Theory of Matrices. Chelsea, New York (2013)"},{"key":"1585_CR17","unstructured":"Goyal, V., Grand-Clement J.: A first-order approach to accelerated value iteration. arXiv:1905.09963"},{"issue":"4","key":"1585_CR18","doi-asserted-by":"publisher","first-page":"1642","DOI":"10.1137\/18M1172454","volume":"39","author":"N Guglielmi","year":"2018","unstructured":"Guglielmi, N., Protasov, V.: On the closest stable\/unstable nonnegative matrix and related stability radii. SIAM J. Matrix Anal. 39(4), 1642\u20131669 (2018)","journal-title":"SIAM J. Matrix Anal."},{"key":"1585_CR19","doi-asserted-by":"crossref","unstructured":"Jungers, R., Protasov, V.Yu., Blondel, V.: Efficient algorithms for deciding the type of growth of products of integer matrices. Linear Algorithm Appl. 428(10), 2296\u20132312 (2008)","DOI":"10.1016\/j.laa.2007.08.001"},{"key":"1585_CR20","unstructured":"Hansen, T.D., Miltersen, P.B., Zwick, U.: Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. In: Innovations in Computer Science 2011, pp. 253\u2013263. Tsinghua University Press (2011)"},{"key":"1585_CR21","first-page":"359","volume":"12","author":"AJ Hoffman","year":"1966","unstructured":"Hoffman, A.J., Karp, R.M.: On nonterminating stochastic games. Manag. Sci. J. Inst. Manag. Sci. Appl. Theory Ser. 12, 359\u2013370 (1966)","journal-title":"Manag. Sci. J. Inst. Manag. Sci. Appl. Theory Ser."},{"key":"1585_CR22","doi-asserted-by":"crossref","unstructured":"Kozyakin, V.S.: A short introduction to asynchronous systems. In: Aulbach, B., Elaydi, S., Ladas, G. (eds.) Proceedings of the Sixth International Conference on Difference Equations (Augsburg, Germany 2001): New Progress in Difference Equations, CRC Press, Boca Raton, pp. 153\u2013166 (2004)","DOI":"10.1201\/9780203575437.ch12"},{"key":"1585_CR23","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.laa.2015.10.017","volume":"489","author":"VS Kozyakin","year":"2016","unstructured":"Kozyakin, V.S.: Hourglass alternative and the finiteness conjecture for the spectral characteristics of sets of non-negative matrices. Linear Algorithm Appl. 489, 167\u2013185 (2016)","journal-title":"Linear Algorithm Appl."},{"issue":"2","key":"1585_CR24","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1109\/TAC.2008.2012009","volume":"54","author":"H Lin","year":"2009","unstructured":"Lin, H., Antsaklis, P.J.: Stability and stabilizability of switched linear systems: a survey of recent results. IEEE Trans. Autom. Contr. 54(2), 308\u2013322 (2009)","journal-title":"IEEE Trans. Autom. Contr."},{"issue":"2","key":"1585_CR25","doi-asserted-by":"publisher","first-page":"5317","DOI":"10.1016\/j.disc.2007.09.049","volume":"308","author":"B Liu","year":"2008","unstructured":"Liu, B.: On an upper bound of the spectral radius of graphs. Discret. Math. 308(2), 5317\u20135324 (2008)","journal-title":"Discret. Math."},{"key":"1585_CR26","volume-title":"Matrices and Graphs: Stability Problems in Mathematical Ecology","author":"DO Logofet","year":"1993","unstructured":"Logofet, D.O.: Matrices and Graphs: Stability Problems in Mathematical Ecology. CRC Press, Boca Raton (1993)"},{"key":"1585_CR27","unstructured":"Mansour, Y., Singh, S.: On the complexity of policy iteration. In: Proceedings of the 15th International Conference on Uncertainty in AI, pp. 401\u2013408 (1999)"},{"key":"1585_CR28","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1016\/j.amc.2014.04.053","volume":"255","author":"Y Nesterov","year":"2015","unstructured":"Nesterov, Y., Nemirovski, A.: Finding the stationary states of Markov chains by iterative methods. Appl. Math. Comput. 255, 58\u201365 (2015)","journal-title":"Appl. Math. Comput."},{"key":"1585_CR29","doi-asserted-by":"crossref","unstructured":"Nesterov, Y., Protasov, V.Yu.: Optimizing the spectral radius. SIAM J. Matrix Anal. Appl. 34(3), 999\u20131013 (2013)","DOI":"10.1137\/110850967"},{"key":"1585_CR30","doi-asserted-by":"crossref","unstructured":"Nesterov, Y., Protasov, V.Yu.: Computing closest stable non-negative matrix. SIAM J. Matrix. Anal. Appl. 1, 1\u201328 (2020)","DOI":"10.1137\/17M1144568"},{"key":"1585_CR31","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/S0024-3795(01)00504-3","volume":"346","author":"DD Olesky","year":"2002","unstructured":"Olesky, D.D., Roy, A., van den Driessche, P.: Maximal graphs and graphs with maximal spectral radius. Linear Algorithm Appl. 346, 109\u2013130 (2002)","journal-title":"Linear Algorithm Appl."},{"key":"1585_CR32","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2014.0699","author":"I Post","year":"2015","unstructured":"Post, I., Ye, Y.: The simplex method is strongly polynomial for deterministic Markov decision processes. Math. Oper. Res. (2015). https:\/\/doi.org\/10.1287\/moor.2014.0699","journal-title":"Math. Oper. Res."},{"key":"1585_CR33","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316887","volume-title":"Markov Decision Processes","author":"ML Putermam","year":"1994","unstructured":"Putermam, M.L.: Markov Decision Processes. Wiley, Hoboken (1994)"},{"key":"1585_CR34","doi-asserted-by":"crossref","unstructured":"Protasov, V.Yu.: The spectral simplex method. Math. Prog. 156, 485\u2013511 (2016)","DOI":"10.1007\/s10107-015-0905-2"},{"key":"1585_CR35","doi-asserted-by":"crossref","unstructured":"Protasov, V.Yu.: How to make the Perron eigenvector simple. CALCOLO 56, 17 (2019)","DOI":"10.1007\/s10092-019-0314-7"},{"key":"1585_CR36","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1287\/moor.9.1.6","volume":"9","author":"UG Rothblum","year":"1984","unstructured":"Rothblum, U.G.: Multiplicative Markov decision chains. Math. Oper. Res. 9, 6\u201324 (1984)","journal-title":"Math. Oper. Res."},{"key":"1585_CR37","volume-title":"Matrix Perturbation Theory","author":"GW Stewart","year":"1990","unstructured":"Stewart, G.W., Sun, J.G.: Matrix Perturbation Theory. Academic Press, New York (1990)"},{"issue":"2","key":"1585_CR38","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1137\/0201010","volume":"1","author":"R Tarjan","year":"1972","unstructured":"Tarjan, R.: Depth first search and linear graph algorithms. SIAM J. Comput. 1(2), 146\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1585_CR39","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1287\/moor.1110.0516","volume":"36","author":"Y Ye","year":"2011","unstructured":"Ye, Y.: The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate. Math. Oper. Res. 36(4), 593\u2013603 (2011)","journal-title":"Math. Oper. Res."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01585-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01585-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01585-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T02:47:13Z","timestamp":1698288433000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01585-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,27]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,5]]}},"alternative-id":["1585"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01585-z","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,10,27]]},"assertion":[{"value":"22 April 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}