ex_5_39.m
de096106547amaster

ex_5_39.m
View Options

This document is not UTF8. It was detected as Shift JIS and converted to UTF8 for display.

			% Exercise 5.39: SDP relaxations of the two-way partitioning problem
			% Boyd & Vandenberghe. "Convex Optimization"
			% Jo?le Skaf - 09/07/05
			% (a figure is generated)
			%
			% Compares the optimal values of:
			% 1) the Lagrange dual of the two-way partitioning problem
			% maximize -sum(nu)
			% s.t. W + diag(nu) >= 0
			% 2) the SDP relaxation of the two-way partitioning problem
			% minimize trace(WX)
			% s.t. X >= 0
			% X_ii = 1

			% Input data
			randn('state',0);
			n = 10;
			W = randn(n); W = 0.5*(W + W');

			% Lagrange dual
			fprintf(1,'Solving the dual of the two-way partitioning problem...');

			cvx_begin sdp
			variable nu(n)
			maximize ( -sum(nu) )
			W + diag(nu) >= 0;
			cvx_end

			fprintf(1,'Done! \n');
			opt1 = cvx_optval;

			% SDP relaxation
			fprintf(1,'Solving the SDP relaxation of the two-way partitioning problem...');

			cvx_begin sdp
			variable X(n,n) symmetric
			minimize ( trace(W*X) )
			diag(X) == 1;
			X >= 0;
			cvx_end

			fprintf(1,'Done! \n');
			opt2 = cvx_optval;

			% Displaying results
			disp('------------------------------------------------------------------------');
			disp('The optimal value of the Lagrange dual and the SDP relaxation fo the ');
			disp('two-way partitioning problem are, respectively, ');
			disp([opt1 opt2])
			disp('They are equal as expected!');