% Solve SDP relaxation of random Max-Cut problem
%
% This script generates a random max-cut problem and solves the  
% semidefinite programming relaxation.
% 
%    minimize   trace LX
%    subject to diag X = e  (ones)
%                X >=0      (psd)
%

clear all
% The data. L (Laplacian) is Hermitian, 
n=10;
L=10*rand(n);
L=L+L';   % random symmetric matrix of weights
L(1:n+1:end)=0;
L=diag(sum(L))-L;   % Laplacian
b=ones(n,1);
  
disp('starting CVX')
% Construct and solve the model
cvx_begin sdp
    variable X(n,n) symmetric
    dual variable Z
    maximize( trace(  X*L  ) )
      diag(X) == b;
      X >= 0 : Z;
cvx_end
Z=full(Z);X=full(X);

% Display resuls
disp( 'The original matrix, L: ' );
disp( L )
disp( 'The optimal point, X:' );
disp( X )
disp( 'The optimal dual variable, Z:' );
disp( Z )
disp( 'min( eig( X ) ), min( eig( X ) ) (both should be nonnegative, or close):' );
disp( 'min( eig( Z ) ), min( eig( Z ) ) (both should be nonnegative, or close):' );
disp( sprintf( '   %g   %g\n', min( eig( X ) ), min( eig( Z ) ) ) );
disp( 'The optimal value, trace LX:' );
disp( trace( L * X ) );
disp( 'Complementary slackness: Z * X, should be near zero:' );
disp( Z(:)' * X(:) )
%%%%%%%
[u,d]=eig(X);
x=u(:,end);
disp( ' upperbound and lowerbound and relative error are: ')
disp( [ trace(L*X)  x'*L*x   (trace(L*X)-x'*L*x)/trace(L*X) ])
