Applied Mathematics Colloquium
Annenberg 105
Optimization of Polynomial Roots, Eigenvalues and Pseudospectra
Michael Overton,
Professor,
Courant Institute of Mathematical Sciences,
New York University,
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.
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.
For more information, please contact Sydney Garstang by phone at x4555 or by email at [email protected] or visit http://www.acm.caltech.edu.
Event Series
Applied Mathematics Colloquium Series