Slope And Geometry In Variational Mathematics
Structure permeates both theory and practice in modern optimization. To make progress, optimizers often presuppose a particular algebraic description of the problem at hand, namely whether the functional components are affine, polynomial, smooth, sparse, etc., and a qualification (transversality) condition guaranteeing the components do not interact wildly. This thesis deals with structure as well, but in an intrinsic and geometric sense, independent of functional representation. On one hand, we emphasize the slope - the fastest instantaneous rate of decrease of a function - as an elegant and powerful tool to study nonsmooth phenomenon. The slope yields a verifiable condition for existence of exact error bounds - a Lipschitz-like dependence of a function's sublevel sets on its values. This relationship, in particular, will be key for the convergence analysis of the method of alternating projections and for the existence theory of steepest descent curves (appropriately defined in absence of differentiability). On the other hand, the slope and the derived concept of subdifferential may be of limited use in general due to various pathologies that may occur. For example, the subdifferential graph may be large (full-dimensional in the ambient space) or the critical value set may be dense in the image space. Such pathologies, however, rarely appear in practice. Semi-algebraic functions - those functions whose graphs are composed of finitely many sets, each defined by finitely many polynomial inequalities - nicely represent concrete functions arising in optimization and are void of such pathologies. To illustrate, we will see that semi-algebraic subdifferential graphs are, in a precise mathematical sense, small. Moreover, using the slope in tandem with semi-algebraic techniques, we significantly strengthen the convergence theory of the method of alternating projections and prove new regularity properties of steepest descent curves in the semi-algebraic setting. To illustrate, under reasonable conditions, bounded steepest descent curves of semi-algebraic functions have finite length and converge to local minimizers - properties that decisively fail in absence of semi-algebraicity. We conclude the thesis with a fresh new look at active sets in optimization from the perspective of representation independence. The underlying idea is extremely simple: around a solution of an optimization problem, an "identifiable" subset of the feasible region is one containing all nearby solutions after small perturbations to the problem. A quest for only the most essential ingredients of sensitivity analysis leads us to consider identifiable sets that are "minimal". In the context of standard nonlinear programming, this concept reduces to the active-set philosophy. On the other hand, identifiability is much broader, being independent of functional representation of the problem. This new notion lays a broad and intuitive variational-analytic foundation for optimality conditions, sensitivity, and active-set methods. In the last chapter of the thesis, we illustrate the robustness of the concept in the context of eigenvalue optimization.
Lewis, Adrian S.
Todd, Michael Jeremy; Renegar, James
Ph.D. of Operations Research
Doctor of Philosophy
dissertation or thesis