Theory And Algorithms For Structured Nonsmooth Optimization

Zhang, Shanshan

Theory And Algorithms For Structured Nonsmooth Optimization

Abstract

Nonsmoothness in optimization is typically highly structured, and this structure is fundamental to any understanding of many concrete settings. This dissertation, consisting of two core chapters (followed by some further developments), studies structured nonsmooth optimization from both theoretical and algorithmic perspectives. In the first central chapter, we consider a broad class of nonsmooth functions called "partly smooth functions", which are well-behaved relative to a certain smooth manifold and moreover enjoy a powerful calculus and sensitivity theory. We use the generalized Hessian of Mordukhovich to study the secondorder conditions and sensitivity theory for this class of optimization problems. In this setting, the generalized Hessian is easy to compute. Using this computation we derive various illuminating characterizations of tilt stability, an influential sensitivity concept for the subdifferential introduced by Poliquin and Rockafellar [38]. We moreover relate this notion to the idea of "strong metric regularity". In the second core chapter, we investigate the potential behavior, both good and bad, of the well-known BFGS algorithm for smooth minimization, when applied to nonsmooth functions. We consider three very particular examples. We first present a simple nonsmooth example, illustrating how BFGS (in this case with an exact line search) typically succeeds despite nonsmoothness. We then explore, computationally, the behavior of the BFGS method with an inexact line search on the same example, and discuss the results. In further support of the heuristic effectiveness of BFGS despite nonsmoothness, we prove that, for the very simplest example of a nonsmooth function (a maximum of two affine functions), the method cannot stall at a nonstationary point. On the other hand, we present a nonsmooth example where the inexact-line-search BFGS method converges to a point despite the presence of directions of linear descent. Finally, we briefly compare line-search and trust-region strategies for BFGS in the nonsmooth case. A subsequent chapter explores some preliminary related development, and considers open questions.

Date Issued

2013-08-19

Committee Chair

Lewis, Adrian S.

Committee Member

Renegar, James
Todd, Michael Jeremy

Degree Discipline

Operations Research

Degree Name

Ph. D., Operations Research

Degree Level

Doctor of Philosophy

Types

dissertation or thesis