Towards a proof of global convergence for Newton-like methods Assume $B_k$ are positive definite with a uniformly bounded condition number, i.e., there is an $M$ such that
$$
||B_k||\cdot ||B_k^{-1}|| \leq M \quad \forall k\in\mathbb{N},
$$
$\nabla f(x_k) := \nabla f_k$, and
$p_k := -B_k^{-1} \nabla f_k$ is a descent direction.
The book (Numerical Optimization by Nocedal & Wright, 2nd ed, page 40) says it is easy to show
$$
\cos \theta_k := \frac{-\nabla f_k^T p_k}{||\nabla f_k || \cdot ||p_k||}
\geq \frac{1}{M}.
$$
How can I prove this?
I tried approaches using the Cholesky decomposition $B_k =L L^T$ and using
$||x|| \leq ||B_k^{-1}||\cdot ||B_k x||$, but to no avail. I think it should be a simple one liner that I'm not seeing? Any help is much appreciated!
 A: I assume $\|\,\cdot\,\|$ denote the euclidean norm and it's operator-norm.
Then, for a vector $x$ and the symmetric root $A=B^{1/2}$ we have
$$ \|x\|^2 = \|A^{-1}A x\|^2 \le \|A^{-1}\|^2 \|Ax\|^2 = \|B^{-1}\| x^T B x . $$
Thus, we have
$$ \frac{p^T B p}{\|Bp\| \|p\|} \ge \frac{\|p\|^2}{\|B^{-1}\| \|B\| \|p\|^2} = \frac1M. $$
A: I'm working really hard on the same problem. The Cholesky decomposition approach you mentioned really inspired me and I found a stronger inequality
$$
\cos(\theta_k) \geq \frac{1}{\sqrt{M}}.
$$
Here is my proof. Let $B_k^{-1} = R_k^T R_k$, then we get
$$
\nabla f_k^T B_k^{-1} \nabla f_k = \nabla f_k^T R_k^T R_k \nabla f_k = ||R_k \nabla f_k||^2. \qquad \qquad \qquad \qquad (1)
$$
Furthermore, since
$$
||\nabla f_k|| \leq ||R_k \nabla f_k||\ ||R_k^{-1}||
$$
and
$$
\ ||B_k^{-1} \nabla f_k|| = ||R_k^T R_k \nabla f_k|| \leq ||R_k^T||\ ||R_k \nabla f_k|| = ||R_k||\ ||R_k \nabla f_k||,
$$
we get
$$
||\nabla f_k ||\ ||B_k^{-1}\nabla f_k|| \leq ||R_k^{-1}|| \ ||R_k|| \ ||R_k \nabla f_k||^2. \qquad \qquad \qquad \qquad (2)
$$
Finally, combining Eqs. (1) and (2), we get
$$
\frac{\nabla f_k^T B_k^{-1} \nabla f_k }{||\nabla f_k ||\ ||B_k^{-1}\nabla f_k||} \geq
\frac{||R_k \nabla f_k||^2}{||R_k^{-1}|| \ ||R_k|| \ ||R_k \nabla f_k||^2} = \frac{1}{|| R_k||\ ||R_k^{-1}||} = \frac{1}{\sqrt{M}}.
$$
