Convex function inequalities with gradient being Lipschitz continuous, starting from $f(y)\le f(x)+(\nabla f(x))^T(y-x)+\frac{L}{2}\Vert y-x\Vert_2^2$

520 Views Asked by At

Let $f$ be a continuously differentiable convex function defined on $\mathbb R^n$, i.e., $f :\mathbb R^n \rightarrow\mathbb R$ is continuously differentiable and for any $x,y \in\mathbb R^n$ and any $\alpha\in (0,1)$, $f(\alpha x + (1 -\alpha)y) \le \alpha f(x) + (1 -\alpha)f(y)$. Suppose that the gradient of $f$ is Lipschitz continuous, i.e., there exists a constant $L > 0$ such that $$\Vert\nabla f(x)-\nabla f(y)\Vert_2\le L\Vert x-y\Vert_2.$$ Prove the following inequalities: \begin{array} ((1).f(y)\le f(x)+(\nabla f(x))^T(y-x)+\frac{L}{2}\Vert y-x\Vert_2^2,~~~\forall x,y\in\mathbb R^n \\ (2).f(y)\ge f(x)+(\nabla f(x))^T(y-x)+\frac{1}{2L}\Vert \nabla f(y)-\nabla f(x)\Vert_2^2,~~~\forall x,y\in\mathbb R^n\\ (3).\frac{1}{L}\Vert \nabla f(y)-\nabla f(x)\Vert_2^2\le(\nabla f(y)-\nabla f(x))^T(y-x),~~~\forall x,y\in\mathbb R^n \end{array} $$$$ For the 1-dim case this is not hard, just use the Taylor expansion and the Lipschitz property can derive the whole 3 inequality. However, I don't know how to extend the results into $\mathbb R^n$ since I don't know how to deal with the 2-norms here. I think there're ways to deal with such kind of problem in convex analysis that I don't know. Are there any solutions or suggestions of solving these inequality? Thanks in advance!