ABSTRACT
It has long been known that the gradient (steepest descent) method may fail on non-smooth problems, but the examples that have appeared in the literature are either devised specifically to defeat a gradient or subgradient method with an exact line search or are unstable with respect to perturbation of the initial point. We give an analysis of the gradient method with steplengths satisfying the Armijo and Wolfe inexact line search conditions on the non-smooth convex function . We show that if a is sufficiently large, satisfying a condition that depends only on the Armijo parameter, then, when the method is initiated at any point
with
, the iterates converge to a point
with
, although f is unbounded below. We also give conditions under which the iterates
, using a specific Armijo–Wolfe bracketing line search. Our experimental results demonstrate that our analysis is reasonably tight.
Disclosure statement
No potential conflict of interest was reported by the authors.
ORCID
Azam Asl http://orcid.org/0000-0001-5865-9623
Michael L. Overton http://orcid.org/0000-0002-6563-6371
Notes
1. There is a subtle distinction between the Wolfe condition given here and that given in [Citation16], since here the Wolfe condition is understood to fail if the gradient of f does not exist at , while in [Citation16] it is understood to fail if the function of one variable
is not differentiable at s = t. For the example analysed here, these conditions are equivalent.
2. The same oscillatory behaviour occurs if we replace the Wolfe condition by the Goldstein condition .
4. In our implementation, we made no attempt to determine whether is differentiable at a given point or not. This is essentially impossible in floating point arithmetic, but as noted earlier, the gradient is defined at randomly generated points with probability one; there is no reason to suppose that any of the methods tested will generate points where
is not differentiable, except in the limit, and hence the ‘subgradient’ method actually reduces to the gradient method with
. See [Citation16] for further discussion.
Additional information
Funding
Notes on contributors
Azam Asl
Azam Asl obtained her B.Sc. in Computer Engineering at Sharif University of Technology in Teheran in 2008. She will receive her Ph.D. in Computer Science from New York University in 2020.
Michael L. Overton
Michael L. Overton obtained his Ph.D. in Computer Science from Stanford University in 1979. He is a Silver Professor of Computer Science and Mathematics at the Courant Institute of Mathematical Sciences, New York University.