ellipsoid

[Enrico Gorgone]

Dear Sirs,

  I'm using Yalmip calling it from Matlab. The feasible region of my problem consists
of constraints of the type:

  \| S x - \gamma  \|^2 \leq 1 ,

where S  is a semidefinite matrix (nxn) and gamma is a n-vector. I did that, but when I have to write
about 100000 constraints, Matlab takes too much time.

This is a part of the code:

 >[ mA , nA ] = size(A);
 >[ mB , nB ] = size(B);

 >S = sdpvar( nA , nA , 'symmetric'); % variables
 >gamma = sdpvar( nA , 1 );
 >t = 0.5;
 
 >cons = S >= 0;
 >for i = 1 : mA
 >  for j = 1 : mB
 >   x = ( t * A( i , : ) + (1 - t ) * B( j , : ) )';
 >   cons = [ cons , norm( S * x - gamma , 2 ) <= 1 ];
 >  end
 > end

How could I overcome the problem?

All the best,
Enrico Gorgone

[Johan Löfberg]

A first step is to use the low-level cone operator to declare the norm constraints

cons = S >= 0;

for i = 1 : mA

    for j = 1 : mB

        x = ( t * A( i , : ) + (1 - t ) * B( j , : ) )';

        cons = [ cons , cone(S * x - gamma ,1) ];

    end

end

This can be further optimize by using the vectorized version

cons = S >= 0;

X = [];

for i = 1 : mA

    for j = 1 : mB

        x = ( t * A( i , : ) + (1 - t ) * B( j , : ) )';

        X = [X x];

    end

end

cons = [ cons , cone([ones(1,mA*mB);S * X - repmat(gamma,1,mA*mB)])];

For mA=nA=mB=nB=50, the generation of X takes 1 sec and cons takes 2sec, and solving using sedumi takes 10 minutes.

When dimensions go up, the symbolic multiplication of S and X will run into memory issues. At that point, you will have to give up the use of a modelling layer and code directly in SeDuMi format or similiar (or maybe try to partition the constraints and try to call cone twice etc)

(The generation of X can of course be optimized further, but that is a MATLAB issue, not YALMIP)

Some extrapolation: You talk about 1e5 constraints. Since this was 2500 constraints, you have 40 times as many constraints. Number of constraints is quadratic in dimension of A and B, thus you're about 6 times larger problem. Running some sizes seem to indicate O(n^4) to O(n^6) practical complexity, i.e., you are looking numbers in the range at 216 hours to 7776 hours :-)