Back to search

Cornell University

Blackbox optimization, Nonsmooth Structure, and Survey Descent

Abstract

dc:description.abstract

First-order, blackbox optimization methods aim to minimize objective functions using only function and gradient evaluations. On smooth, strongly-convex objectives; classical results ensure the linear convergence of these methods relative to the number of function and gradient evaluations. An analogous nonsmooth theory is challenging due to a lack of reliable, local models. As a consequence, convergence guarantees for nonsmooth optimization procedures have generally remained sublinear. In this dissertation, I propose a "survey descent" method - inspired by a new max-of-smooth model - where an iteratively-updated "survey" of points move closer-and-closer to the objective minimizer while guided by (but never touching) an "active manifold" that lies at the boundary of different smooth subdomains of the nonsmooth objective. I prove that, when the nonsmooth objective possesses a "finite-max" structure, survey descent exhibits local linear convergence; and I demonstrate empirically that survey descent holds promise even beyond the finite-max case. I also propose a blackbox initialization procedure for survey descent that finds an initial survey containing exactly one point from each smooth subdomain of a finite-max objective. Of separate interest, I show how the minimization of the numerical radii of square matrices frequently generates solutions that land on the aforementioned active manifold - an interesting example for an "identification" property of proximal operators, a common subroutine used within nonsmooth optimization methods.

Degree

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

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Han, X.Y.
Chair dc:contributor.chair
  • Lewis, Adrian
Committee members dc:contributor.committeemember
  • Renegar, James
  • Chen, Yudong

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-ShareAlike 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16219241
Dc Identifier Other
ProQuest Submission ID: 13814
ProQuest Publication ID: 30572965

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

Han, X.Y.. Blackbox optimization, Nonsmooth Structure, and Survey Descent. Doctor of Philosophy thesis, Cornell University, 2023. https://hdl.handle.net/1813/114645