Acta Numerica

Research Article

Eigenvalue optimization

Adrian S. Lewisa1* and Michael L. Overtona2

a1 Department of Combinatorics and Optimization University of Waterloo Ontario N2L 3G1, Canada E-mail: aslewis@orion.uwaterloo.ca WWW:http://orion.uwaterloo.ca/~aslewis

a2 Computer Science Department Courant Institute of Mathematical Sciences New York University New York, NY 10012-1110, USA E-mail: overton@cs.nyu.edu WWW:http://cs.nyu.edu/cs/faculty/overton

Optimization problems involving eigenvalues arise in many different mathematical disciplines. This article is divided into two parts. Part I gives a historical account of the development of the field. We discuss various applications that have been especially influential, from structural analysis to combinatorial optimization, and we survey algorithmic developments, including the recent advance of interior-point methods for a specific problem class: semidefinite programming. In Part II we primarily address optimization of convex functions of eigenvalues of symmetric matrices subject to linear constraints. We derive a fairly complete mathematical theory, some of it classical and some of it new. Using the elegant language of conjugate duality theory, we highlight the parallels between the analysis of invariant matrix norms and weakly invariant convex matrix functions. We then restrict our attention further to linear and semidefinite programming, emphasizing the parallel duality theory and comparing primal-dual interior-point methods for the two problem classes. The final section presents some apparently new variational results about eigenvalues of nonsymmetric matrices, unifying known characterizations of the spectral abscissa (related to Lyapunov theory) and the spectral radius (as an infimum of matrix norms).

Footnotes

* Supported in part by the Natural Sciences and Engineering Research Council of Canada.

† Supported in part by the U.S. National Science Foundation under grant CCR-9401136.