Semi-Algebraic Techniques In Variational Analysis: Pseudospectra, Robustness, Generic Continuity, And Mountain Pass Algorithms.

Abstract

Variational Analysis is the modern theory of nonsmooth, nonconvex analysis built on the theory of convex and smooth optimization. While the general theory needs to handle pathologies, functions and sets appearing in applications are typically structured. Semi-algebraic functions and sets eliminates much of the pathological behavior, and still forms a broad class of constructs appearing in practice, making it an ideal setting for practical variational analysis. Chapter 1 is an introduction to the thesis and Chapter 2 reviews preliminaries. Chapters 3 to 5 describe various semi-algebraic techniques in variational analysis. Chapter 3 gives equivalent conditions for the Lipschitz continuity of pseudospectra in the set-valued sense. As corollaries, we give formulas for the Lipschitz constants of the pseudospectra, pseudospectral abscissa and pseudospectral radius. We also study critical points of the resolvent function. Chapter 4 studies robust solutions of an optimization problem using the " epsilon-robust regularization" of a function, and prove that it is Lipschitz at a point for all small epsilon greater than 0 for nice functions, and in particular semi-algebraic functions. This result generalizes some of the ideas in Chapter 3. Chapter 5 studies the continuity properties of set-valued maps. We prove that the set of points where a closed-valued semi-algebraic (and more generally, tame) set-valued map is not strictly continuous is a set of lower dimension. As a by product of our analysis, we prove a Sard-type theorem for local (Pareto) minimums of scalar-valued and vector-valued functions. Chapter 6 departs from the theoretical bent of the rest of the thesis and is computational. We describe algorithms for computing critical points of mountain pass type. We prove that sub-level sets of a function coalesce at critical points of mountain pass type and discuss algorithmic implications. In particular, we propose a locally superlinearly convergent algorithm for smooth nondegenerate critical points of Morse index 1. We conclude this chapter by describing a strategy for the Wilkinson problem of finding the closest matrix with repeated eigenvalues.