In the context of convex optimisation, suppose $f$ is a convex function, differentiable with $∇f$, and suppose $0 ⪯ ∇^{2}f ⪯ MI$.
I want to show that $\|∇f(x) − ∇f(y)\| ≤ M\|x − y\|$. I am not sure how to do that.
And one more follow-up to this proof. If we use norm $\|·\|_∞$, do we have another constant $M'$ such that $\|∇f(x) − ∇f(y)\|_∞ ≤ M'\|x − y\|_∞$?
Given $y$ and $x$, define the function $g:[0,1] \rightarrow \mathbb{R}$, $$g(t) = (\nabla f(x) - \nabla f(y))^{T}(\nabla f(y+t(x-y)) - \nabla f(y)),$$ for all $t \in [0,1]$. Note that $$ g'(t) = (\nabla f(x) - \nabla f(y))^{T} \nabla^2 f (y+t(x-y)) (x-y), $$ for all $t \in (0,1).$ Consequently, by the mean value theorem, there is a $\bar{t} \in (0,1)$ such that $$\begin{align} \| \nabla f(x) - \nabla f(y)\|^2 = {} & g(1)-g(0)\\ = {}& g'(\bar{t}) \\ = {} & (\nabla f(x) - \nabla f(y))^{T}\nabla^2 f(y+\bar{t} (x-y)) (x-y) \\ \leq {} & \| \nabla f(x) - \nabla f(y) \| \|\nabla^2 f (y+\bar{t}(x-y))\| \|x-y\| \end{align}$$ Hence, $$\| \nabla f(x) - \nabla f(y)\| \leq \|\nabla^2 f (y+\bar{t}(x-y))\| \|x-y\|.$$ Since $\|\nabla^2 f (y+\bar{t}(x-y))\|\leq M,$ we have $$\| \nabla f(x) - \nabla f(y)\| \leq M \|x-y\|.$$
If you want to change the norm, you can use the fact all norms are equivalent.