Let $A \succ 0$ and $B$ be $n\times n$ symmetric matrices. Find the largest scalar $\gamma \geq 0$ such that $$A + \gamma B \succeq 0$$
Here is my (failed) attempt:
The problem is: $$\max_{\gamma\ge 0} \gamma : v^\top(A+\gamma B)v \ge 0 \quad \forall v\in\mathbb R^n$$
Let $Au_i = \lambda u_i$ for $i=1,\dots,n$. And let $v=\sum_i \alpha_i u_i$.
The problem becomes: $$\max_{\gamma\ge 0} \gamma : \sum_i\alpha_i^2(\lambda_i+\gamma u_i^\top B u_i)\ge 0 \quad \forall \alpha$$
Since this must be true for all $\alpha$ this is true in particular for $\alpha=e_i^n$ where $e_j$ is the $j$th standard basis vector. Moreover, $\alpha_i^2$ is non-negative for all $\alpha$. Therefore, we have: $$\max_{\gamma\ge 0}\gamma:\lambda_i+\gamma u_i^\top Bu_i\ge 0 \quad \forall i$$
Now, if $u_i^\top Bu_i>0$, we have $-\frac{\lambda_i}{u_i^\top Bu_i}<0\le\gamma$, so we drop these cases.
We are left with cases when $u_i^\top Bu_i< 0$: $$\max_{\gamma\ge 0}\gamma:\gamma\le-\frac{\lambda_i}{u_i^\top Bu_i}\quad\forall i:u_i^\top Bu_i<0$$
Therefore, we have $$\gamma=\min_i-\frac{\lambda_i}{u_i^\top Bu_i}:u_i^\top Bu_i<0$$
If I make some numerical experiment, for example : $$A=\begin{bmatrix}3&2&1\\2&3&1\\1&1&2\end{bmatrix}\quad B=\begin{bmatrix}0&2&3\\2&0&2\\3&2&0\end{bmatrix}$$
I obtain $\gamma=\frac{1}{2}$. But, $$\begin{bmatrix}3&2&1\\2&3&1\\1&1&2\end{bmatrix}+\frac{1}{2}\begin{bmatrix}0&2&3\\2&0&2\\3&2&0\end{bmatrix}\not\succeq 0$$
So I guess I have made a mistake somewhere.
Anyone can help me ?
If $B$ is positive semidefinite, clearly $A+\gamma B\succeq0$ for every $\gamma\ge0$. Therefore the maximal $\gamma$ does not exist.
If $B$ is not positive semidefinite, note that $A+\gamma B\succeq0$ if and only if $I+\gamma A^{-1/2}BA^{-1/2}\succeq0$. Therefore you need $1+\gamma\lambda_\min(A^{-1/2}BA^{-1/2})\ge0$ and the maximum nonnegative $\gamma$ is given by $$ \dfrac{-1}{\lambda_\min(A^{-1/2}BA^{-1/2})}=\dfrac{-1}{\lambda_\min(A^{-1}B)}. $$
Apparently, the first step in your proof is already wrong. I don't see how the optimisation problem can be reformulated as $$\max_{\gamma\ge 0} \gamma : \sum_i\alpha_i^2(\lambda_i+\gamma u_i^\top B u_i)\ge 0 \quad \forall \alpha.$$ Cross terms such as $u_i^\top Bu_j$ are clearly missing in your reformulation.