# Find all directions such that they decrease the function value after taking a small step towards that direction

Let $f: \mathbb{R}^n \rightarrow \mathbb{R}$ and all second partial derivatives of $f$ exist and are continuous over the domain of the function, mixed derivatives are continuous and hence $\forall i, j \frac{\partial}{\partial x_i} \frac{\partial f}{\partial x_j} = \frac{\partial}{\partial x_j} \frac{\partial f}{\partial x_i}$. Thus, a Hessian matrix exists and is symmetric.

Let the Hessian matrix be indefinite in $\mathbf{x_0}$ (i.e. $\exists \mathbf{r_1}: \mathbf{r_1^T}: \mathbf{H(\mathbf{x_0})} \mathbf{r_1} < 0$ and also $\exists \mathbf{r_2}: \mathbf{r_2^T}: \mathbf{H(\mathbf{x_0})} \mathbf{r_2} > 0$), therefore $\mathbf{x_0}$ is a saddle point of function $f$ and $\frac{\partial f}{\partial \mathbf{x}}(\mathbf{x_0}) = \mathbf{0}$.

Given a Hessian matrix, how do I find a direction $\mathbf{v}$ such that the very small step in that direction from $\mathbf{x_0}$ would lead to the decrease of the function? More formally, find $\mathbf{v}$ such that $\lim_{t \rightarrow 0+} f(\mathbf{x_0}) - f(\mathbf{x_0} + t \mathbf{v}) > 0$.

I am also given eigendecomposition of a matrix, i.e. all the eigenvalues $\lambda_i$ and the corresponding eigenvectors $\mathbf{c}_i$, which I am not sure how to use yet.

My understanding is that Hessian matrix $\mathbf{p^T} \mathbf{H(x_0)} \mathbf{p}$ represents $\lim_{t \rightarrow 0+} f(\mathbf{x_0}) - f(\mathbf{x_0} + t \mathbf{p}) > 0$. Am I correct?

If my assumption holds, my approach would be to solve $\mathbf{p^T} \mathbf{H(x_0)} \mathbf{p} < 0$ with respect to $\mathbf{p}$, but I would end up solving a system of quadratic nonequalities, which doesn't look very promising. Is there any way of getting the result $\mathbf{v}$ easier somehow using the eigenvector decomposition?

• It appears that $\mathbf x_0$ is intended to be a critical point of $f$. Is that the case? – amd Dec 18 '17 at 2:37

You are correct. By Taylor's theorem, you have $$f(x_0+tp) =f(x_0) +t\nabla f(x_0)^T p + \frac{t^2}{2}p^TH(x_0)p + o(t^2)= f(x_0) + \frac{t^2}{2}p^TH(x_0)p + o(t^2)$$ because of the fact that $\nabla f(x_0)=0$ by hipothesis. Now take any $p\in \Bbb R^n$ such that $p^TH(x_0)p<0.$ Such a $p$ always exists because of the indefinitness hipothesis. We now show that $p$ is a descent direction of $f$ at $x_0.$ Indeed, otherwise you would have
$$f(x_0+tp)\geq f(x_0)$$ for all $t$ small enough, and hence
$$0\leq \frac{f(x_0+tp)-f(x_0)}{t^2}= p^TH(x_0)p + \frac{o(t^2)}{t^2},$$ which is a contradiction when $t$ is small enough because $\frac{o(t^2)}{t^2} \to 0$ and $p^TH(x_0)p<0$ by construction. That being said, I can't imagine another way of finding a descent direction.