= Descent lemma
{title2=$f(v)\leq f(u)+\langle\nabla f(u),v-u\rangle+\tfrac L2\|v-u\|^2$}
Suppose $f$ is a <differentiable function> on an open <convex set> $D\subseteq\mathbb R^n$ and has an $L$-<Lipschitz gradient> there, in the <Euclidean norm>. For $u,v\in D$, the <descent lemma> states
$$
f(v)\leq f(u)+\langle\nabla f(u),v-u\rangle+\frac L2\|v-u\|_2^2.
$$
A bounded continuous <Hessian matrix> gives one sufficient route to this estimate.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§9.1.2, p. 461, equation (9.13): Hessian upper bound and quadratic upper estimate; §9.3.1, p. 466, equation (9.17): substitution of a negative-gradient step]{ref}
For a short proof, put $d=v-u$. The <fundamental theorem of calculus> along the <line segment> gives
$$
f(v)-f(u)-\langle\nabla f(u),d\rangle
=\int_0^1\langle\nabla f(u+td)-\nabla f(u),d\rangle\,dt.
$$
The <Cauchy-Schwarz inequality> and the <Lipschitz gradient> bound make the <integrand> at most $Lt\|d\|_2^2$; its <integral> is $L\|d\|_2^2/2$. This proof needs no assumption that $f$ is a <convex function>.
For the <gradient descent> update $v=u-\eta\nabla f(u)$, provided $v\in D$, substitution yields
$$
f(v)\leq f(u)-\eta\left(1-\frac{L\eta}{2}\right)\|\nabla f(u)\|_2^2.
$$
For $L>0$ and $0<\eta<2/L$, this ensures strict decrease whenever the <gradient> is nonzero. At $\eta=2/L$ it guarantees only nonincrease; the quadratic example has a nonshrinking alternating component at this endpoint. At $\eta=1/L$ the guaranteed decrease is $\|\nabla f(u)\|_2^2/(2L)$. A bound valid only on $D$ cannot justify a step leaving $D$.
If a fixed admissible <step size> is used forever, every iterate stays in $D$, and $f(x_k)$ has a finite lower bound, summing this inequality shows $\sum_k\|\nabla f(x_k)\|_2^2<\infty$, hence $\nabla f(x_k)\to0$. That conclusion alone gives neither convergence of the iterates nor a <global minimum>. For example, the smooth <polynomial> $f(x)=x^4-x^2$ has $f'(0)=0$ and $f''(0)=-2$: <gradient descent> started at zero never moves, although $f(1/\sqrt2)=-1/4<0$. On $D=(-1,1)$, $|f''(x)|\leq10$, so the <Lipschitz gradient> hypothesis holds on this domain. <Convex functions> and <strongly convex functions> provide additional structure; the exact quadratic convergence result above uses a <positive-definite matrix>.
Back to article page
