Optimization Online


Computing closest stable non-negative matrices

Yurii Nesterov(Yurii.Nesterov***at***uclouvain.be)
Vladimir Protasov(v-protassov***at***yandex.ru)

Abstract: Problem of finding the closest stable matrix for a dynamical system has many applications. It is well studied both for continuous and discrete-time systems, and the corresponding optimization problems are formulated for various matrix norms. As a rule, non-convexity of these formulations does not allow finding their global solutions. In this paper, we analyze positive discrete-time systems. They also suffer from non-convexity of the stability region, and the problem in the Frobenius norm or in 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 exact solution of the corresponding nonconvex projection problems in polynomial time. For the distance measured in the operator $\ell_{\infty}$-norm or $\ell_{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 max-norm, this can be seen as an analogue of Kharitonov's theorem for non-negative matrices.

Keywords: non-negative matrix, spectral radius, Schur stability, polyhedral norm, distance to infeasibility.

Category 1: Convex and Nonsmooth Optimization


Download: [PDF]

Entry Submitted: 08/24/2017
Entry Accepted: 08/24/2017
Entry Last Modified: 08/24/2017

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society