cutsdpexplained.m

%% Optimize over manually approximated ball
sdpvar x y
X = [1 x y;[x;y] eye(2)];
Objective = -x-y;
ops = sdpsettings('plot.shade',.1,'verbose',0);
ballApproximation = [-1 <= [x y] <= 1];
clf;hold on
for k = 1:10  
  for i = 1:20
    vi = randn(3,1);
    ballApproximation = [ballApproximation, vi'*X*vi >= 0];  
  end
  plot(ballApproximation,[x;y],'blue',200,ops); 
  optimize(ballApproximation,Objective,ops);
  plot(value(x),value(y),'k*');drawnow
  drawnow
end 


%% Targeting cuts
ballApproximation = [-1 <= [x y] <= 1];
clf;hold on
for k = 1:10  
  optimize(ballApproximation,Objective,ops);
  [V,D] = eig(value(X));  
  vi = V(:,1);
  ballApproximation = [ballApproximation, vi'*X*vi >= 0];    
  plot(ballApproximation,[x;y],'blue',200,ops);   
  plot(value(x),value(y),'k*');
  drawnow
end 

%% Manual MISDP implementation
%% You need an SDP solver for first plot
clf
hold on
X = [1 x y;[x;y] eye(2)];
binvar d
plot([X >= 0, -1 <= [x y] <= 1, implies(d,x>=0.5),implies(1-d,x <= -0.5)]);
Model = [-1 <= [x y] <= 1, implies(d,x>=0.5),implies(1-d,x <= -0.5)];
for i = 1:10
    plot(Model,[x;y],'yellow',200,ops);
    optimize(Model,-x-y,ops);
    plot(value(x),value(y),'k*');drawnow    
    [V,D] = eig(value(X));
    v = V(:,1);
    Model = [Model, v'*X*v >= 0];
end

%% Using CUTSDP
Model = [X>=0,
        -1 <= [x y] <= 1, 
        implies(d,x>=0.5),implies(1-d,x <= -0.5)];
optimize(Model, Objective, sdpsettings('solver','cutsdp'));