Absract convergence of a suboptimal version of steepest descent

Question

I'm looking for a citable reference to fill in a gap in an intermediate step of a proof which requires convergence of a suboptimal version of steepest descent.

The function $f:\bf{R}^n\to\bf{R}^n$ I am optimizing is strictly convex and differentiable almost everywhere, and my steepest descent steps $$x_{n+1}=x_{n}-s_k\frac{\nabla{f(x_n)}}{\|{\nabla{f(x_n)}}\|},$$ have step sizes $s_k$ satisfying $s_k\rightarrow0^+$ and $\sum_k s_k=\infty.$ The step sizes $s_k$ are pre-specified, so it may occasionally happen that a particular step is counter-productive, ie $f(x_{n+1})>f(x_n)$.

Is there a citable reference which asserts that $x_n$ will converge to the minimum for almost every starting point $x_0$? (The sequence isn't well-defined for all $x$, so it isn't even defined with certainty.)

I don't care about the actual rate of convergence or any of the standard numerical analysis issues, since this is a proof and not a calculation.

Answer 1

This may be a little overkill, but in general what you are looking for is Zangwill's global convergence theorem, see e.g. http://www.math.udel.edu/~angell/gl_conv.pdf

Answer 2

Suppose the gradient is Lipschitz continuous with constant $L$ (even if we don't know it). Using $f(y)\le f(x) + ||\nabla f(x)||^T(y-x) + \frac{L}{2}||y-x||$ and $x_{k+1}=x_k-s_k\nabla f(x)$, then we can write $f(x_{k+1})\le f(x_k) - (1-\frac{s_kL}{2})s_k||\nabla f(x)||^2$. With $0<s_k\le\frac{1}{L}$, we have $(1-\frac{s_kL}{2})\ge \frac{1}{2}$ and therefore we have that $f(x_{k+1})\le f(x_k) - \frac{s_k}{2}||\nabla f(x)||^2$

In the case of predetermined diminishing step-sizes ie $s_k\to 0$, then we have $s_k\in(0,\frac{1}{L}]$ for very large $k$, . Thus for very large $k$, we can then use Zangwill convergence idea of $\sum \frac{s_k}{2}||\nabla f(x)||^2 < \infty$ (I have assumed $f$ is bounded from below).

Somehow (not precisely sure) if $\sum s_k=\infty$, then we can conclude that $\underset{k\to \infty}{\text{lim}}||\nabla f(x)||\to 0$.(See Problem 1 in http://users.ece.utexas.edu/~cmcaram/EE381V_2012F/problemset3.pdf). I will be glad if anyone can clarify on how this conclusion is valid or present any other alternate proof. Thanks.