Back to search

Cornell University

Theory And Algorithms For Structured Nonsmooth Optimization

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research
Grantor
Cornell University
Year dc:date.issued
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhang, Shanshan
Chair dc:contributor.chair
  • Lewis, Adrian S.
Committee members dc:contributor.committeemember
  • Renegar, James
  • Todd, Michael Jeremy

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
8267517

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Zhang, Shanshan. Theory And Algorithms For Structured Nonsmooth Optimization. Doctor of Philosophy thesis, Cornell University, 2013. https://hdl.handle.net/1813/34360