L1 and L∞ minimization via a variant of Karmarkar´s algorithm

Simple iterative algorithms are presented for L₁ and L_∞ minimization (regression) based on a variant of Karmarkar´s linear programming algorithm. Although these algorithms are based on entirely different theoretical principles to the popular IRLS (iteratively reweighted least squares) algorithm, they have almost identical matrix operations. Also presented are the results of a Monte Carlo study comparing the numerical convergence properties of the Karmarkar algorithm for L₁ minimization to those of an IRLS and a simplex algorithm. The test problem involves L ₁ estimation of AR (autoregressive) model parameters. The Karmarkar algorithm outperformed IRLS by achieving higher numerical accuracy in fewer iterations. Techniques for reducing the computational cost per iteration of the Karmarkar L₁ algorithm are discussed