% This code computes a matrix in the convex hull of {A_1,...,A_m}
% with minimum condition number, where and A_i are positive definite
% n by n matrices. It constructs input for SeDuMi to solve
%
% min  lambda_max(X)
% s.t. X - I >= 0, y >= 0, X = y_1*A_1 + ... + y_m*A*m.
%% 
% Input
% M       - a matrix whose ith column consists of the vector formed by 
%           stacking the columns of A_i one by one
%%
% Output
% t       - approximate minimum condition number
% time    - cpu time
%%
% March 5, 2011
% Written by Zhaosong Lu and Ting Kei Pong

function [t,X,time] = condition_se_dual2(M)
% s y

clear K

n = sqrt(size(M,1));
m = size(M,2);

At = zeros(2*n^2+m,1+m);
c = sparse(2*n^2+m,1);

At(1:m, 2:1+m) = -eye(m);
K.l = m;

At(m+1:n^2+m,2:end) = -M;
c(m+1:n^2+m,1) = -reshape(eye(n),n^2,1);

At(n^2+m+1:2*n^2+m,1) = -reshape(eye(n),n^2,1);
At(n^2+m+1:2*n^2+m,2:end) = M;
K.s = [n n]';

b = [-1 sparse(1,m)];

tic
[x,y] = sedumi(At,b,c,K);
time = toc;

y = y(2:m+1);
X = reshape(M*y,n,n);
t = cond(X/sum(y));
X = X/sum(y);

fprintf(' min condition number = %4.1f\n', t)