0
$\begingroup$

I am looking at theorems for two different situations for a differentiable function $f: \mathbb{R}^n \to \mathbb{R}$.

Theorem A
Let for $G \subseteq \mathbb{R}^n $ and $B$ open with $G \subseteq B \subseteq \mathbb{R}^n $, $f: B \to \mathbb{R}$ be continuously differentiable on $G$. If $x^*$ is a local minimum then $\forall d \in Z(x^*) $:

$$ \nabla f(x^*)^\top d \geq 0 $$

where $Z(x):= \{\lambda d \in \mathbb{R}^n |\forall \alpha \in [0,1]: x + \alpha d \in G, \lambda \in [0, \infty) \}$ is the cone of admissible directions.

The next one simply says

Theorem B
If $f: \mathbb{R}^n \to \mathbb{R}$ is continuously differentiable and $x^*$ is a local minimum, then $$\nabla f(x^*) = 0$$

I first encountered Theorem A and thought nothing of it. It seemed rational to me that if we are at a local minimum then the derivative there evaluated in any direction should be positive or $0$ i.e. be a direction of ascent. But after reading Theorem B I remembered that in univariate calculus the derivative at an extremum is always $0$.

So my question is, why is $\nabla f(x^*)^\top d$ not always equal to $0$ in the constrained case? What is an example for a local extremum in a constrained setting where $\nabla f(x^*) \neq 0$?

$\endgroup$
5
  • $\begingroup$ In Theorem A, is the minimum over all $x \in G$? $\endgroup$
    – angryavian
    Feb 8, 2022 at 16:07
  • $\begingroup$ If you consider the univariate function $f(x)=x$ and minimize it over the closed interval $[0,1]$, you will find that the minimizer is $x^* = 0$ but $f'(x^*) \cdot (1-0)= 1$ is not zero. $\endgroup$
    – angryavian
    Feb 8, 2022 at 16:08
  • $\begingroup$ @angryavian This is trivial in 1d and with a compact domain. But Theorem A doesn't say that $G$ needs to be compact. Or would you say that this gradient can only be unequal to $0$ when $G$ is compact? If so, please show me a proof. $x^*$ is just a local minimum in Theorem A. $\endgroup$
    – lpnorm
    Feb 8, 2022 at 16:33
  • $\begingroup$ If $x^*$ is in the interior of the constraint set, then the cone of admissible directions contains all directions; then the inequality in Theorem A holds for all $d$ and implies the gradient at $x^*$ is zero. The only case when the gradient is not zero in Theorem A is therefore if $x^*$ is on the boundary of the constraint set, where the cone of admissible directions is restricted. $\endgroup$
    – angryavian
    Feb 8, 2022 at 16:39
  • $\begingroup$ That makes sense, thanks. Please make it an answer! A non trivial example would also help me understand more $\endgroup$
    – lpnorm
    Feb 8, 2022 at 16:49

1 Answer 1

1
$\begingroup$

If $x^*$ is in the interior of the constraint set, then $Z(x^*)$ contains all directions. The inequalities in Theorem A then imply $\nabla f(x^*)=0$. (More generally, this is why Theorem B is a corollary of Theorem A.)

Thus, the only situation where $\nabla f(x^*) \ne 0$ in Theorem A is if $x^*$ lies on the boundary of the constraint set.

  • A univariate example like $f(x) = x$ with constraint set $[0,1]$ suffices to demonstrate this, as $x^*=0$ and $f'(x^*) = 1$.
  • For a multivariate example, take $f(x_1, x_2) = x_1$ on the unit disk $\{(x_1, x_2) : x_1^2 + x_2^2 \le 1\}$. Then $x^* = (-1, 0)$ and $\nabla f(x^*) = (1, 0)$. The theorem holds, since $Z(x^*) = \{(x_1, x_2) : x_1 \ge 0\}$.
$\endgroup$

You must log in to answer this question.

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