Special PIMS Seminar: Michael Overton

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.