Does a Lower Bounded Differentiable Function Always Have Arbitrarily Small Gradient?

Question

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?

Answer 1

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.

Answer 2

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.