# Thread: karmarkar s algorithm - linear program

1. ## karmarkar s algorithm - linear program

I have been trying to implement karmarkars algorithm to solve a linear program using matlab.

My program doesn converge to a solution even after letting it run forever!
considering tht my current problem has only 7 variables i think something is wrong with my code.

i would be grateful if some1 could point out defects if you find any

please refer images for algorithm used, I was not able to type out the whole thing

thanks a ton!!!!!!!!!!!!!!!!!!!!!!!!!!!

Matlab code:

clc
clear

c=[-15;-6;-8;-1;0;0;0];

a=[10 05 25 03 01 00 00 ;
12 04 12 01 00 01 00 ;
07 00 00 01 00 00 01 ;];

b=[50;48;35];

N=size(a);
m=N(1)+1;
n=N(2)+3;
beta1=30;
c1=(-n/beta1)*b;
B=[a zeros(N(1),1) c1 -c1-a*ones(N(2),1); zeros(1,N(2)) 0 n 0];

d=[beta1*c' 0 0 100];

zo=(1/n)*ones(n,1);
z=zo;e=10;
dtr=norm(d)*sqrt(n*(n-1));
it=0;
while e>0.001
dz=diag(z);
p=[B*dz;ones(1,n)];
y=zo-(0.25/dtr)*((eye(n)-p'*inv(p*p')*p)*dz*d');
zn=zeros(n,1);
ndtr=0;
for i=1:n
ndtr=ndtr+(z(i)*y(i));
end

for i=1:n
zn(i)=z(i)*y(i)/ndtr;
end

if mod(it,100000)==0
y1=0;
end
it=it+1;
z=zn;
e=norm(d*z)
end

Hi dear