Approximating subdifferentials by random sampling of gradients

J. V. Burke, A. S. Lewis, M. L. Overton

Research output: Contribution to journalArticlepeer-review

Abstract

Many interesting real functions on Euclidean space are differentiable almost everywhere. All Lipschitz functions have this property, but so, for example, does the spectral abscissa of a matrix (a non-Lipschitz function). In practice, the gradient is often easy to compute. We investigate to what extent we can approximate the Clarke subdifferential of such a function at some point by calculating the convex hull of some gradients sampled at random nearby points.

Original languageEnglish (US)
Pages (from-to)567-584
Number of pages18
JournalMathematics of Operations Research
Volume27
Issue number3
DOIs
StatePublished - Aug 2002

Keywords

  • Bundle method
  • Clarke subdifferential
  • Eigenvalue optimization
  • Generalized gradient
  • Nonsmooth analysis
  • Spectral abscissa
  • Stochastic gradient

ASJC Scopus subject areas

  • Mathematics(all)
  • Computer Science Applications
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Approximating subdifferentials by random sampling of gradients'. Together they form a unique fingerprint.

Cite this