(This is from page 474 of Boyd & Vandenberghe's Convex Optimization, on algorithms for unconstrained minimization)
Assumptions
The function $f : \mathbb{R}^N \mapsto \mathbb{R}$ is convex and twice-differentiable and there exists an optimal point $x^*$ such that $f(x^*) \leq f(x)$ for all $x \in \text{dom}(f)$. Moreover, for $x_0$, which is the starting point for our algorithm we have that $S := \{ x \in \text{dom}(f) | \ f(x) \leq f(x_0) \}$ is a closed set. Finally it is assumed that $f$ is strongly convex on $S$, which means that there exists an $m > 0$ such that
\begin{equation}
\nabla^2 f(x) \succeq mI.
\end{equation}
Claim
Because of strong convexity, we have for $x,y \in S$
\begin{equation}
f(y) \geq f(x) + \nabla f(x)'(y-x) + \frac{m}{2} \parallel y-x \parallel^2_2
\end{equation}
and this inequality implies that the sublevel sets in $S$ are bounded. I do not understand where this final claim on boundedness comes from. (To be clear, I understand this inequality, just not the implication on bounded sublevel sets)
My attempt
Take a sublevel set $S' = \{y\ | \ f(y) \leq f(x) \} \subset S$. Then for $y \in S'$ the given inequality implies
\begin{equation}
0 \geq f(y) – f(x) \geq \nabla f(x)'(y-x) + \frac{m}{2} \parallel y-x \parallel^2_2
\end{equation}
and then somehow use this to show $y$ is bounded. Any help would be appreciated, I must be overlooking something.
Best Answer
You have
\begin{equation} f(y) \geq f(x) + \nabla f(x)'(y-x) + \frac{m}{2} \| y-x \|^2_2, \: \forall x,y \in S. \end{equation}
In particular, for $x=x^*,$ it is
\begin{equation} f(y) \geq f(x^*) + \nabla f(x^*)'(y-x^*) + \frac{m}{2} \| y-x^* \|^2_2, \: \forall y \in S. \end{equation} Since $x^*$ is a global minimum of $f$ it is $\nabla f(x^*)=0.$ That is,
\begin{equation} f(y) \geq f(x^*) + \frac{m}{2} \| y-x^* \|^2_2, \: \forall y \in S. \end{equation}
Now, by definition of $S,$ one gets
\begin{equation} f(x_0)\ge f(y) \geq f(x^*) + \frac{m}{2} \| y-x^* \|^2_2, \: \forall y \in S \end{equation} from where
\begin{equation} \| y-x^* \|^2_2\le \frac{2}{m}(f(x_0)- f(x^*)), \: \forall y \in S, \end{equation} which gives us the boundedness of $S.$