A GLOBALLY AND QUADRATICALLY CONVERGENT AFFINE SCALING METHOD FOR LINEAR L(1) PROBLEMS

Recently, various interior point algorithms related to the Karmarkar algorithm have been developed for linear programming. In this paper, we first show how this "interior point" philosophy can be adapted to the linear l1 problem (in which there are no feasibility constraints) to yield a globally and linearly convergent algorithm. We then show that the linear algorithm can be modified to provide a globally and ultimately quadratically convergent algorithm. This modified algorithm appears to be significantly more efficient in practise than a more straightforward interior point approach via a linear programming formulation: we present numerical results to support this claim.