# Transforming semidefinite program into generalized eigenvalue problem (GEVP)

Suppose we have the following optimization problem on $$r\in \mathbb{R}$$ with constraint on positive definite matrices $$A,B$$

$$\begin{eqnarray} \text{minimize } &\; r\\ \text{subject to } &\; A \prec r B \end{eqnarray}$$

What is a good way to show that solution is the largest generalized eigenvalue, using the definition of generalized eigenvalue from page 102 of Boyd & Vandenberghe's Convex Optimization:

• Small technical detail is that you should have a non-strict inequality, as the generalized eigenvalue if the value $r$ for which the inequality no longer is strict, i.e. the value for which $\det (A-rB)=0$ Commented Sep 15, 2020 at 6:08
• According to page 10 of this book, it's already a GEVP. Or am I missing something? Commented Sep 15, 2020 at 14:33
• Thanks for the reference! Updated question for clarity Commented Sep 15, 2020 at 16:15

It's important to note that by assumption of $$A\in S^n$$ and $$B\in S^n_{++}$$ (e.g. that $$A$$ is symmetric and $$B$$ is symmetric positive definite). Then
$$A\prec r B \iff \sup_{\|u\|_2 =1 }u^T(A-rB)u < 0. \quad (*)$$ Define $$\bar u$$ by the generalized eigenvalue (the $$u$$ that achieves the supremum in $$(*)$$). Since $$B$$ is symmetric positive definite, then for any $$u\neq 0$$, $$u^TBu> 0$$, so $$(*)$$ is equivalent to $$\frac{\bar u^TA\bar u}{ \bar u^TB\bar u } < r.$$ Since the problem is to minimize $$r$$, the optimal solution to the SDP is in fact $$\frac{\bar u^TA\bar u}{ \bar u^TB\bar u } = r.$$
It is left to show that $$\frac{\bar u^TA\bar u}{ \bar u^TB\bar u } = \sup_u \frac{u^TAu}{ u^TBu }=\lambda_{\max}(A,B) .$$ Assume that it is not true, e.g. there exists $$\hat u$$ where $$\frac{\hat u^TA\hat u}{\hat u^TB\hat u} - \xi= \frac{\bar u^TA\bar u}{ \bar u^TB\bar u } = r, \quad \xi > 0.$$ Then $$\hat u^T(A-rB)\hat u = \xi \hat u^TB\hat u> 0 > \sup_{\|u\|_2=1}u^T(A-rB)u$$ which is not possible. Therefore $$\lambda_{\max}(A,B) = r$$.