# 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!

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.$$
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}}.$$