% L1 regularised multiple kernel Fisher discriminant analysis via 
% semi-infinite linear programming (SILP). Binary version.
% The LP problem in the beta step is solved using the Mosek toolbox.
% Fei Yan, f.yan@surrey.ac.uk, University of Surrey, UK, April 2009.

% Inputs
% "G": the cell containing centered kernel matrices
% "a": the indicator vector (see [1,2] for details)
% "lambda": regularization parameter
% "epsilon": tolerance parameter
% "max_iter": maximal number of iterations

% Outputs
% "alpha": the learnt coefficients of training samples
% "beta": the learnt weights of kernels
% "theta": value of the objective function in SILP
% "violation": normalised constraint violation

% References: 
% [1] Multiclass Discriminant Kernel Learning via Convex Programming. JMLR 2008
% [2] Lp Norm Multiple Kernel Fisher Discriminant Analysis for Object and Image Categorisationss. 
%     CVPR 2010


function [alpha beta theta violation] = l1_mk_fda_binary(G, a, lambda, epsilon, max_iter)


m = length(a);
n = length(G);

S = 1;
theta = -inf;
beta = ones(n, 1)/n;
violation = zeros(max_iter, 1);

cc = [zeros(n, 1); -1];
blx = [zeros(n, 1); -inf];
bux = [];
		
A = [ones(1, n) 0];
blc = [1];
buc = [1];
			
t = 0;
while(t < max_iter)
	
	t = t+1;

	% alpha step

	G_Sum = zeros(m, m);
	for j = 1:n
		G_Sum = G_Sum + beta(j, 1) * G{j};
	end
	b = 1/2 * eye(m) + 1/(2*lambda) * G_Sum;
	alpha = b \ a;
			
	for j = 1:n
		u(j, 1) = 1/(4*lambda) * (alpha'*G{j}*alpha);
	end
	v = 1/4*alpha'*alpha - alpha'*a;
	S = beta' * u + v;
			
	violation(t, 1) = abs(1-S/theta);
	if(violation(t, 1) <= epsilon)
		break;
	end
		
			
	% beta step
	
	A = [A; [u' -1]];
	blc = [blc; -v];
	buc = [buc; +inf];
		
	param =[];
	cmd = 'minimize echo(0)';
			
	[res] = msklpopt(cc, A, blc, buc, blx, bux, param, cmd);
	beta = res.sol.itr.xx(1:n);
	theta = res.sol.itr.xx(n+1);
end
