Computing Closest Stable Nonnegative Matrix

Yurii Nesterov () and Vladimir Protasov
Additional contact information
Yurii Nesterov: Université catholique de Louvain, LIDAM/CORE, Belgium

No 3233, LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: The problem of finding the closest stable matrix for a dynamical system has many applications. It is studied for both continuous and discrete-time systems and the corresponding optimization problems are formulated for various matrix norms. As a rule, nonconvexity of these formulations does not allow finding their global solutions. In this paper, we analyze positive discrete-time systems. They also suffer from nonconvexity of the stability region, and the problem in the Frobenius norm or in the Euclidean norm remains hard for them. However, it turns out that for certain polyhedral norms, the situation is much better. We show that for the distances measured in the max-norm, we can find an exact solution of the corresponding nonconvex projection problems in polynomial time. For the distance measured in the operator `∞-norm or `1-norm, the exact solution is also efficiently found. To this end, we develop a modification of the recently introduced spectral simplex method. On the other hand, for all these three norms, we obtain exact descriptions of the region of stability around a given stable matrix. In the case of the max-norm, this can be seen as an extension onto the class of nonnegative matrices, the Kharitonov theorem, providing a stability criterion for polynomials with interval coefficients [V. L Kharitonov, Differ. Uravn., 14 (1978), pp. 2086-2088; K. Panneerselvam and R. Ayyagari, Internat. J. Control Sci. Engrg., 3 (2013), pp. 81-85]. For practical implementation of our technique, we developed a new method for approximating the maximal eigenvalue of a nonnegative matrix. It combines the local quadratic rate of convergence with polynomial-time global performance guarantees.

Keywords: Non-negative matrices; spectral radius; Schur stability; iterative optimization method; polyhedral norm; non-symmetric eigenvalue problem (search for similar items in EconPapers)
Pages: 28
Date: 2023-01-01
Note: In: SIAM Journal on Matrix Analysis and Applications, 2020, vol. 41(1), p. 1-28
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvrp:3233

DOI: 10.1137/17M1144568

Access Statistics for this paper

More papers in LIDAM Reprints CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().