Computing closest stable nonnegative matrix

SIAM Journal on Matrix Analysis and Applications. 2020. Vol. 41. No. 1. P. 1–28.

Nesterov Y., Protasov V.

The problem of nding 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 nding their global solutions. In this paper, we analyze positive discretetime

systems. They also suer 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 nd an exact solution of the corresponding nonconvex projection problems

in polynomial time. For the distance measured in the operator `1-norm or `1-norm, the exact

solution is also eciently found. To this end, we develop a modication 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 coecients [V. L Kharitonov, Dier. 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: nonnegative matrix, Iterative optimization method, spectral radius, Stability

Publication based on the results of: Uncertainty quantification in high-dimensional models (2020)