综述：线性规划的超长步仿射尺度算法

《Operations Research Perspectives》：A Very-Long-Step affine scaling for linear programming

　　

本文研究标准形式的线性规划（Linear Programming, LP）问题，其中可行集定义为 P = {x ∈ ?? | Ax = b, x ≥ 0}。假设矩阵 A 的维度为 m × n，且其行向量线性无关。针对此类线性规划问题，可采用多种求解方法，其中单纯形法最为著名。然而，本文采用仿射尺度算法（Affine Scaling Algorithm, AFS）——一种最简单的内点算法变体——来求解标准形式的线性规划问题。AFS 是一种改进迭代方法，其迭代点序列位于可行集 P 的内部，记 P′ = {x ∈ ?? | Ax = b, x > 0} 为 P 的内部，其元素称为内点。该算法的核心思想是：不直接在 P 上最小化目标函数，而是在由尺寸参数 β（0 < β < 1）控制的椭球上求解一系列优化问题。从内点 x? 出发，算法构造以 x? 为中心的内部椭球 S?，在该椭球上最小化目标函数得到最优点 x1，随后 x1 成为新内部椭球的中心。该过程不断重复，在特定假设下，点序列 {x?} 收敛于问题 (1.1) 的最优解。1967 年，Dikin [1] 首次提出 AFS，但直到 Karmarkar [2] 的类似工作出现后才受到关注。1986 年，Barnes [3] 与 Vanderbei、Meketon 和 Freedman [4] 在仿射尺度算法理论方面取得了重大进展，这些工作推动了仿射尺度变体及其收敛性分析的现代发展。关于这些方法及其收敛结果的更深入讨论，可参考 Wright [5]、Ye [6]、Bertsimas [7] 和 Vanderbei [8] 的著作。 多年来，众多研究人员对 AFS 方法的收敛性分析进行了深入研究。1974 年，Dikin 在非退化假设下分析了 AFS 的收敛性。Barnes [3] 和 Vanderbei 等人 [4] 在原始和对偶非退化假设下给出了更简洁的收敛性证明。Adler 等人 [9] 在无退化假设下研究了原始和对偶连续轨迹的收敛性。随后，Tsuchiya [10, 11] 证明了在步长 β ≤ 1/8 的条件下，对偶非退化假设对于长步长版本 AFS 的全局收敛并非必要。他还引入了势函数（potential function）的概念，用于研究 AFS 在可行域边界附近的局部行为。Dikin [12] 和 Tsuchiya 等人 [13] 利用势函数思想，在 β < 1/2 和 β ≤ 2/3 的条件下证明了退化线性规划问题的全局收敛性。最后，Hall 等人 [14] 指出，当步长 β > 2/3 时，对偶估计序列的收敛性无法得到保证。 AFS 的全局收敛性分析和混沌分析是吸引众多研究人员关注的重要课题。Monteiro 等人 [15] 和 Saigal [16] 针对退化线性规划问题提出了两种长步长 AFS 算法的简洁证明。在 Saigal [17] 的后续工作中，引入了两种基于预测-校正（predictor-corrector）的方法，加速了 AFS 的收敛。随后，Castillo 等人 [18] 首次讨论了 AFS 的混沌分析。此后，Bruin 等人 [19] 讨论了当 β 接近 2/3 时 AFS 算法的混沌行为，这与其他研究人员分析的其它内点方法的混沌行为一致。近期，Md Sarowar 等人 [20] 将 Nesterov 的重启策略 [21-25] 与 AFS 方法相结合，提供了 AFS 改进的收敛速率推广。他们还提出了第二种算法——加速仿射尺度算法（Accelerated AFS, AAFS），通过引入非线性 Shank 级数变换技术进一步展示了改进效果。 本文研究一种带保护机制的超长步仿射尺度框架。需要强调的是，使用激进的仿射尺度步长本身并非新思想。类似的边界步长分数选择在早期的仿射尺度研究中 [4] 以及标准线性规划教材 [26] 中已有出现。因此，本文的主要贡献并非仅仅使用在当前归一化下满足 β? > 1 的步长，而在于将激进的仿射尺度步长与两种显式保护机制相结合：一个上界 β_max 以及周期性间隔迭代（spacer iterations），满足 β? ∈ (0, 1)。

1. 引言

