% Exemplo do algoritmo de Karmarkar
% Edgar & Himmelblau, 1988
% 
%  min c'x 
%      A x = b
%       x >= 0

c=[1; 2; 3];
A=[1  1  1];
b=1;
x0=[1; 1/3; 1/3]
erro=norm(c);
I=eye(3);
gama=0.98;
k=0;
iter=100;

while erro > 1e-4 & k < iter,
 k=k+1;
 v=b-A*x0;
 Dv=diag(v);
 dp=-inv(A'*Dv^(-2)*A)*c;
 hv=-A*dp;
 if any(hv >= 0), break; end
 z=-v./hv;
 j=find(z>0);
 alfa=gama*min(z(j))
 x1=x0+alfa*dp
 D=diag(x1);
 x0=x1;
 erro=norm(dp)
end
