function [xo,Ot,nS,lambda]=karmarkar(c,x,A,b,tol,mxit)
%   Solves the linear programming problem
%      min S(x)=c'x   subject to: A x <= b, x >= 0
%   using the Karmarkar's algorithm.
%
%   [xo,Ot,nS,lambda]=karmarkar(c,x0,A,b,tol,mxit)
%
%   c: coefficients of the objective function
%   x0: initial point (must be feasible)
%   A: constraint matrix
%   b: constraint vector
%   tol: tolerance (default = 1e-4)
%   mxit: maximum number of iterations (default = 100)
%   xo: optimal point
%   Ot: optimal value of S
%   nS: number of objective function evaluations
%   lambda: Lagrange multipliers

%   Copyright (c) 2001 by LASIM-DEQUI-UFRGS
%   $Revision: 1.0 $  $Date: 2001/08/15 23:05:15 $
%   Argimiro R. Secchi (arge@enq.ufrgs.br)

 if nargin < 4,
   error('karmarkar requires four input arguments');
 end
 if nargin < 5 | isempty(tol),
   tol=1e-4;
 end
 if nargin < 6 | isempty(mxit),
   mxit=100;
 end

[m,n]=size(A);
erro=norm(c);
gama=0.9995;
nS=0;
f=b-A*x;

if ~all(f),
   disp('starting point is not interior');
   return
end
   
while erro > tol & nS < mxit,
 nS=nS+1;
 iD2=diag(1./f.^2);
 d=-inv(A'*iD2*A)*c;
 dp=-A*d;
 z=-f./dp;
 j=find(z>0);
 alfa=gama*min(z(j));
 x=x+alfa*d;
 f=b-A*x;
 %plot3([x01(1);xo(1)],[x01(2);xo(2)],[x01(3);xo(3)],'ro')
 erro=norm(alfa*d);
end

% B=inv(A*A')*A;
% P=I-A'*B;
% lambda=-B*c;

xo=x;
Ot=c'*xo;
