Towards a proof of global convergence for Newton-like methods

Question

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!

Answer 1

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

Answer 2

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