2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ You should be aware that SDP's have a duality theory. It is easiest to formulate this particular problem using the form that is dual to the form you mention in your question. Try an SDP of the form of (12.3) in the lecture notes that you've linked to. $\endgroup$ Commented Apr 16, 2021 at 4:25
  • $\begingroup$ I see that it mentions the form (12.3) and it's semi clear to me how to get between these, but it's equally unclear to me how to phrase it in the form (12.3). $\endgroup$ Commented Apr 16, 2021 at 4:38

2 Answers 2

Reset to default
6
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ This answer is exactly what I was hoping for but now I think I'm misunderstanding something more basic. The matrices $C,A_i$ need to be PSD for $C - \sum_{i=1}^m A_i y_i \succeq 0$ to even make sense right? But $-A,$ and $-I$ are very clearly negative semidefinite? Is this a trivial detail? $\endgroup$ Commented Apr 21, 2021 at 1:01
  • 1
    $\begingroup$ Yes, you are missing something as the individual matrices do not have to satisfy anything but symmetry. $-A - (-I)t \succeq 0$ is equivalent to $tI \succeq A$ which is precisely the intended model, feasible when $t$ larger than the largest eigenvalue of $A$. $\endgroup$ Commented Apr 21, 2021 at 5:19
2
$\begingroup$

The trick is to formulate the constraints such that $X$ becomes: $$X = \begin{pmatrix}t^{+} & 0 & O \\ 0 & t^{-} & O \\ O & O & tI-A \end{pmatrix},$$ with the interpretation $t = t^+ - t^-$. You can then take $$C = \begin{pmatrix}1 & 0 & O \\ 0 & -1 & O \\ O & O & O \end{pmatrix}.$$ You need $2$ inequality constraints per element of $A$ to set the $tI-A$ block in $X$. For example, to set $X_{33}$ equal to $(tI-A)_{11}$ you need the inequalities $X_{33} - t \geq -A_{11}$ and $-(X_{33} - t) \geq A_{11}$:

$$ \begin{pmatrix}-1 & 0 & 0 & O \\ 0 & 1 & 0 & O \\ 0 & 0 & 1 & O \\ O & O & O & O \end{pmatrix} \bullet X \geq -A_{11} $$

$$ \begin{pmatrix}1 & 0 & 0 & O \\ 0 & -1 & 0 & O \\ 0 & 0 & -1 & O \\ O & O & O & O \end{pmatrix} \bullet X \geq A_{11}. $$

Naively you could generate $2n^2$ constraints, but due to symmetry you only need $2 \cdot 0.5 n(n+1)$.

As pointed out in the comments, this formulation is very inefficient because it has variables. The off-diagonal elements of $X$ are constrained to fixed values, but solvers do not take advantage of this and just treat those elements as variables.

$\endgroup$
7
  • $\begingroup$ Ah! I thought it would be something like on constraint per element of $A$, but this also seemed very inelegant and clunky and I wasn't sure of the details. Thank you very much. $\endgroup$ Commented Apr 16, 2021 at 15:05
  • 2
    $\begingroup$ Do note that this is an extremely inefficient representation of the problem, as the primal side is the wrong way to attack this problem. Maybe you focused on this form as this was what the OP used, but it is not the way you would want to do it. $\endgroup$ Commented Apr 16, 2021 at 17:50
  • 1
    $\begingroup$ As you write, you model has $m=O(n^2)$ primal constraints/dual variables. If you formulate in dual space as in my answer, you have m=1 dual variable/primal constraints. The solver solves linear systems of equations for line searches which is $O(m^3)$ $\endgroup$ Commented Apr 16, 2021 at 18:38
  • 2
    $\begingroup$ I think you are missing how SDPs are represented and solved. The dimension of the cone (here $n$) is not something which necessarily relate to the number of dual variables (size of $y$ = number of primal equality constraints on the cone $X$= m). Complexity depends on both cone dimension (as you have to perform $O(n^3)$ linear algebra on those when doing line searches etc) and the problem complexity $m$ (which defines how large $O(m^3)$ linear systems of equations you solve), and these two combined when constructing the Hessian in $O(n^2m^2)$. $\endgroup$ Commented Apr 16, 2021 at 19:01
  • 2
    $\begingroup$ To summarize, Johan's formulation has m=1 and n equal to the dimension of the matrix A. The alternative formulation by LinAlg has m=n^2+n and a matrix of size slightly larger than n (because of the 1x1 blocks) Johan's formulation is much more efficient. Modeling systems like Yalmip and CVX will sometimes switch to a dual formulation for exactly this reason. $\endgroup$ Commented Apr 16, 2021 at 21:20

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.