Active set algorithms for isotonic regression; a unifying framework (Q752010)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Active set algorithms for isotonic regression; a unifying framework |
scientific article |
Statements
Active set algorithms for isotonic regression; a unifying framework (English)
0 references
1990
0 references
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.
0 references
isotonic regression problem
0 references
pool adjacent violators algorithm
0 references
active set method
0 references
minimum lower set algorithm
0 references
0 references
0 references
0 references
0 references