ACTIVE SET ALGORITHMS FOR ISOTONIC REGRESSION - A UNIFYING FRAMEWORK
ACTIVE SET ALGORITHMS FOR ISOTONIC REGRESSION - A UNIFYING FRAMEWORK
复制标题
DOI：
10.1007/bf01580873
复制
发表时间：
1990-08-01
影响因子：
2.7
通讯作者：
CHAKRAVARTI, N
中科院分区：
文献类型：
--
作者：
BEST, MJ;CHAKRAVARTI, N
在本论文和后续的论文中，我们将展示等渗回归问题的几种算法可以被视为活动集方法。活动集方法为等渗回归算法的研究提供了一个统一的框架，简化了现有算法的阐述，并产生了一些新的高效算法。我们还研究了几种算法的计算复杂度。在本文中，我们考虑了关于完全阶$$\begin{gathered} minimize\sum\limits_{i = 1}^n {w_i } (y_i - x_i )^2 \hfill \\ subject tox_1 \leqslant x_2 \leqslant \cdot \cdot \cdot \leqslant x_n \hfill \\ \end{gathered} $$的等渗回归问题，其中每个阶都是严格正的，并且每个阶都是任意实数。我们证明了池相邻违反者算法（由于Ayer等人，1955;Miles, 1959; Kruskal, 1964）是一种对偶可行活动集方法，最小下集算法（由于Brunk等人，1957）是一种计算复杂度为O（n2）的原始可行活动集方法。提出了一种新的O(n)原始可行活动集算法。最后讨论了Van Eeden的方法，证明了它具有最坏情况指数时间复杂度。
In this and subsequent papers we 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. We also investigate the computational complexity of several algorithms.In this paper we consider the isotonic regression problem with respect to a complete order $$\begin{gathered} minimize\sum\limits_{i = 1}^n {w_i } (y_i - x_i )^2 \hfill \\ subject tox_1 \leqslant x_2 \leqslant \cdot \cdot \cdot \leqslant x_n \hfill \\ \end{gathered} $$ where eachwiis strictly positive and eachyiis an arbitrary real number. We show that the Pool Adjacent Violators algorithm (due to Ayer et al., 1955; Miles, 1959; Kruskal, 1964), is a dual feasible active set method and that the Minimum Lower Set algorithm (due to Brunk et al., 1957) is a primal feasible active set method of computational complexity O(n2). We present a new O(n) primal feasible active set algorithm. Finally we discuss Van Eeden's method and show that it is of worst-case exponential time complexity.