A relaxed version of Karmarkar's method (Q1108926)

This paper develops a relaxed version of Karmarkar's method and discusses relative theoretical problems for a class of interior-point methods. The relaxed algorithm uses inexact projections and has the same polynomial time complexity. At each step one solves inexactly a least-squares problem involving a basis for the null space of the constraint matrix instead of exactly solving the ``ball'' minimization problem. Implementational issues relevant to the method are discussed and computational results are also presented.