1
$\begingroup$

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?

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

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.

$\endgroup$

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.