Memory issues in log det maximization


(Francisco Lourenço) #1

I’m trying to solve

variable w(n,n) symmetric nonnegative;
variable theta nonnegative;
delta=diag(sum(w))-w+eye(n)*theta;
maximize( log_det(real(delta)) - trace(delta*covar) - (beta/m)*sum(abs(w(:))) );
With covar being an n \times n covariance matrix.

Even without any additional constraints I can’t solve this problem for any decently high value of n due to memory problems. Even n=100 will result in the optimization failing due to CVX trying to create a matrix that’s several GB larger than my computer’s RAM. Is there any way I can avoid these memory issues or is that just always going to be a problem when trying to solve something like this through the successive approximation method?


(Mark L. Stone) #2

I solved this for n =100, as shown below, with MATLAB process growing to about 12 GB using CVXQUAD’s exponential.m replacement, calling SDPT3. This requires installing CVXQUAD https://github.com/hfawzi/cvxquad3 and its exponential.m replacement for CVX’s version, as described on the CVXQUAD page.

CVXQUAD forms quantity proportional to m+k (m and k are the Pade approximant parameters) of 2 by 2 LMIs, which I believe CVX will handle as second order cones. Reducing m and k to 2 from the default 3 (this may require going in to adjust the CVXQUAD code), and which reduces the Pade approximant accuracy, will therefore reduce the number of second order cones.

I had to rewrite the log_det term, introducing additional variables t and u, in order to explicitly invoke CVX’s exponential cone and get CVXXQUAD’s Pade approximant to be invoked.

I don’t know what the net memory savings, if any, of the CVXQUAD version is, but it should run faster and be more reliable than CVX’s successive approximation method. You could also try CVX 3.0 beta with SCS as solver, which is first order. That might allow larger problems to be solved and should also avoid CVX’s successive approximation method…

n=100; covar=rand(n);covar=covar*covar';beta=1;m=1;
cvx_begin
variable w(n,n) symmetric nonnegative;
variable theta nonnegative;
variables t u;
delta=diag(sum(w))-w+eye(n)*theta;;
maximize( t - trace(delta*covar) - (beta/m)*sum(abs(w(:))) );
{t/n,1,u} == exponential(1); 
det_rootn(real(delta)) >= u;
cvx_end

Edit: I just notice the abs applied to w(:), which was declared nonnegartive, so is unnecessary. Getting rid of the abs (and I got rid of the real, which I don’t think matters) reduces the SFPT3 problem size from 45478 variables, 20212 equality constraints to 25378 variables, 10112 equality constraints, and reduced maximum MATLAB process size to under 4GB. CVX modeling and solution time was cut from 1520 to 766 sec. And this is all for the CVXQUAD pade approximant (didn’t try successive approximation method for n = 100).


(Francisco Lourenço) #3

Thanks for the help. I had already tried SCS but I was having problems with CVX 3.0 which was saying that my problem was unbounded.


(Mark L. Stone) #4

CVX 3.0beta does have some bugs.