# Local minimization of a function over a line

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?

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.

• 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? – independentvariable Apr 20 '20 at 14:15
• 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. – Siong Thye Goh Apr 20 '20 at 14:18
• 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^*$. – independentvariable Apr 20 '20 at 14:28
• not sure if a desmos link would help. – Siong Thye Goh Apr 20 '20 at 14:37
• 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$. – prubin Apr 20 '20 at 16:07