Active set algorithms for isotonic regression; a unifying framework (Q752010)

Considered is the isotonic regression problem with respect to a complete order \[ (IRC)\quad \text{ minimize } \sum^{n}_{i=1}w_ i(y_ i- x_ i)^ 2\text{ subject to } x_ 1\leq x_ 2\leq...\leq x_ n, \] where each \(w_ i\) is strictly positive and each \(y_ i\) is an arbitrary real number. It is shown that the pool adjacent violators algorithm is a dual feasible active set method; the minimum lower set algorithm is a primal feasible active set method; and that the minimum lower set algorithm requires \(O(n^ 2)\) elementary arithmetic operations. The authors describe a new primal feasible active set method and show that it requires only O(n) elementary arithmetic operations. It is also shown that the Van Eeden's algorithm is a recursive method with a low rate of convergence and that it is of exponential average time complexity.