Let $f:\mathbb{R}^n\to\mathbb{R}, f\in C^2,
\overline{x}\in\mathbb{R}^n$ such that $\nabla f(\overline{x})=0$ but
$\nabla^2 f(\overline{x})$ is not semidefinite positive. Prove that
there exists a descent direction $d$ in $\overline{x}$
I think that the following theorem helps solving the exercise:
Theorem: let $f:\mathbb{R}^n\to\mathbb{R}, f\in C^2$. If $x^*$ is a
local minizer of $f$ in $\mathbb{R}^n$, then $\nabla f(x^*) = 0$ and
$\nabla^2 f(x^*)$ is semidefinite positive
So, since $x^*$ local minimizer $\implies$ $\nabla f(x^*) = 0$ and $\nabla^2 f(x^*)$ is semidefinite positive, the contrapositive in this case is that since $\nabla^2 f(x^*)$ is not semidefinite positive, we have that $x^*$ is not a local minimizer. Therefore, there exists a ball around $x^*$ such that for $x$ in the ball, $f(x)<f(x^*)$. Since it's a ball, we can pick any direction $d$ inside this ball, starting from $x^*$ such that $x^*+\lambda d$ is still in the ball. It's just a matter of picking the right $\lambda$. Therefore there exists a descent direction $d$
Second proof attempt:
$$f(x+p) = f(x) + p^t\nabla f(x) + \frac{1}{2}p^t\nabla^2f(x+tp)p$$
for some $t\in (0,1)$ by taylor's theorem.
We know that $h^t\nabla^2f(x+rh)h<0$ for small $r$. By the taylor expansion:
$$f(x+rp) = f(x) + rp^t\nabla f(x) + \frac{1}{2}rp^t\nabla^2f(x+rtp)rp$$
for $t\in(0,1)$.
Then by doing $\overline{t} = rt$:
$$f(x+rp) = f(x) + rp^t\nabla f(x) + \frac{1}{2}r^2p^t\nabla^2f(x+\overline{t}p)p$$
for $\overline{t}\in(0,r)$.
We end up with:
$$f(x+rp) = f(x) + \frac{1}{2}r^2p^t\nabla^2f(x+\overline{t}p)p$$
but the last term is negative by what I said in the beggining. Therefore, $f(x+rp)<f(x)$ for small $r$, so $p$ is our descent direction.
Best Answer
Suppose $A$ is not positive semi definite, then there is some $h$ such that $h^TAh < 0$.
This is an application of Taylor's theorem and continuity.
By continuity of the Hessian $H(x)$ we see that there is some neighbourhood of $\bar{x}$ such that $h^T H(x) h < -\delta = {1 \over 2} h^T H(\bar{x}) h$.
Let $\phi(t) = f(\bar{x}+th)$, then Taylor gives $\phi(t) = \phi(0)+ \phi'(0) t + {1 \over 2} \phi''(\xi) t^2$ for some $\xi \in (0,t)$.
Since $\phi'(0) = 0, \phi''(\xi) = h^T H(\bar{x}+ \xi h) h$, we see that $f(x+th) \le f(x) - {1 \over 2} \delta t^2$ for small $t$.
Note that both $h$ and $-h$ are descent directions.
The integral form of the theorem gives an explicit formula, but is messier to type :-).