Analysis of the gradient method with an Armijo–Wolfe line search on a class of non-smooth convex functions

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 $f\left(x\right)=a|x^{\left(1\right)}|+\sum _{i=2}^n{x}^{\left(i\right)}$. 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 $x_0\in {\mathbb{R}}^n$ with $x_0^{\left(1\right)}\ne 0$, the iterates converge to a point $\overline{x}$ with ${\overline{x}}^{\left(1\right)}=0$, although f is unbounded below. We also give conditions under which the iterates $f\left(x_k\right)\to -\mathrm{\infty }$, using a specific Armijo–Wolfe bracketing line search. Our experimental results demonstrate that our analysis is reasonably tight.

KEYWORDS:

• Steepest descent method
• convex optimization
• non-smooth optimization

2010 MATHEMATICS SUBJECT CLASSIFICATIONS:

• 49M30
• 65K05
• 90C25

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 [16], since here the Wolfe condition is understood to fail if the gradient of f does not exist at $x_k+t{d}_k$, while in [16] it is understood to fail if the function of one variable $s\mapsto f(x_k+s{d}_k)$ 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 $f(x_k+t{d}_k)\ge f\left(x_k\right)+c_{2}t\mathrm{\nabla }f(x_k{)}^T{d}_k$.

3. www.cs.nyu.edu/overton/software/hanso/

4. In our implementation, we made no attempt to determine whether $\hat{f}$ 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 $\hat{f}$ is not differentiable, except in the limit, and hence the ‘subgradient’ method actually reduces to the gradient method with $t_k=1/k$. See [16] for further discussion.

Additional information

Funding

Michael L. Overton was supported in part by National Science Foundation [grant number DMS-1620083].

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.