Large scale SDP

1

Hi, I have the following simple SDP problem to solve:

\min_{\mathbf{x},\mathbf{U},\mathbf{V}} \quad tr(\mathbf{U}+\mathbf{V})

\text{s.t.} \quad \quad\quad\sum_{i=1}^m x_i\mathbf{A}_i +\mathbf{A}_0 = \mathbf{U} - \mathbf{V}, \nonumber \\ \quad\quad\quad \quad \mathbf{U}, \mathbf{V} \succeq 0,\\ \quad\quad\quad\quad \mathbf{1}^T\mathbf{x}=1, \quad \mathbf{x} \succeq 0.

where \mathbf{x} \in \mathbf{R}^m; \mathbf{A}_i, \mathbf{U},\mathbf{V} \in \mathbf{S}_{+}^{n\times n} . When n =500, the Matlab simply goes out of memory because there are too many variables to optimise (2n^2+m). Does any one have experience with this?

2

What version and build of CVX are you using? There was a bug in 2.1 a few months ago that was causing generated SDPs to be larger and more expensive than necessary. And have you tried other solvers (MOSEK, SeDuMi, etc.)

That said, a 500x500 semidefinite cone has 125,250 variables, and you have two of those here. That’s not a large number of variables for a linear program, but it’s definitely large for an SDP.

The more significant cost, though, is the number of equality constraints. The complexity of each iteration depends cubically on that number. How many equality constraints does CVX report?

3

The cvx version is 2.0. When n=502, calling SDP 4.0: 631148 variables, 252388 equality constraints. Will it help to change the equality constraints to two inequality constraints?

4

I tried cvx version 2.1 with the latest build, SDPT3 and SeDuMi run out of memory again (more than 400 GB).

5

Oh my, CVX will definitely not be able to handle a problem of that size. You’ll need a Hessian-free method for this one, and I’m afraid I can’t help with that.

6

Are there some large scale SDP solvers available?