Karmarkar算法及其变形

研究如下形式的LP minc~Tx, s.t.Ax=0,(1) e~Tx=1,x≥0。其中A为m×n的行满秩矩阵,e=(1,…,1)~T∈R~n。已知x~0=(x_1~0,…,x_n~0)~T为(1)的一个严格可行内点。令Ω={x|x∈R~n,Ax=0},S={x|x∈R~n,e~Tx=1,x≥0},D=diag{x_1~0,…,x_n~0}。我们用统一的观点和方法导出K法和MK法。对(1)进行投影变换T: (?)x∈R~n,有 T(x)=y=(D~(-1)x/(e~TD~(-1)x))。 (2)