The Nonlinear L1-Norm Estimation Problem

This chapter focuses on the special case of the general nonlinear L_p-norm estimation. The R. H. Bartels and A. R. Conn algorithm for nonlinear L₁-norm estimation is an extension of their earlier algorithm for solving linear L₁-norm estimation problems. From a computational point of view the nonlinear L₁- and L∞-norm estimation problems are the most difficult of the L_p-norm problems to solve. The reason for this is that the objective functions for these two problems have discontinuous derivatives. D. H. Anderson and M. R. Osborne couched the L₁- and L∞-norm problems within the framework of so-called polyhedral norms. The Murray and Overton algorithm is an application and adaptation of the modified Newton algorithm for linearly constrained nonlinear programming problems to solve L₁-norm problems. L₁-norm estimation has become a very popular tool. It is a satisfactory robust alternative to least squares.