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
    0 references
    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
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references