I am trying to prove that a function $f:Z \mapsto \mathbb{R}$ is 1-strongly convex if and only if the function $f – \frac{1}{2}\|\cdot\|^2$ is convex.
Assuming that $f$ is strongly convex, I have by definition that for $\alpha \in (0,1)$
$$ f(\alpha x + (1-\alpha)y) \leq \alpha f(x) + (1 – \alpha)f(y) + \frac{\alpha(1-\alpha)}{2}\|x-y\|^2$$
I subtracted $\frac{1}{2}\|\alpha x + (1 – \alpha)y\|^2$ on both sides to get that $f – \frac{1}{2}\|\cdot\|^2$ is convex but didn't succeed… How to show the right hand side stays less than $$ \alpha [f(x) -\frac{1}{2}\|x\|^2 ] + (1 – \alpha)[f(y) – \frac{1}{2}\|y\|^2 ]?$$
I am also having a similar trouble proving the other implication…
Best Answer
Let $\sigma > 0$, $Z$ be a Hilbert space, and $f : Z \rightarrow (-\infty, +\infty]$ a function. It's required to show that $f$ is $\sigma$-strongly convex iff $f-\frac{\sigma}{2}\|.\|^2$ is convex.
By definiton, $f$ is $\sigma$-strongly convex if and only if $$ \begin{split} f(\alpha x + (1-\alpha)y) \le \alpha f(x) + (1 - \alpha)f(y) - \frac{\sigma}{2}\alpha(1-\alpha)&\|x-y\|^2,\\ &\forall (\alpha, x, y) \in [0, 1] \times Z^2. \end{split} $$
Now, one readily computes $$ \begin{split} &\alpha f(x) + (1 - \alpha)f(y) - \frac{\sigma}{2}\alpha(1-\alpha)\|x-y\|^2 - \frac{\sigma}{2}\|\alpha x + (1 - \alpha)y\|^2\\ &=\alpha (f(x) - \frac{\sigma}{2}\|x\|^2) + (1-\alpha)(f(y) - \frac{\sigma}{2}\|y\|^2) - \frac{\sigma}{2}R, \end{split} $$ where $R := \alpha (1 - \alpha)\|x-y\|^2 + \|\alpha x + (1-\alpha) y\|^2 - \alpha \|x\|^2 - (1 - \alpha) \|y\|^2.$
Exercise: Show by direct computation that $R = 0$. Conclude.