DATA PREORDERING IN GENERALIZED PAV ALGORITHM FOR MONOTONIC REGRESSION
DATA PREORDERING IN GENERALIZED PAV ALGORITHM FOR MONOTONIC REGRESSION作者机构：Department of Mathematics LinkSping University SE-58183 Link6ping Sweden
出 版 物：《Journal of Computational Mathematics》 (计算数学（英文）)
年 卷 期：2006年第24卷第6期
页 面：771-790页
核心收录：
学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070105[理学-运筹学与控制论] 0701[理学-数学]
主 题：Quadratic programming Large scale optimization Least distance problem,Monotonic regression Partially ordered data set Pool-adjacent-violators algorithm.
摘 要：Monotonic regression （MR） is a least distance problem with monotonicity constraints induced by a partiaily ordered data set of observations. In our recent publication [In Ser. Nonconvex Optimization and Its Applications, Springer-Verlag, （2006） 83, pp. 25-33], the Pool-Adjazent-Violators algorithm （PAV） was generalized from completely to partially ordered data sets （posets）. The new algorithm, called CPAV, 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 CPAV 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 CPAV 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.
维普期刊数据库