smallest positive definite matrix Given positive (semi) definite matrices A and B, can we answer the question, what is Max c s.t. A - cB is positive (semi) definite for scalar c? In other words,
\begin{align}
\max_{c\in \mathbb{R}}~c \\
\text{subject to }A-cB>=0
\end{align}
Are there useful results to help a line search?
 A: Good News: Your question is well studied. 
(not so) bad news: There is no closed form solution in general. 
Note that $A-cB$ is positive (semi) definite for $c=0$, thus $0$ is a lower bound. Define $F=A-cB$. Let $\lambda_{min}(.)$ denote the minimum eigenvalue of its argument.
Closed Form Solution-- A closed form solution exists whenever $B$ is invertible and in that case, $c=\lambda_{min}(B^{-1}A)$. (please try on your own to prove it.)
Iterative Solution-- Whenever $B$ is not invertible, you will need resort to some other technique. The key observation here is that your problem is convex and belongs to the class of semi-definite programming. Thus, any standard convex package, for eg: CVX (search google), should be able to solve it. If you are insistent over a custom line search algorithm, make the observation that the one dimensional function $f(c)$, defined as
\begin{align}
f(c)=\lambda_{min}(A-cB)
\end{align}
is concave function of $c$ over the real line. It is monotonically non-increasing function of $c$, if one restricts it to the non-negative values for $c$, which is the interesting range for you. Note that $f(0)\geq 0$ Thus, you are interested in the point where $f(c)$ crosses the $x-axis$, thus the standard bisection algorithm given herel will definitely help. It basically finds the zero-crossing point of the input function which is you what you need here. 
A: Thanks for the thorough response. I don't follow the closed form solution though: We already know that c = 0 is a lower bound. But there is no guarantee that B^{-1}A is positive semi-definite, is there? Tried to prove it myself but arriving at the given answer seems to rely on A and B^{-1} commuting, which is not given.
