线性收敛

线性收敛是数值优化和迭代算法中描述收敛速度的核心概念之一。它刻画了迭代序列在逼近极限值时误差衰减的速率，是衡量算法效率的重要指标。

从数学定义上看，设迭代序列 $\{x_k\}$ 收敛到极限点 $x^*$，若存在常数 $\mu \in (0,1)$ 和一个正整数 $K$，使得对所有 $k \geq K$ 都有 $\|x_{k+1} - x^*\| \leq \mu \|x_k - x^*\|$ 成立，则称该序列线性收敛到 $x^*$，常数 $\mu$ 称为收敛因子。该定义反映了一个直观的性质：每步迭代的误差大致按固定比例缩小。当 $\mu$ 接近 0 时收敛极快，接近 1 时收敛极慢。若 $\mu = 0.1$，每步误差缩小一个数量级；若 $\mu = 0.9$，则需多步才能看到明显缩减。在线性收敛的严格定义中，有时还细分为 Q-线性收敛和 R-线性收敛两种子类型，前者要求相邻两步误差的比值有确定上界，后者则只要求误差序列的根序列有上界，条件更弱。

在收敛速度的谱系中，线性收敛处于中间位置。比它慢的是次线性收敛，其误差衰减速度慢于任何指数衰减，典型的例子如一阶方法中步长取 $1/k$ 时的梯度下降，误差按 $O(1/k)$ 或 $O(1/\sqrt{k})$ 的量级衰减。比线性收敛快的是超线性收敛，其收敛因子 $\mu_k$ 本身趋于 0，即 $\lim_{k\to\infty} \|x_{k+1} - x^*\|/\|x_k - x^*\| = 0$，例如牛顿法在解附近的典型行为就是超线性甚至二次收敛。更进一步是二次收敛，每步误差大致平方衰减，即 $\|x_{k+1} - x^*\| \leq C\|x_k - x^*\|^2$。区分这些收敛阶具有重要的实践意义：在机器学习训练中，若算法只达到次线性收敛，可能需要极多的迭代才能达到高精度；若能达到线性或超线性收敛，则可大幅减少计算量。

线性收敛在优化算法中极为常见。经典梯度下降法在目标函数强凸且光滑的条件下，即满足强凸参数 $m > 0$ 和 Lipschitz 光滑参数 $L > 0$，其收敛因子为 $\mu = (L - m)/(L + m)$ 或 $\max\{|1 - \alpha m|, |1 - \alpha L|\}$，视步长选择而定。条件数 $\kappa = L/m$ 越大，$\mu$ 越接近 1，收敛越慢——这解释了为何预处理和自适应方法能显著加速收敛。共轭梯度法在精确线搜索下对二次凸问题理论上具有 $n$ 步以内的精确收敛性质，但在实际含入误差影响下则表现为线性收敛，且收敛因子与矩阵条件数的平方根 $\sqrt{\kappa}$ 有关，相比梯度法的 $\kappa$ 有显著改善。

加速技术可以大幅改进收敛速度。Nesterov 提出的加速梯度法在保持一阶信息的前提下，通过引入动量项将收敛速度从 $O((1-1/\kappa))$ 提升至 $O((1-1/\sqrt{\kappa}))$，在理论上达到了最优的一阶收敛速率下界。拟牛顿法如 BFGS、DFP 以及它们的有限内存变体 L-BFGS 在光滑强凸条件下同样线性收敛，且其收敛因子与问题的条件数相关性较弱，实践中往往比梯度法快得多。此外，非线性共轭梯度法（如 Fletcher-Reeves 和 Polak-Ribière 格式）在适当条件下也线性收敛，成为中等规模问题中无需存储 Hessian 矩阵的有效选择。

线性收敛的严格分析需要借助 Lyapunov 函数或势能函数技术。对于梯度下降法，常用的 Lyapunov 函数是目标函数值与最优值之差 $f(x_k) - f(x^*)$，通过梯度下降的不等式性质可推出该差值的收缩关系。而对于更一般的算子迭代格式，则需要通过不动点理论中的收缩映射原理来建立收敛性——若迭代映射 $T$ 是 $\mu$-收缩的，即对所有 $x,y$ 有 $\|T(x) - T(y)\| \leq \mu\|x - y\|$，则由 Banach 不动点定理可保证线性收敛到唯一不动点，这对理解分裂算法和 ADMM 等方法的收敛性至关重要。

在实际计算中，线性收敛的观测方法很简单：在半对数坐标系中绘制误差随迭代次数的变化曲线，若数据点近似落在一条直线上（即误差呈指数衰减），则说明算法达到了线性收敛。这条直线的斜率直接对应收敛因子 $\mu$ 的对数值。若曲线向下弯曲（加速衰减），则可能是超线性收敛；若向上弯曲（减速衰减），则可能是次线性收敛。对于实际应用而言，线性收敛性往往意味着算法的实用性——能在可接受的迭代次数内达到所需精度。

线性收敛在随机优化中也扮演着重要角色。当目标函数为有限个函数的平均时，随机梯度下降在最强的假设下也只能达到次线性收敛。但若采用方差缩减技术（如 SAG、SVRG、SARAH 等方法），则可恢复线性收敛速率，同时保持单次迭代的低计算成本。这些方法在机器学习领域已得到广泛使用。

约束优化和无约束优化中线性收敛的机制有所不同。在约束优化中，投影梯度法和罚函数法通常只能达到线性收敛，活跃集方法若能正确识别约束则可能实现超线性收敛。内点法在理论上可实现超线性甚至二次收敛，但实际计算中需注意病态条件带来的数值不稳定性，常需配合预条件技术才能有效发挥线性以上收敛速度的优势。

总的来说，线性收敛是优化算法分析和设计中最重要的概念之一。它不仅为算法的理论保证提供了可量化的标准，也为实践中的算法选择和参数调优提供了明确的方向。当需要高精度解时，应选择具有线性或更快收敛速率的算法；当只需要适度精度时，次线性收敛的算法可能因其较低的单步计算成本而更具优势。理解和准确判断算法的收敛阶，是有效解决各类优化问题的基本能力。