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?


2 Answers 2


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .