Variational analysis of non-Lipschitz spectral functions

James V. Burke, Michael L. Overton

Research output: Contribution to journalArticlepeer-review

Abstract

We consider spectral functions f ○ λ, where f is any permutation-invariant mapping from Cn to R, and λ is the eigenvalue map from the set of n x n complex matrices to Cn, ordering the eigenvalues lexicographically. For example, if f is the function "maximum real part", then f ○ λ is the spectral abscissa, while if f is "maximum modulus", then f ○ λ 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 subgradient extensively analyzed in Variational Analysis, R.T. Rockafellar and R. J.-B. Wets (Springer, 1998). We show that a necessary condition for Y to be a subgradient of an eigenvalue function f ○ λ at X is that Y* commutes 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 abscissa, we refine these conditions, and we precisely identify the case where subdifferential regularity holds. We conclude by introducing the notion of a semistable program: maximize a linear function on the set of square matrices subject to linear equality constraints together with the constraint that the real parts of the eigenvalues of the solution matrix are non-positive. Semistable programming is a nonconvex generalization of semidefinite programming. Using our analysis, we derive a necessary condition for a local maximizer of a semistable program, and we give a generalization of the complementarity condition familiar from semidefinite programming.

Original languageEnglish (US)
Pages (from-to)317-351
Number of pages35
JournalMathematical Programming, Series B
Volume90
Issue number2
DOIs
StatePublished - Apr 2001

Keywords

  • Eigenvalue function
  • Nonsmooth analysis
  • Semistable program
  • Spectral abscissa
  • Spectral radius
  • Stability

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'Variational analysis of non-Lipschitz spectral functions'. Together they form a unique fingerprint.

Cite this