I was reading about Trust Region Methods for solving Nonlinear Optimization problems are came across this statement in my notes:
If the quadratic approximation to the function $f(x)$ which is given by $m(x+p)=f(x)+\nabla f(x)^Tp + 0.5p^T\nabla^2 f(x) p$ has $\nabla^2f(x)$ which is not positive definite, then the quadratic model is unbounded below.
I can't seem to appreciate why this is true.
I tried looking at it from the following perspective but that leads me to a dead end.
\begin{align} m(x+p)&=f(x)+\nabla f(x)^Tp + 0.5p^T\nabla^2 f(x) p\\\nabla^2f(x)&\not \succ 0\\ \exists y\;s.t.\;\\ y^T\nabla^2f(x)\;y&<0 \\ Let \;p&=y\\ m(x+y)&=\underbrace{f(x)}_{Known}+\underbrace{\nabla f(x)^Ty}_{?????} + \underbrace{0.5y^T\nabla^2 f(x) y}_{<0}\\ \end{align}
I disagree; it's the case where $Hf$ has a negative eigenvalue that is trivial.
Let $v$ be an eigenvector with negative eigenvalue. Then
$$m(x+vt) = f(x) + t\left[\nabla f(x) \cdot v\right] + t^2 \lambda/2$$ is a polynomial with negative leading coefficient, and so is unbounded below as $t\to\infty$.
When $Hf$ is positive semi-definite, it's trickier, and I don't think your statement is universally true. In particular, I claim that $m$ is bounded below if and only if all eigenvectors of $Hf$ with zero eigenvalue are orthogonal to $\nabla f(x)$.
Only if direction: let $v$ be an eigenvector with eigenvalue 0, and with $v\cdot \nabla f(x) \neq 0$. Since the sign of $v$ is arbitrary we can assume WLOG that $v\cdot \nabla f(x) < 0$, and then $$m(x+vt) = f(x) + t \left[\nabla f(x)\cdot v\right] + 0 \to -\infty$$ as $t\to\infty$.
If direction: Since $m$ is a polynomial, it suffices to show that $\lim_{t\to\infty} m(x+vt)$ is bounded below for all $v$. Expand $v$ in the eigenbasis of $Hf(x)$, with $v_0$ the component in the span of the eigenvectors with zero eigenvalue, and $v_+$ the component in the span of the eigenvectors with positive eigenvalue. Then $$m(x+vt) = f(x) + t\left[\nabla f(x)\cdot v_+\right] + t^2v_+^THf(x)v_+/2.$$ If $v_+=0$, $m(x+tv)$ is constant; otherwise, $m(x+vt)$ has positive leading coefficient, and $m(x+vt)\to\infty$ as $t\to\infty$.