In my optimization lecture notes I have the following definition:
Definition: Let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ be differentiable. The $f$ is strongly convex it $\exists$ a positive constant $\alpha > 0$ such that
$$
\langle \nabla f(y) – \nabla f(x),y-x \rangle \geq \alpha||y-x||^2 \qquad,\forall x,y \in \mathbb{R}^n \tag{1}
$$
However, in the Online Linear Optimization via Smoothing on page 2, it says the function is $\beta$-strongly convex if
$$
f(y) -f(x) – \langle \nabla f(x),y-x \rangle \geq \frac{\beta}{2}||y-x||^2 \qquad \forall x,y \in \mathbb{R}^n \tag{2}
$$
How can we show that (1) is equivalent to (2) with appropriate choice of $\beta$?
Best Answer
Let’s take $(1)$ and write $g_1=f-\frac{\alpha}{2}\|\cdot\|_2^2$. Then $(1)$ is equivalent to $\langle \nabla g_1(y)-\nabla g_1(x),\,y-x \rangle \geq 0$, ie $g_1$ convex.
Do the same for $(2)$ with $g_2= f-\frac{\beta}{2}\|\cdot\|_2^2$.