On Minimizing the Special Radius of a Nonsymmetric Matrix Function: Optimality Conditions and Duality Theory

Abstract

Let $A( x )$ be a nonsymmetric real matrix affine function of a real parameter vector $x \in \mathcal{R}^m $, and let $\rho ( x )$ be the spectral radius of $A( x )$. The article addresses the following question: Given $x_0 \in \mathcal{R}^m $, is $\rho ( x )$ minimized locally at $x_0 $, and, if not, is it possible to find a descent direction for $\rho ( x )$ from $x_0 $? If any of the eigenvalues of $A( x_0 )$ that achieve the maximum modulus $\rho ( x_0 )$ are multiple, this question is not trivial to answer, since the eigenvalues are not differentiable at points where they coalesce. In the symmetric case, $A( x ) = A( x )^T $ for all $x,\rho ( x )$ is convex, and the question was resolved recently by Overton following work by Fletcher and using Rockafellar’s theory of subgradients. In the nonsymmetric case $\rho ( x )$ is neither convex nor Lipschitz, and neither the theory of subgradients nor Clarke’s theory of generalized gradients is applicable. A new necessary and sufficient condition is given for $\rho ( x )$ to have a first-order local minimum at $x_0 $, assuming that all multiple eigenvalues of $A( x_0 )$ that achieve the maximum modulus are nondefective. The optimality condition is computationally verifiable and involves computing “dual matrices.” If the condition does not hold, the dual matrices provide information that leads to the generation of a descent direction. The result can be extended to the case where $\rho ( x )$ is replaced by the maximum real part of the eigenvalues of $A( x )$. The authors use the eigenvalue perturbation theory of Rellich and Kato, which provides expressions for directional derivatives of $\rho ( x )$. They also derive formulas for the codimension of manifolds on which certain eigenvalue structures of $A( x )$ are maintained; these are due to Von Neumann and Wigner and to Arnold. Finally, they discuss the much more difficult question of resolving optimality when $A( x_0 )$ has a defective multiple eigenvalue achieving the maximum modulus $\rho ( x_0 )$.