Efficient implementation and benchmark of interior point methods for the polynomial L1 fitting problem

Interior point methods specialized to the L 1 fitting problem are surveyed and the affine-scaling primal method is presented. Their main features are highlighted and improvements are proposed for polynomial fitting problems. For such problems, a careful handling of data avoids storing of matrices fo...

Full description

Saved in:
Bibliographic Details
Published in:Computational statistics & data analysis 2000, Vol.35 (2), p.119-135
Main Authors: Oliveira, Aurelio R.L., Nascimento, Mário A., Lyra, Christiano
Format: Article
Language:English
Subjects:
Applied sciences
Data mining
Exact sciences and technology
Interior point methods
L1 curve fitting
L1 regression problems
L1-based statistical analysis
Linear inference, regression
Linear programming
Mathematical foundations
Mathematical programming
Mathematics
Numerical analysis
Numerical analysis. Scientific computation
Numerical approximation
Operational research and scientific management
Operational research. Management science
Probability and statistics
Sciences and techniques of general use
Statistics
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Interior point methods specialized to the L 1 fitting problem are surveyed and the affine-scaling primal method is presented. Their main features are highlighted and improvements are proposed for polynomial fitting problems. For such problems, a careful handling of data avoids storing of matrices for the interior point approaches. Moreover, the computational complexity of iterations is reduced. An inexpensive way to compute a basic solution, using interpolation, is also provided. Extensive numerical experiments are carried out, including comparisons with a specialized simplex method. In general, the interior point methods performed better than the simplex approach. Among the interior point methods investigated, the dual affine scaling version was the most efficient.
ISSN:0167-9473
1872-7352
DOI:10.1016/S0167-9473(00)00006-2