Beside the nice geometric proceeding a particular interest in this method is derived from the following observation: In Karmarkar's as well as in this algorithm one has to solve a linear equation system of the form A D2ATy = b. The solution of this system is the most time consuming part in linear programs. While in Karmarkar's method the entries of the diagonal Matrix D are the coordinates of the iteration point, the diagonal entries are either 0 or 1 in our method. Hence throughout this paper D is a purely combinatorial matrix which yields to reasonable numbers of rank one updates of the corresponding Cholesky factor of A D2AT. Moreover, the Cholesky factors become sparser than in Karmarkar's approach.
Math. Inst. der Universität zu Köln
The following versions are available: