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?

  • 2
    $\begingroup$ If $f$ is $C^1$ then the answer is yes. $\endgroup$ – copper.hat Oct 3 '18 at 5:03
  • $\begingroup$ @copper.hat Can you give me any hint how to prove it? $\endgroup$ – Zhenduo Cao Oct 3 '18 at 13:52
  • $\begingroup$ 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))$. $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.