Variational analysis of non-Lipschitz spectral functions

We consider spectral functions f o lambda, where f is any permutation-invar iant mapping from C-n to R, and lambda is the eigenvalue map from the set o f n x n complex matrices to C-n, ordering the eigenvalues lexicographically For example, if f is the function "maximum real part", then f o lambda is the spectral abscissa, while if f is "maximum modulus", then f o lambda is the spectral radius. Both these spectral functions are continuous, but they are neither convex nor Lipschitz. For our analysis, we use the notion of s ubgradient extensively analyzed in Variational Analysis, R.T. Rockafellar a nd R. J.-B. Wets (Springer, 1998). We show that a necessary condition for Y to be a subgradient of an eigenvalue function S o h at X is that Y* commut es with X. We also give a number of other necessary conditions for Y based on the Schur form and the Jordan form of X. In the case of the spectral abs cissa, wt: refine these conditions, and we precisely identify the case wher e subdifferential regularity holds. We conclude by introducing the notion o f a semistable program: maximize a linear function on the set of square mat rices subject to linear equality constraints together with the constraint t hat the real parts of the eigenvalues of the solution matrix are non-positi ve. Semistable programming is a nonconvex generalization of semidefinite pr ogramming. Using our analysis, we derive a necessary condition for a local maximizer of a semistable program, and we give a generalization of the comp lementarity condition familiar from semidefinite programming.