Does a Lower Bounded Differentiable Function Always Have Arbitrarily Small Gradient? I am studying optimization and the following question occurred to me: Suppose $f:\mathbb{R}^n\to\mathbb{R}$ is differentiable and bounded below. Is it true that for every $\epsilon>0$, there exists $x\in\mathbb{R}^n$ such that $\|\nabla f(x)\|<\epsilon$?
I am able to show that this is true for $n=1$. Let $f^*=\inf_{x\in\mathbb{R}}f(x)$, then there exists a sequence $\{x_n\}$ such that $f(x_n)\to f^*$. There are two cases.
Case 1. If $\{x_n\}$ has a limit point $x^*$, then $f(x^*)=f^*$, so $x^*$ is a global minimizer and $f'(x^*)=0$.
Case 2. If $\{x_n\}$ does not have a limit point, then $|x_n|\to\infty$. By Mean Value Theorem, there exists $\xi_n$ such that $f(x_n)-f(0)=f'(\xi_n)x_n$. Thus $|f'(\xi_n)|=|f(x_n)-f(0)|/|x_n|\to0$.
In $\mathbb{R}^n$, the analysis of case 1 is the same, but case 2 does not generalize naturally, because MVT becomes $f(x_n)-f(0)=\nabla f(\xi_n)^\top x_n$. Is there a way to get around this?
 A: This is only a partial answer, but if we add the assumption that $\nabla f$ is Lipschitz. That is, $\lVert \nabla f(x) - \nabla f(y)\rVert \leq L \lVert x - y \rVert$ for some $L > 0$, we can use ideas from the analysis of gradient descent.
In particular, suppose that $\lVert \nabla f(x)\rVert \geq K > 0$ for all $x$.
The idea is now to construct a sequence $\{x_n\}$ such that $f(x_n)$ diverges to $-\infty$.
For this, chose any $x_1 \in \mathbf{R}^n$ and define recursively
$$
x_{n+1}
= x_n - \epsilon_n \frac{\nabla f(x_n)}{\lVert \nabla f(x_n) \rVert},
$$
where $\{\epsilon_n\}$ is a sequence such that $\sum_{n=1}^\infty \epsilon_n = \infty$, $\sum_{n=1}^\infty \epsilon_n^2 < \infty$ (a canonical choice is $\epsilon_n = 1/n$).
The mean-value theorem then yields that there is some $c_n \in [0, 1]$ such that, for $\xi_n = c_n x_{n+1} + (1-c_n) x_n = x_n - c_n\epsilon_n \nabla f(x_n) /\lVert \nabla f(x_n) \rVert$, we have that
\begin{align*}
f(x_{n+1})
&= f(x_n) + \nabla f(\xi_n)^T(x_{n+1} - x_n)
\end{align*}
But now, by our Lipschitz contition, we have
\begin{align*}
\lVert \nabla f(\xi_n) - \nabla f(x_n) \rVert
&\leq L \lVert \xi_n - x_n\rVert 
= L c_n \epsilon_n  
\leq L \epsilon_n 
\end{align*}
Combining the above equations, we get
\begin{align*}
f(x_{n+1})
&= f(x_n) + \nabla f(x_n)^T (x_{n+1} - x_n) + (\nabla f(\xi_n) - \nabla f(x_n))^T (x_{n+1} - x_n) \\
&\leq f(x_n) - \epsilon_n \lVert \nabla f(x_n)\rVert + \lVert \nabla f(\xi_n) - \nabla f(x_n) \rVert \epsilon_n \\
&\leq f(x_n) - K\epsilon_n + L \epsilon_n^2.
\end{align*}
Iterating this, we have that
\begin{align*}
f(x_{n+1}) \leq f(x_1) -K \sum_{k=1}^n \epsilon_n + L \sum_{k=1}^n \epsilon_k^2.
\end{align*}
Since $\epsilon_n$ is square-summable but not summable this means that $\limsup_{n\rightarrow\infty} f(x_n) = -\infty$ so that $f$ is not bounded below.
A: The answer is yes. This is in fact a special case of Ekeland's variational principle. See Theorem 2.2 of Ekeland's 1974 paper.
