Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

An L1 estimation algorithm with degeneracy and linear constraints

Shi, M. and Lukas, M.A. (2002) An L1 estimation algorithm with degeneracy and linear constraints. Computational Statistics & Data Analysis, 39 (1). pp. 35-55.

PDF - Authors' Version
Download (224kB)
Link to Published Version:
*Subscription may be required


An implementation of the reduced gradient algorithm is proposed to solve the linear L1 estimation problem (least absolute deviations regression) with linear equality or inequality constraints, including rank deficient and degenerate cases. Degenerate points are treated by solving a derived L1 problem to give a descent direction. The algorithm is a direct descent, active set method that is shown to be finite. It is geometrically motivated and simpler than the projected gradient algorithm (PGA) of Bartels, Conn and Sinclair, which uses a penalty function approach for the constrained case. Computational experiments indicate that the proposed algorithm compares favourably, both in reliability and efficiency, to the PGA, to the algorithms ACM551 and AFK (which use an LP formulation of the L1 problem) and to LPASL1 (which is based on the Huber approximation method of Madsen, Nielsen and Pinar). Although it is not as efficient as ACM552 (Barrodale–Roberts algorithm) on large scale unconstrained problems, it performs better on large scale problems with bounded variable constraints.

Item Type: Journal Article
Murdoch Affiliation(s): School of Chemical and Mathematical Science
Publisher: Elsevier
Copyright: © 2002 Elsevier Science B.V
Item Control Page Item Control Page


Downloads per month over past year