The algorithm to find the smallest $0 \leq \gamma$ such that $A \leq \gamma B$

Question

I am self-studying Heinz H. Bauschke and Walaa M. Moursi's "An Introduction to Convexity, Optimization, and Algorithms". I came across the first proposition in this book and I got so frustrated because even though I self-studied linear algebra from Gilbert Strang's course, I had never seen this algorithm before and the book provides no further reference nor any explanation for why is it true. The proposition is as follows:

Assume $A, B \in \mathbb{R}^{n \times n}$ are positive semidefinite. Suppose that there exists $0 \leq \beta $ such that $A \leq \beta B$. Then the smallest $0 \leq \gamma$ such that $A \leq \gamma B$ can be found as follows:

1- Find an orthonormal basis of eigenvectors $u_1,...\ , u_d$ corresponding to all nonzero eigenvalues of $B$. Assemble these in a matrix $U \in \mathbb{R}^{n \times d}$. If d = 0, then return $\gamma = 0$.

2- Obtain the Cholesky decomposition of $U^TBU = LL^T$.

3- Return $\gamma = \lambda_{max}(L^{-1}U^TAUL^{-T})$.

Can you please guide me on why this is true? Also, can you suggest any references that I can study that give me the background needed for such problems?

Disclaimer: I tried to find my question anywhere else but wasn't successful, so if it's a duplicate, give me a comment and I will remove it.

Answer 1

We have $$A - \gamma B \preceq 0 \iff U^\top (A - \gamma B) U \preceq 0.$$ Direction $\Rightarrow$ is clear, and for direction $\Leftarrow$, consider $$ x^\top (A - \gamma B) x.$$ If $x$ is in the column space of $U$, then there exists some $y$ such that $x = Uy$ and $$ x^\top (A - \gamma B) x = y^\top U^\top (A - \gamma B) U y \leq 0.$$ If $x$ is not in the column space of $U$, then $Bx = 0$, and $$ x^\top (A - \gamma B) x = x^\top A x \leq x^\top (\beta B) x = 0 \leq 0.$$ So, we investigate: $$U^\top (A - \gamma B) U = U^\top A U - \gamma LL^\top = L(L^{-1} U^\top A U L^{-\top} - \gamma I) L^\top.$$ Now since $L$ is invertible, we have $$L(L^{-1} U^\top A U L^{-\top} - \gamma I) L^\top \preceq 0 \iff L^{-1} U^\top A U L^{-\top} - \gamma I \preceq 0,$$ from which it follows that $\gamma$ should be the largest eigenvalue of $L^{-1} U^\top A U L^{-\top}$.

Edit: per the request of OP, I provide some additional clarification on the last step. I claim that $$L(L^{-1} U^\top A U L^{-\top} - \gamma I) L^\top \preceq 0 \iff L^{-1} U^\top A U L^{-\top} - \gamma I \preceq 0.$$ I shall prove the direction $\Leftarrow$. Let $y \in \mathbb{R}^k$. Since $L$ is invertible, there exists some $x$ such that $L^\top x = y$. Then $$ y^\top(L^{-1} U^\top A U L^{-\top} - \gamma I) y = x^\top L(L^{-1} U^\top A U L^{-\top} - \gamma I)L^\top x \leq 0.$$ Direction $\Rightarrow$ follows similarly. (if you want to read more about this principle, it can be found under the name 'similar matrices').

As for the entire problem, this is a specific instance of semidefinite programming (SDP). There are many surveys and textbooks on that if you are interested.