Active set algorithms for isotonic regression; A unifying framework

Active set algorithms for isotonic regression; A unifying framework

0.00 Avg rating0 Votes
Article ID: iaor1991759
Country: Netherlands
Volume: 47
Issue: 3
Start Page Number: 425
End Page Number: 439
Publication Date: Aug 1990
Journal: Mathematical Programming (Series A)
Authors: ,
Abstract:

In this and subsequent papers the authors will show that several algorithms for the isotonic regression problem may be viewed as active set methods. The active set approach provides a unifying framework for studying algorithms for isotonic regression, simplifies the exposition of existing algorithms and leads to several new efficient algorithms. The authors also investigate the computational complexity of several algorithms. In this paper they consider the isotonic regression problem with respect to a complete order minimize equ1subject to equ2where each equ3is strictly positive and each equ4is an arbitrary real number. The authors show that the Pool Adjacent Violators algorithm is a dual feasible active set method and that the Minimum Lower Set algorithm is a primal feasible active set method of computational complexity equ5. They present a new equ6primal feasible active set algorithm. Finally the authors discuss Van Eeden's method and show that it is of worst-case exponential time complexity.

Reviews

Required fields are marked *. Your email address will not be published.