Special PIMS Seminar: Michael Overton
- Date: 11/03/2011
- Time: 15:30
University of Victoria
Optimization of Polynomial Roots, Eigenvalues and Pseudospectra
Abstract:The root radius and root abscissa of a monic polynomial
are respectively the maximum modulus and the maximum real part of its
roots; both these functions are nonconvex and are non-Lipschitz near
polynomials with multiple roots. We begin the talk by giving
constructive methods for efficiently minimizing these nonconvex
functions in the case that there is just one affine constraint on the
polynomial's coefficients.
We then turn to the spectral radius and spectral abscissa functions
of a matrix, which are analogously defined in terms of eigenvalues. We
explain how to use nonsmooth optimization methods to find local
minimizers and how to use nonsmooth analysis to study local optimality
conditions for these nonconvex, non-Lipschitz functions.
Finally, the pseudospectral radius and abscissa of a matrix A are
respectively the maximum modulus or maximum real part of elements of its
pseudospectrum (the union of eigenvalues of all matrices within a
specified distance of A). These functions are also nonconvex but, it
turns out, locally Lipschitz, although the pseudospectrum itself is not a
Lipschitz set-valued map.
We discuss applications from control and from Markov chain Monte
Carlo as examples throughout the talk. Coauthors of relevant papers
include Vincent Blondel, Jim Burke, Kranthi Gade, Mert Gurbuzbalaban,
Adrian Lewis and Alexandre Megretski.
