论文标题
一种动态编程方法，用于广义几乎等渗优化
A dynamic programming approach for generalized nearly isotonic optimization
论文作者
论文摘要
已广泛研究了形状限制的统计估计问题，并在信号处理，生物信息学和机器学习中进行了许多重要的实际应用。在本文中，我们提出和研究了一个广义的几乎等渗优化（GNIO）模型，该模型恢复了特殊情况，是形状约束统计回归中许多经典问题，例如等渗回归，几乎等渗回归和单峰回归问题。我们开发了一种有效且易于实现的动态编程算法，用于解决提出的模型，其递归性质经过仔细地发现和利用。对于特殊$ \ ell_2 $ -gnio问题，实现详细信息和最佳$ {\ cal o}（n）$运行时间分析我们的算法。数值实验，包括我们方法之间的比较，功能强大的商业求解器Gurobi以及解决$ \ ell_1 $ -gnio的现有快速算法和$ \ ell_2 $ -gnio问题，都在模拟和真实的数据集上表现出了我们提出的质量效率和强大的Algorith algorith algorith slage Algorith scormants gnio gnio的效率和强大性。
Shape restricted statistical estimation problems have been extensively studied, with many important practical applications in signal processing, bioinformatics, and machine learning. In this paper, we propose and study a generalized nearly isotonic optimization (GNIO) model, which recovers, as special cases, many classic problems in shape constrained statistical regression, such as isotonic regression, nearly isotonic regression and unimodal regression problems. We develop an efficient and easy-to-implement dynamic programming algorithm for solving the proposed model whose recursion nature is carefully uncovered and exploited. For special $\ell_2$-GNIO problems, implementation details and the optimal ${\cal O}(n)$ running time analysis of our algorithm are discussed. Numerical experiments, including the comparisons among our approach, the powerful commercial solver Gurobi, and existing fast algorithms for solving $\ell_1$-GNIO and $\ell_2$-GNIO problems, on both simulated and real data sets, are presented to demonstrate the high efficiency and robustness of our proposed algorithm in solving large scale GNIO problems.
