一种基于残差的随机Kaczmarz方法用于求解线性可行性问题

《Applied Mathematics Letters》：A residual-based randomized Kaczmarz method for solving linear feasibility problems

　　李宇涵|王泽|叶宇欣|尹俊峰中国上海同济大学上海智能自主系统研究所，邮编200092

摘要
本文提出了一种基于残差的随机Kaczmarz方法，通过依据残差的负值所定义的概率准则来动态选择活跃行索引，从而解决线性可行性问题。该文建立了所提方法的收敛性理论，并利用Hoffman引理得到了期望收敛速率的上界。通过数值实验进一步证明了该方法在迭代步数和计算时间方面的高效性。

引言
考虑求解如下线性不等式组Ax≤b，其中A∈Rm×n，b∈Rm，x∈Rn，这类问题在工程和科学计算中广泛存在，比如运营优化[1]、[2]，信号重建[3]、[4]、[5]，图像处理[6]、[7]以及机器学习[8]、[9]。

Kaczmarz方法[10]是一种经典且高效的用于求解相容线性方程的行作用法。其随机化版本已被证明，在按行范数的平方成比例随机选择行时，具有期望线性收敛速率[11]。此后又提出了许多随机Kaczmarz方法的变体并进行了研究，如贪婪随机Kaczmarz方法[12]、随机块Kaczmarz方法[13]以及替代超平面Kaczmarz方法[14]、[15]。

线性不等式组的松弛方法由Agmon[16]、Motzkin和Schoenberg[17]于1954年提出，该方法通过将当前迭代结果投影到选定的半空间中来寻找线性不等式组的解。它是POCS方法[18]和Kaczmarz方法[10]的一种特例。最近，提出了用于线性不等式组的随机迭代投影方法，并证明了其具有期望线性收敛速率[19]。该方法的随机块版本提高了大规模系统的计算效率[20]。还利用在随机选取的约束子集中违反最严重的约束，构建了随机采样松弛的Kaczmarz–Motzkin方法[21]。

为了进一步提高松弛随机Kaczmarz方法的计算效率，本文提出了一种基于残差的随机Kaczmarz方法，该方法动态运用概率准则。在可行区域非空的假设下，利用Hoffman引理从理论上证明了该方法的收敛性及其期望线性收敛速率。数值实验验证了该方法在迭代步数和所需时间方面的高效性。

本文结构如下：第2节构建了用于求解线性不等式组的基于残差的随机Kaczmarz方法；第3节证明了该方法的收敛性并确定了相应的收敛上界；第4节通过数值实验验证新方法的效率；最后第5节给出一些结论。

章节摘录
用于求解线性不等式组的基于残差的随机Kaczmarz方法
用aiT表示矩阵A∈Rm×n的第i行，bi和xi分别表示向量b∈Rm和x∈Rn的第i个分量。定义(xi)+=max(xi,0)为非负投影。用于求解线性不等式组的松弛随机Kaczmarz方法[19]的迭代公式为：xk+1=xk?aiTxk?bi+‖ai‖2/2ai，其中k=0,1,2,…，行索引i是以概率pi=‖ai‖2/2/‖A‖F2被选中的。从方程(2.1)可以看出，当约束条件满足aiTx≤bi时，更新步长为零。

收敛性分析
用S=x∈Rn∣Ax≤b表示(1.1)式的可行区域。在本文中，假设系数矩阵A没有零行且?S≠0?。用PS(x)表示x在S上的投影，PS(x)也是minz∈S‖x?z‖2的最优解。定义向量x到可行区域S的距离为d(x,S)=minz∈S‖x?z‖2=‖x?PS(x)‖2。对于系统Ax≤b而言，不可行性的距离为μ=infmax‖ΔA‖2,‖Δb‖:(A+ΔA)x≤b+Δb为不可行时的值。此时，Hoffman常数可由以下引理给出。

引理3.1

数值实验
使用随机高斯矩阵和Matrix Market中的矩阵，比较了用于求解线性不等式组的随机采样Kaczmarz-Motzkin方法(SKM)、松弛随机Kaczmarz方法(RK)以及基于残差的随机Kaczmarz方法(ReRK)的收敛性。由于这些方法的随机性，实验在相同参数下重复20次，记录每次的迭代次数(IT)和计算时间(CPU)的平均值。

所有数值实验结果均表明……

结论
本文引入了一种基于新概率准则的用于求解线性可行性问题的基于残差的随机Kaczmarz方法，该方法能够动态选择残差较大的违反约束进行迭代。建立了该方法的收敛定理，并给出了期望线性收敛速率。数值实验进一步证明了该方法的高效性。未来可以进一步探索块行索引选择策略和加速技术。

伦理审批
无需伦理审批。

符合伦理标准
本工作符合伦理标准。

利益冲突声明
作者声明不存在任何利益冲突。