Theory And Algorithms For Structured Nonsmooth Optimization

Other Titles
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.
Journal / Series
Volume & Issue
Date Issued
Effective Date
Expiration Date
Union Local
Number of Workers
Committee Chair
Lewis, Adrian S.
Committee Co-Chair
Committee Member
Renegar, James
Todd, Michael Jeremy
Degree Discipline
Operations Research
Degree Name
Ph. D., Operations Research
Degree Level
Doctor of Philosophy
Related Version
Related DOI
Related To
Related Part
Based on Related Item
Has Other Format(s)
Part of Related Item
Related To
Related Publication(s)
Link(s) to Related Publication(s)
Link(s) to Reference(s)
Previously Published As
Government Document
Other Identifiers
Rights URI
dissertation or thesis
Accessibility Feature
Accessibility Hazard
Accessibility Summary
Link(s) to Catalog Record