# 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?

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.

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.