Let $f:\mathbb{R}\to\mathbb{R}^n$ be a differentiable convex function, i.e., $f(y)\geq f(x)+\langle \nabla f(x), y-x\rangle\,\,\forall x,y\in \mathbb{R}^n$.
We do not assume that the gradient is Lipschitz continuous. Is it possible to show that the sequence of the function values $\{f(x^{k})\}_{k\geq0}$ non-increasing where $x^{k+1}=x^k -\alpha \nabla f(x^k)$ and $\alpha>0$ ($\alpha$ can be selected so that it does not create a problem)?
Best Answer
This does not work if $\nabla f$ is not Lipschitz and $\alpha > 0$ is fixed. Let us take $$ f(x) = |x|^{3/2} \qquad \forall x \in \mathbb R.$$ Then, if $x_k > 0$ is small enough (depending on $\alpha$), we have $$ \alpha \nabla f(x_k) > 2 x_k,$$ i.e., $|x_{k+1}| > |x_k|$ and, thus, $f(x_{k+1}) > f(x_k)$.