论文标题
重球动量引起的采样kaczmarz motzkin方法线性可行性问题
Heavy Ball Momentum Induced Sampling Kaczmarz Motzkin Methods for Linear Feasibility Problems
论文作者
论文摘要
最近提出的采样Kaczmarz Motzkin（SKM）算法与解决大规模线性可行性（LF）问题的最先进方法相比表现良好。为了在解决LF问题的背景下探索动量的概念，在这项工作中，我们提出了一种动量诱导的算法，称为动量采样Kaczmarz Motzkin（MSKM）。 MSKM算法是通过将重球动量集成到SKM算法中来开发的。我们对所提出的MSKM算法提供了严格的融合分析，从中我们获得了几种用于解决LF问题的Kaczmarz类型方法的收敛结果。此外，在有些弱的条件下，我们为MSKM算法产生的序列的所谓塞萨罗平均值建立了亚线性收敛速率。然后，我们通过对人工和真实数据集进行彻底的数值实验来备份理论结果。为了进行公平的比较，我们在多种测试实例上与SKM方法相比，我们测试了我们提出的方法：1）随机生成的实例，2）Netlib LPS和3）线性分类测试实例。我们还将所提出的方法与Netlib LPS上的传统内部方法（IPM）和活动集方法（ASM）进行了比较。所提出的动量诱导的算法在所有考虑的测试实例上显着胜过基本SKM方法（无动量）。此外，与IPM和ASM算法相比，所提出的算法也表现良好。最后，我们提出了一种随机版本的MSKM算法，称为AntoChastic-Momentum采样Kaczmarz Motzkin（SSKM），以更好地处理大型现实世界数据。我们通过对拟议SSKM算法进行严格的理论收敛分析来结束工作。
The recently proposed Sampling Kaczmarz Motzkin (SKM) algorithm performs well in comparison with the state-of-the-art methods in solving large-scale Linear Feasibility (LF) problems. To explore the concept of momentum in the context of solving LF problems, in this work, we propose a momentum induced algorithm called Momentum Sampling Kaczmarz Motzkin (MSKM). The MSKM algorithm is developed by integrating the heavy ball momentum to the SKM algorithm. We provide a rigorous convergence analysis of the proposed MSKM algorithm from which we obtain convergence results of several Kaczmarz type methods for solving LF problems. Moreover, under somewhat weaker conditions, we establish a sub-linear convergence rate for the so-called Cesaro average of the sequence generated by the MSKM algorithm. We then back up the theoretical results via thorough numerical experiments on artificial and real datasets. For a fair comparison, we test our proposed method in comparison with the SKM method on a wide variety of test instances: 1) randomly generated instances, 2) Netlib LPs and 3) linear classification test instances. We also compare the proposed method with the traditional Interior Point Method (IPM) and Active Set Method (ASM) on Netlib LPs. The proposed momentum induced algorithm significantly outperforms the basic SKM method (with no momentum) on all of the considered test instances. Furthermore, the proposed algorithm also performs well in comparison with IPM and ASM algorithms. Finally, we propose a stochastic version of the MSKM algorithm called Stochastic-Momentum Sampling Kaczmarz Motzkin (SSKM) to better handle large-scale real-world data. We conclude our work with a rigorous theoretical convergence analysis of the proposed SSKM algorithm.
