# For a positive function, can the length of gradient get arbitrarily close to 0?

Consider a differentiable function $$f:R^d\rightarrow R_+$$. Let $$a=\inf\limits_{x\in R^d} f(x)$$. It's evident that $$a\ge0$$.

Now if there exists $$x\in R^d$$ such that $$f(x)=a$$, then $$f'(x)=0$$.

If there doesn't exist $$x\in R^d$$ such that $$f(x)=a$$, can we prove that $$\forall \epsilon>0, \exists x\in R^d$$ such that $$|f'(x)|<\epsilon$$? Is there any relevant theorem?

• If $f$ is $C^1$ then the answer is yes. – copper.hat Oct 3 '18 at 5:03
• @copper.hat Can you give me any hint how to prove it? – Zhenduo Cao Oct 3 '18 at 13:52
• I suspect one could prove this using Peano's existence theorem applied to the system $\dot{x} = - \nabla f(x)$ and looking at the Lyapunov-like function $t \mapsto f(x(t))$. – copper.hat Oct 3 '18 at 16:29

Here is a roundabout way to prove this assuming that $$f$$ is $$C^1$$.

Suppose $$\|\nabla f(x)\| \ge \delta >0$$ for all $$x$$.

Pick some $$x_0$$ and apply steepest descent to $$f$$ starting at $$x_0$$. We will obtain a contradiction.

Let $$\lambda_k$$ be the largest $$\lambda \in \{1,{1 \over 2}, { 1\over 4},.. \}$$ such that $$f(x_k-\lambda \nabla f(x_k)) \le f(x_k) - {1 \over 2} \lambda \|\nabla f(x_k)\|^2$$ (cf. the Armijo step size rule). Since $$df(x_k, -\nabla f(x_k)) = -\|\nabla f(x_k)\|^2$$, we see that $$\lambda_k$$ is well defined as long as $$\nabla f(x_k) \neq 0$$. Let $$x_{k+1} = x_k - \lambda_k \nabla f(x_k)$$ and note that $$f(x_{k+1}) -f(x_k) \le -{1 \over 2}\lambda_k \|\nabla f(x_k)\|^2$$, hence non increasing.

Summing, we get $$f(x_n)-f(x_0) \le -{1 \over 2} \sum_i \lambda_{k=0}^{n-1} \|\nabla f(x_k)\|^2$$

Since $$f$$ is bounded below, we see that $$\sum_k \lambda_k \|\nabla f(x_k)\|^2$$ is bounded, and since $$\|\nabla f(x_k)\| \ge \delta$$, we see that $$\sum_k \lambda_k \|\nabla f(x_k)\|$$ is bounded and hence $$x_k \to x^*$$ for some $$x^*$$.

Since we have assumed that $$\nabla f(x^*) \neq 0$$ and $$\nabla f$$ is continuous, it is not hard to show that we must have $$\lambda_k \ge \lambda^* >0$$ for some $$\lambda^*$$ and for $$x_k$$ sufficiently close to $$x^*$$. In particular, this gives $$f(x_{k+1}) \le f(x_k) - {1 \over 2} \lambda^* \|\nabla f(x_k) \|^2 \le f(x_k) - {1 \over 4} \lambda^* \|\nabla f(x^*) \|^2$$ for sufficiently large $$k$$. However, this gives $$f(x_k) \downarrow - \infty$$ which contradicts continuity of $$f$$ at $$x^*$$.

Hence $$\inf_x \| \nabla f(x) \| = 0$$.