An algorithm for $l_1 $-norm minimization with application to nonlinear $l_1 $-approximation

Abstract

Necessary and sufficient conditions for minimizing an $l_1 $-norm type of objective function are derived using the nonlinear programming (NLP) approach. Broader sufficient conditions are made possible by using directional derivatives. It is shown that an algorithm previously proposed by Osborne and Watson (1971) for nonlinear $l_1 $-approximation falls under a prototype steepest descent algorithm. The $l_1 $-problem is converted to a sequence of problems, each of which involves the minimization of a continuously differentiable function. Based on this conversion and on the optimality conditions obtained, an algorithm that solves the $l_1 $-minimization problem is proposed. An extrapolation technique due to Fiacco and McCormick (1966) and (1968, p.188) is used to accelerate the convergence of the algorithm and to improve its numerical stability. To illustrate some of the theoretical ideas and to give numerical evidence, several examples are solved. The algorithm is then used to solve some nonlinear $l_1 $-approximation problems. A comparison between the Osborne-Watson algorithm and the proposed one is also presented.