## 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.