A question on problem scale

[Karl]

A question on problem scale

Hi everyone,

I use the following code solving a simple SDP:

A = rand(n,n);
P = sdpvar(n,n);
F = [P >= 0];
options = sdpsettings('solver','sedumi');
solvesdp(F,norm(P - A,1),options);

The above codes seems to work well when n == 10. However it halts with some error messages if n == 100. Why?

In addition, if we use a $l_2^2$ norm (ie.,(norm(P - A,2))^2) as the objective function, the model can not work at all. Why?

Thank you in advance for your replies.

[Johan Löfberg]

The first problem is a very very large problem. To begin with, when n=100, P will have 5050 variables. In addition to these variables, you will need yet another 5050 variables to model the 1-norm of the matrix. These variables are used in something like 10000 inequalities  to model the 1-norm. To summarize, it is simply a very hard problem.

The second case fails to begin with since you a squaring a norm operator. Squaring a convex operator does not necessarily yield a convex expression ( for instance (-2+norm(x))^2 is not convex), so YALMIP is not capable of recognizing that this actually can be expressed using a simple epigraph through its convexity propagation rules. However, no need to square the norm in the objective, just minimize the norm. Still, a very large problem since the Frobenious norm is the 2-norm of vec(P), which is a vector of length 10000., which thus yields a very large SOCP cone in SeDuMi.

[Karl]

Dear Johan,

Thank you very much for your explaining.