separate_pt_poly.m
de096106547amaster

separate_pt_poly.m
View Options

			% Section 8.1.1: Separating a point from a polyhedron
			% Boyd & Vandenberghe "Convex Optimization"
			% Joelle Skaf - 10/09/05
			%
			% The goal is to produce a hyperplane separating x0 and the polyhedron
			% defined as {x \| Ax <= b}
			% minimize mu'x0 - b'lambda
			% A'*lambda = mu
			% norm(mu)* <= 1
			% lambda >= 0

			% Input data
			randn('seed',0);
			n = 10;
			m = 2*n;
			x0 = randn(n,1);
			A = randn(m,n);
			b = rand(m,1);

			% CVX solution
			fprintf(1,'Finding a separating hyperplane between the 2 polyhedra...');

			cvx_begin quiet
			variables muu(n) lambda(m)
			maximize ( muu'x0 - b'lambda )
			A'*lambda == muu;
			norm(muu) <= 1;
			lambda >= 0;
			cvx_end

			fprintf(1,'Done! \n');

			% Verification
			disp('------------------------------------------------------------------');
			disp('Note that 0 is in {x \| Ax <= b} by construction...' );
			disp('Verifying that x0 is separated from {x \| Ax <= b} i.e. mu^T*x0 > 0');
			disp([' mu^Tx0 = ' num2str(muu'x0) ]);