I am learning this book: Optimization for Data Analysis. I am not familiar with calculating the Euclidean norm, and it is too abstract for me. So, I am struggling with the exercise 8-(a) in Chapter 2:
Suppose that $f$: $\mathbb{R}^n \rightarrow \mathbb{R}$ is an $m$-strongly convex function with $L$-Lipschitz gradient and (unique) minimizer $x^*$ with function value $f^* = f (x^*)$. Show that the function $q(x) := f (x)− \frac{m}{2}||x||^2$ is convex with $(L−m)$-Lipschitz continuous gradients.
The convexity can be directly proved by the definition of $m$-strongly convexity. However, it is hard to prove that it is $(L−m)$-Lipschitz continuous gradients. I try to simplify $$||\nabla q(x)-\nabla q(y)||=||\nabla f(x)-\nabla f(y)-m(x-y)||,$$ and apply triangle inequality : $||a\pm b|| \le ||a||+||b||$, but it can not prove it.
How can this part be proved? Please give any suggestions. Thanks!
I might get the proof:
First, we have $$ \nabla q(x) = \nabla f(x) -mx, $$ and $$ 2<x_0,x> + ||x-x_0||^2-||x||^2-||x_0||^2= 0\\ \Leftrightarrow m<x_0,x> + \frac{m}{2}||x-x_0||^2-\frac{m}{2}||x||^2-\frac{m}{2}||x_0||^2= 0 $$ Since $f$ is with $L$-Lipschitz gradient, we have $$ f(x)\le f(x_0)+<\nabla f(x_0), x-x_0> + \frac{L}{2}||x-x_0||^2. $$ For above inequality, add $0$ on the left-hand side, and add $m<x_0,x> + \frac{m}{2}||x-x_0||^2-\frac{m}{2}||x||^2-\frac{m}{2}||x_0||^2$ on the right-hand side, i.e., $$f(x)\le f(x_0)+<\nabla f(x_0), x-x_0> + \frac{L}{2}||x-x_0||^2 - (m<x_0,x> + \frac{m}{2}||x-x_0||^2-\frac{m}{2}||x||^2-\frac{m}{2}||x_0||^2). $$ Easy to prove that $$ <\nabla f(x_0), x-x_0> - (m<x_0,x> + \frac{m}{2}||x-x_0||^2-\frac{m}{2}||x||^2-\frac{m}{2}||x_0||^2)= \frac{m}{2}||x||^2-\frac{m}{2}||x_0||^2+<\nabla f(x_0)-mx_0, x-x_0> - \frac{m}{2}||x-x_0||^2. $$ So, we can get $$ f(x)\le f(x_0)+\frac{m}{2}||x||^2-\frac{m}{2}||x_0||^2+<\nabla f(x_0)-mx_0, x-x_0> + \frac{L-m}{2}||x-x_0||^2\\ \Leftrightarrow f(x)-\frac{m}{2}||x||^2\le f(x_0)-\frac{m}{2}||x_0||^2+<\nabla f(x_0)-mx_0, x-x_0> + \frac{L-m}{2}||x-x_0||^2\\ \Leftrightarrow q(x)\le q(x_0)+<\nabla q(x_0), x-x_0> + \frac{L-m}{2}||x-x_0||^2.\\ $$ Because $q(x)$ is convex, the above inequality is an equivalent Lipschitz continuous gradient condition with $(L-m)$-Lipschitz gradient.