A Global and Quadratic Affine Scaling Method for Linear $L_{1}$ Problems.

Abstract

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 $l_{1}$ problem (in which there are no feasibility constraints) to yield a globally convergent algorithm. We then show that the linear algorithm can be modified to provide a globally and ultimately quadratically convergent algorithm. This modified algorithm is significantly more efficient in practice: we present numerical results to support this claim.