Approximating Subdifferentials by Random Sampling of Gradients

James V. Burke (burkemath.washington.edu)
Adrian S. Lewis (aslewiscecm.sfu.ca)
Michael L. Overton (overtoncs.nyu.edu)

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.

Keywords: Spectral abscissa, spectral radius, nonsmooth analysis

Category 1: Convex and Nonsmooth Optimization (Nonsmooth Optimization )

Citation: Submitted to Math. Oper. Research.

Download: [Postscript]

Entry Submitted: 05/31/2001
Entry Accepted: 05/31/2001
Entry Last Modified: 05/31/2001

Modify/Update this entry