本文考虑标准形式的线性规划（Linear Programming, LP）问题，其可行集定义为 P = {x ∈ ?? | Ax = b, x ≥ 0}。假设矩阵 A 的维度为 m × n，且行向量线性无关。求解此类问题的方法众多，其中单纯形法最为著名。本文采用仿射尺度算法（Affine Scaling Algorithm, AFS）——一种最简单的内点算法变体——来求解标准形式线性规划问题。AFS 是一种改进迭代方法，其迭代点序列位于可行集 P 的内部。该算法的核心思想是：不直接在 P 上最小化目标函数，而是在由尺寸参数 β（0 < β < 1）控制的内部椭球上求解一系列优化问题。从内点 x? 出发，算法构造以 x? 为中心的内部椭球 S?，在该椭球上最小化目标函数得到最优点 x1，随后 x1 成为新内部椭球的中心。该过程不断重复，在特定假设下，点序列 {x?} 收敛于问题的最优解。

1967 年，Dikin 首次提出 AFS，但直到 Karmarkar 的类似工作出现后才受到关注。1986 年，Barnes 与 Vanderbei、Meketon 和 Freedman 在仿射尺度算法理论方面取得了重大进展，推动了仿射尺度变体及其收敛性分析的现代发展。关于这些方法及其收敛结果的更深入讨论，可参考 Wright、Ye、Bertsimas 和 Vanderbei 的著作。

多年来，众多研究人员对 AFS 方法的收敛性分析进行了深入研究。1974 年，Dikin 在非退化假设下分析了 AFS 的收敛性。Barnes 和 Vanderbei 等人在原始和对偶非退化假设下给出了更简洁的收敛性证明。Adler 等人在无退化假设下研究了原始和对偶连续轨迹的收敛性。随后，Tsuchiya 证明了在步长 β ≤ 1/8 的条件下，对偶非退化假设对于长步长版本 AFS 的全局收敛并非必要。他还引入了势函数（potential function）的概念，用于研究 AFS 在可行域边界附近的局部行为。Dikin 和 Tsuchiya 等人利用势函数思想，在 β < 1/2 和 β ≤ 2/3 的条件下证明了退化线性规划问题的全局收敛性。最后，Hall 等人指出，当步长 β > 2/3 时，对偶估计序列的收敛性无法得到保证。

AFS 的全局收敛性分析和混沌分析是吸引众多研究人员关注的重要课题。Monteiro 等人和 Saigal 针对退化线性规划问题提出了两种长步长 AFS 算法的简洁证明。在 Saigal 的后续工作中，引入了两种基于预测-校正（predictor-corrector）的方法，加速了 AFS 的收敛。随后，Castillo 等人首次讨论了 AFS 的混沌分析。此后，Bruin 等人讨论了当 β 接近 2/3 时 AFS 算法的混沌行为，这与其他研究人员分析的其它内点方法的混沌行为一致。近期，Md Sarowar 等人将 Nesterov 的重启策略与 AFS 方法相结合，提供了 AFS 改进的收敛速率推广。他们还提出了第二种算法——加速仿射尺度算法（Accelerated AFS, AAFS），通过引入非线性 Shank 级数变换技术进一步展示了改进效果。

本文研究一种带保护机制的超长步仿射尺度框架。需要强调的是，使用激进的仿射尺度步长本身并非新思想。类似的边界步长分数选择在早期的仿射尺度研究中以及标准线性规划教材中已有出现。因此，本文的主要贡献并非仅仅使用在当前归一化下满足 β? > 1 的步长，而在于将激进的仿射尺度步长与两种显式保护机制相结合：一个上界 β_max 以及周期性间隔迭代（spacer iterations），满足 β? ∈ (0, 1)。

2. 超长步仿射尺度算法框架

本节介绍超长步仿射尺度算法的具体框架。该算法在传统仿射尺度算法的基础上，通过放宽内部椭球约束以允许更长的步长。具体而言，算法在每次迭代中允许步长参数 β? 超过传统意义上的安全界限，同时通过上界 β_max 和周期性间隔迭代两种保护机制确保算法的全局收敛性。间隔迭代采用满足 β? ∈ (0, 1) 的标准仿射尺度步长，周期性插入到激进步长之间，以防止迭代点序列偏离最优解方向。

3. 全局收敛性分析

在标准假设条件下，本节证明了超长步仿射尺度算法的全局收敛性。通过构造适当的势函数并利用间隔迭代的性质，研究人员证明了无论激进步长如何选择，只要满足上界约束 β_max 且间隔迭代周期性出现，算法产生的迭代点序列都将收敛于线性规划问题的最优解。该收敛性证明不依赖于原始或对偶非退化假设，拓展了已有仿射尺度算法的收敛性理论。

4. 数值实验

在基准测试问题上，超长步仿射尺度算法相比传统仿射尺度算法（AS）、长步长算法（LS1）和（LS2）表现出更少的迭代次数。实验结果表明，该算法能够高效地将对偶间隙（duality gap）降低至约 1e-4 的精度，并且具有良好的可扩展性，适用于较大规模的线性规划问题。