5
$\begingroup$

Let $f:\mathbb{R}^n \mapsto \mathbb{R}$ be a differentiable function. Suppose $x^*$ is a local minimizer of $f$ along every line that passes through $x^*$. This means that the function $$g(\alpha) = f(x^* + \alpha d)$$ is being minimized for $\alpha = 0$ for any direction $d \in \mathbb{R}^n$. It is easy to show that this implies $\nabla f(x^*) = 0$.

The question is:

Is $x^*$ a local minimizer of $f$?

The answer is, it can be a local minimizer, maximizer, or a saddle point. I really don't get the reason. We are given that, for sufficiently small $\alpha>0$, $f(x^*) \leq f(x^* + \alpha d), \forall d \in \mathbb{R}^n$. Doesn't this also imply that $x^*$ is a local minimizer?

$\endgroup$
6
$\begingroup$

Here is a counterexample:

Consider $n=2$, $f(x,y)=(y+x^2)(y+2x^2)$ where and consider $(x^*, y^*)=(0,0)$.

\begin{align}g_d(\alpha)&=f(\alpha d_1, \alpha d_2)\\&= (\alpha d_2 + (\alpha d_1)^2)(\alpha d_2 + 2(\alpha d_1)^2)\\ &= \alpha^2(d_2+\alpha d_1^2)(d_2+2\alpha d_1^2)\\ &= \alpha^2(2d_1^4\alpha^2 + 3d_2d_1^2\alpha+d_2^2) \end{align}

We know that $g_d(0)=0$, let's study what happens when $\alpha \ne 0$.

If $d_2=0$, then we have $g_d(\alpha ) \ge 0$.

If $d_2 \ne 0$, note that $2d_1^4\alpha^2 + 3d_2d_1^2\alpha + d_2^2>0$ when $\alpha$ is small but non-zero, hence $g_d(\alpha)\ge 0$ near the zero neighborhood.

Hence $(0,0)$ is a local minimizer of $f$ along every line.

However,

$$f\left(x, -\frac32x^2\right) = \left(-\frac32x^2+x^2\right) \left(-\frac32x^2+2x^2\right)=-\frac14x^4\le 0$$

In particular, we can let $x$ be arbitarily small and non-zero.

Hence $(0,0)$ is not a local minimum.

enter image description here

$\endgroup$
7
  • $\begingroup$ Thanks for your answer! I also have a counter-example: $f(x_1, x_2) = (x_2 - x_1)^2(x_2 - 2x_1^2)$. However, I don't get the intuition. Can you please help me with the intuition? $\endgroup$ Apr 20 '20 at 14:15
  • $\begingroup$ I think counterexamples illustrate that even though we restrict it to a line, a point is a minimum along the restricton. However, if we draw a neighborhood, and draw a certain small curve, we can find a smaller value. $\endgroup$ Apr 20 '20 at 14:18
  • $\begingroup$ That's very hard to imagine... I always think like if $x^*$ is the minimum over each line, then it is local minimum, because any point in the very-small-ball around $x^*$ also is on a line from $x^*$. $\endgroup$ Apr 20 '20 at 14:28
  • 1
    $\begingroup$ not sure if a desmos link would help. $\endgroup$ Apr 20 '20 at 14:37
  • 1
    $\begingroup$ I think part of the intuition is that, in your statement about "sufficiently small $\alpha > 0$, the "sufficiently small" part is different for each direction. So for any given $\alpha$, there's a direction in which it is not small enough to prevent a decrease in $f$. $\endgroup$
    – prubin
    Apr 20 '20 at 16:07

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.