A globally and quadratically convergent affine scaling method for linear \(l_ 1\) problems (Q1199751)

The paper deals with the piecewise linear \(\ell_ 1\) approximation problem \(\min\{\sum^ m_{i=1}| a^ T_ i x-b_ i| | x\in\mathbb{R}^ n\}\), \(a_ i\in\mathbb{R}^ n\), \(b_ i\in\mathbb{R}\). For an equivalent formulation as constrained \(\ell_ 1\) problem similar to inner point methods in linear optimization a descent algorithm is proposed, which looks for the direction of steepest descent under an affine scaling of coordinates preventing a too fast approach to points of nondifferentiability in contrast to the more familiar ``distance of the boundary condition'' used by barrier methods in nonlinear optimization. Exploiting the special structure of the problem appropriately chosen hybrid combinations of the proposed linear directions and local Newton directions yield a globally and ultimately quadratic algorithm under standard assumptions of nondegeneracy. In practice the refined algorithm seems to be more efficient than a straightforward inner point method applied to the dual of the problems' LPP equivalent as is suggested by numerical results.