The DOI matches its Crossref record; 21 of the 21 references it cites were found in a registry or an index.
A Robust Gradient Sampling Algorithm for Nonsmooth, Nonconvex Optimization
Abstract
Let f be a continuous function on $\Rl^n$, and suppose f is continuously differentiable on an open dense subset. Such functions arise in many applications, and very often minimizers are points at which f is not differentiable. Of particular interest is the case where f is not convex, and perhaps not even locally Lipschitz, but is a function whose gradient is easily computed where it is defined. We present a practical, robust algorithm to locally minimize such functions, based on gradient sampling. No subgradient information is required by the algorithm. When f is locally Lipschitz and has bounded level sets, and the sampling radius $\eps$ is fixed, we show that, with probability 1, the algorithm generates a sequence with a cluster point that is Clarke $\eps$-stationary. Furthermore, we show that if f has a unique Clarke stationary point $\bar x$, then the set of all cluster points generated by the algorithm converges to $\bar x$ as $\eps$ is reduced to zero. Numerical results are presented demonstrating the robustness of the algorithm and its applicability in a wide variety of contexts, including cases where f is not locally Lipschitz at minimizers. We report approximate local minimizers for functions in the applications literature which have not, to our knowledge, been obtained previously. When the termination criteria of the algorithm are satisfied, a precise statement about nearness to Clarke $\eps$-stationarity is available. A MATLAB implementation of the algorithm is posted at http://www.cs.nyu.edu/overton/papers/gradsamp/alg.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Rockafellar, R. T. (1970) · Princeton University Press eBooks · doi:10.1515/9781400873173 · Cited by 10,801
Optimization and Nonsmooth Analysis
Clarke, F. H. (1990) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611971309 · Cited by 10,264
Practical Methods of Optimization
Fletcher, R. (2000) · Wiley eBooks · doi:10.1002/9781118723203 · Cited by 7,605
Practical methods of optimization
(1988) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(88)90129-2 · Cited by 5,818
Practical Methods of Optimization.
Witzgall, C., & Fletcher, R. (1989) · Mathematics of Computation · doi:10.2307/2008742 · Cited by 3,591
Linear Multivariable Control: a Geometric Approach
Wonham, W. M. (1979) · Springer eBooks · doi:10.1007/978-1-4684-0068-7 · Cited by 3,136
Convex Analysis and Minimization Algorithms I
Hiriart-Urruty, J.-B., & Lemaréchal, C. (1993) · Grundlehren der mathematischen Wissenschaften · doi:10.1007/978-3-662-02796-7 · Cited by 2,378
Nonlinear Programming: Sequential Unconstrained Minimization Techniques
Fiacco, A. V., & McCormick, G. P. (1968) · Defense Technical Information Center (DTIC) · Cited by 2,262
Nonsmooth Analysis and Control Theory
(1998) · Graduate Texts in Mathematics · doi:10.1007/b97650 · Cited by 1,962
(2017) · Approximation Techniques for Engineers · doi:10.1201/9781315205007-4 · Cited by 1,155
Cited by
Classification and Review of Control Strategies for Plug-In Hybrid Electric Vehicles
Wirasingha, S. G., & Emadi, A. (2011) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2010.2090178 · Cited by 696
A Convergence Theory for Deep Learning via Over-Parameterization
Allen-Zhu, Z., Li, Y., & Song, Z. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1811.03962 · Cited by 657
Nonsmooth optimization via quasi-Newton methods
Lewis, A. S., & Overton, M. L. (2013) · Mathematical Programming · doi:10.1007/s10107-012-0514-2 · Cited by 352
Self-citationSmoothing methods for nonsmooth, nonconvex minimization
Chen, X. (2012) · Mathematical Programming · doi:10.1007/s10107-012-0569-0 · Cited by 295
Lower Bound Theory of Nonzero Entries in Solutions of $\ell_2$-$\ell_p$ Minimization
Chen, X., Xu, F., & Ye, Y. (2010) · SIAM Journal on Scientific Computing · doi:10.1137/090761471 · Cited by 288
A Globally Convergent Algorithm for Nonconvex Optimization Based on Block Coordinate Update
Xu, Y., & Yin, W. (2017) · Journal of Scientific Computing · doi:10.1007/s10915-017-0376-0 · Cited by 285
From static output feedback to structured robust static output feedback: A survey
Sadabadi, M. S., & Peaucelle, D. (2016) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2016.09.014 · Cited by 260
Metadata
- Authors
- Burke, J. V., Lewis, A. S., & Overton, M. L.
- Venue
- SIAM Journal on Optimization
- Published
- 2005-01
- Volume
- 15
- Issue
- 3
- Pages
- 751-779
- ISSN
- 1052-6234 (ISSN-L)
- 1095-7189
- OpenAlex
- W2064942524
- Cited by
- 453
- References
- 21
- FWCI
- 14.12
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.