Volume 24, Issue 6
Data Preordering in Generalized Pav Algorithm for Monotonic Regression

Oleg Burdakov, Anders Grimvall & Oleg Sysoev

DOI:

J. Comp. Math., 24 (2006), pp. 771-790

Published online: 2006-12

Preview Full PDF 155 1684
Export citation
  • Abstract

Monotonic regression (MR) is a least distance problem with monotonicity constraints induced by a partially ordered data set of observations. In our recent publication [In Ser. {\sl Nonconvex Optimization and Its Applications}, Springer-Verlag, (2006) {\bf 83}, pp. 25-33], the Pool-Adjacent-Violators algorithm (PAV) was generalized from completely to partially ordered data sets (posets). The new algorithm, called GPAV, is characterized by the very low computational complexity, which is of second order in the number of observations. It treats the observations in a consecutive order, and it can follow any arbitrarily chosen topological order of the poset of observations. The GPAV algorithm produces a sufficiently accurate solution to the MR problem, but the accuracy depends on the chosen topological order. Here we prove that there exists a topological order for which the resulted GPAV solution is optimal. Furthermore, we present results of extensive numerical experiments, from which we draw conclusions about the most and the least preferable topological orders.

  • Keywords

Quadratic programming Large scale optimization Least distance problem Monotonic regression Partially ordered data set Pool-adjacent-violators algorithm

  • AMS Subject Headings

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{JCM-24-771, author = {}, title = {Data Preordering in Generalized Pav Algorithm for Monotonic Regression}, journal = {Journal of Computational Mathematics}, year = {2006}, volume = {24}, number = {6}, pages = {771--790}, abstract = { Monotonic regression (MR) is a least distance problem with monotonicity constraints induced by a partially ordered data set of observations. In our recent publication [In Ser. {\sl Nonconvex Optimization and Its Applications}, Springer-Verlag, (2006) {\bf 83}, pp. 25-33], the Pool-Adjacent-Violators algorithm (PAV) was generalized from completely to partially ordered data sets (posets). The new algorithm, called GPAV, is characterized by the very low computational complexity, which is of second order in the number of observations. It treats the observations in a consecutive order, and it can follow any arbitrarily chosen topological order of the poset of observations. The GPAV algorithm produces a sufficiently accurate solution to the MR problem, but the accuracy depends on the chosen topological order. Here we prove that there exists a topological order for which the resulted GPAV solution is optimal. Furthermore, we present results of extensive numerical experiments, from which we draw conclusions about the most and the least preferable topological orders. }, issn = {1991-7139}, doi = {https://doi.org/}, url = {http://global-sci.org/intro/article_detail/jcm/8790.html} }
TY - JOUR T1 - Data Preordering in Generalized Pav Algorithm for Monotonic Regression JO - Journal of Computational Mathematics VL - 6 SP - 771 EP - 790 PY - 2006 DA - 2006/12 SN - 24 DO - http://doi.org/ UR - https://global-sci.org/intro/article_detail/jcm/8790.html KW - Quadratic programming KW - Large scale optimization KW - Least distance problem KW - Monotonic regression KW - Partially ordered data set KW - Pool-adjacent-violators algorithm AB - Monotonic regression (MR) is a least distance problem with monotonicity constraints induced by a partially ordered data set of observations. In our recent publication [In Ser. {\sl Nonconvex Optimization and Its Applications}, Springer-Verlag, (2006) {\bf 83}, pp. 25-33], the Pool-Adjacent-Violators algorithm (PAV) was generalized from completely to partially ordered data sets (posets). The new algorithm, called GPAV, is characterized by the very low computational complexity, which is of second order in the number of observations. It treats the observations in a consecutive order, and it can follow any arbitrarily chosen topological order of the poset of observations. The GPAV algorithm produces a sufficiently accurate solution to the MR problem, but the accuracy depends on the chosen topological order. Here we prove that there exists a topological order for which the resulted GPAV solution is optimal. Furthermore, we present results of extensive numerical experiments, from which we draw conclusions about the most and the least preferable topological orders.
Oleg Burdakov, Anders Grimvall & Oleg Sysoev. (1970). Data Preordering in Generalized Pav Algorithm for Monotonic Regression. Journal of Computational Mathematics. 24 (6). 771-790. doi:
Copy to clipboard
The citation has been copied to your clipboard