I'm trying to understand how finding the largest eigenvalue can be phrased as an SDP. More or less everything I know about SDP comes from here. The problem itself is on page $5$.
Given a PSD matrix $A$ with eigenvalues $\lambda_1 \geq \lambda_2 \ldots \geq \lambda_n$, it's clear that the eigenvalues of $tI – A$ are $t – \lambda_i$ (where $I$ represents the identity matrix). Then $tI – A$ has all positive eigenvalues only when $t \geq \lambda_1$. Thus
$$\lambda_1 = \text{min} \{ t \; | \; tI -A \succeq 0\}$$
Where I'm using $\succeq 0$ to mean the PSD ordering. I know SDP problems can take the form
\begin{align*}
\text{minimize} \quad & C \bullet X \\
\text{s.t} \quad & A_i \bullet X \geq b_i \quad i = 1, \ldots, m \\
& X \succeq 0 \\
\end{align*}
How can I phrase the first minimum as a minimum of this form? What are the $C,X,A_i, b_i$? Even further, if $A(x)$ is a PSD matrix given by a vector $x$, how could I phrase minimizing the largest eigenvalue of $A(x)$ as an SDP in this form? Again I'm not sure how to choose the $C,X$, etc. This comes from trying to understand this.
Best Answer
The easiest strategy here is to realize that SDP solvers solve SDPs defined by data $(b,C,A)$ defining the primal and dual pair, and they solve both simultaneously.
The primal (which you are trying to fit your model to)
\begin{align*} \text{minimize} \quad & C \bullet X \\ \text{s.t} \quad & A_i \bullet X = b_i \quad i = 1, \ldots, m \\ & X \succeq 0 \\ \end{align*}
and the dual
\begin{align*} \text{maximize} \quad & b^Ty \\ \text{s.t} \quad & C - \sum_{i=1}^m A_i y_i \succeq 0 \\ \end{align*}
The problem you are trying to solve is easily interpreted from the dual side
\begin{align*} \text{maximize} \quad & -t \\ \text{s.t} \quad & -A - (-I)t \succeq 0 \\ \end{align*}
I.e you already have data to send to the solver $(-1,-A,-I)$. The dual solution returned by the solver is your $t$.