Abstract
The convergence theory for the gradient sampling algorithm is extended to directionally Lipschitz functions. Although directionally Lipschitz functions are not necessarily locally Lipschitz, they are almost everywhere differentiable and well approximated by gradients and so are a natural candidate for the application of the gradient sampling algorithm. The main obstacle to this extension is the potential unboundedness or emptiness of the Clarke subdifferential at points of interest. The convergence analysis we present provides one path to addressing these issues. In particular, we recover the usual convergence theory when the function is locally Lipschitz. Moreover, if the algorithm does not drive a certain measure of criticality to zero, then the iterates must converge to a point at which either the Clarke subdifferential is empty or the direction of steepest descent is degenerate in the sense that it does lie in the interior of the domain of the regular subderivative.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Borwein, J. M., Zhu, Q. J.: Techniques of Variational Analysis. Canadian Math Society (2005)
Borwein, J. M., Burke, J. V., Lewis, A. S.: Differentiability of cone-monotone functions on separable Banach space. Pro. Amer. Math Soc. 132, 1067–1076 (2003)
Burke, J. V., Lewis, A. S., Overton, M.L.: Approximating subdifferentials by random sampling of gradients. Math. Oper Res. 27(3), 567–584 (2002)
Burke, J. V., Lewis, A. S., Overton, M. L.: Two numerical methods for optimizing matrix stability. Linear Algebra Appl. 351/352, 117–145 (2002)
Burke, J. V., Lewis, A. S., Overton, M. L.: A Nonsmooth, Nonconvex optimization approach to robust stabilization by static output feedback and Low-Order controllers. IFAC Proceedings Volumes 36, 175–181 (2003)
Burke, J. V., Lewis, A. S., Overton, M.L.: A robust gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 15(3), 751–779 (2005)
Burke, J. V., Curtis, F. E., Lewis, A. S., Overton, M. L., Simoes, L. E. A.: Gradient sampling methods for nonsmooth optimization. In: Bagirov, A.M., Gaudioso, M., Karmitsa, N., Mäkella, M.M., Taheri, S. (eds.) Numerical Nonsmooth Optimization: State of the Art Algorithms, chapter 6, pp 201–225. Springer (2020)
Burke, J. V., Deng, S.: Weak sharp minima revisited, part ii: Applications to linear regularity and error bounds. Math. Prog. 104, 236–261 (2005)
Burke, J. V.: Methods for Solving Generalized Systems of Inequalities with Application to Nonlinear Programming. PhD thesis University of Illinois at Urbana-Champaign (1983)
Clarke, F. H.: Optimization and Nonsmooth Analysis. Wiley, New York (1983). Reprinted by SIAM Philadelphia 1990
Kiwiel, K. C.: Convergence of the gradient sampling algorithm for nonsmooth nonconvex optimization. SIAM J. Optim. 18(2), 379–388 (2007)
Lin, Q.: Sparsity and Non-Convex, Non-Smooth Optimization. Phd Thesis, University of Washington, Seattle (2009)
Nirenberg, L.: Lecture notes in functional analysis (1961)
Rockafellar, R. T., Wets, R. J. -B.: Variational Analysis. Springer (1998)
Rockafellar, R. T.: Clarke’s tangent cones and the boundaries of closed sets in \(\mathbb {R}^{n}\). Nonlin. Anal. Th. Meth. and Appl. 3, 145–154 (1979)
Rockafellar, R. T.: Directionally lischitzian functions and subdifferential calculus. Proc. London Math. Soc. 39, 331–355 (1979)
Rockafellar, R. T.: Generalized directional derivatives and subdifferentials of nonconvex functions. Canadian J. Math. 32, 157–180 (1980)
Acknowledgements
The authors sincerely thank two referees for their care careful reading and thoughtful comments. Their efforts have significantly improved the clarity of the presentation.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This paper is dedicated to Terry Rockafellar on the occasion of his 85th birthday.
Supported in part by the U.S. National Science Foundation grant DMS-1908890.
Rights and permissions
About this article
Cite this article
Burke, J.V., Lin, Q. Convergence of the Gradient Sampling Algorithm on Directionally Lipschitz Functions. Set-Valued Var. Anal 29, 949–966 (2021). https://doi.org/10.1007/s11228-021-00610-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11228-021-00610-3