An inexact infeasible arc-search interior-point method for linear optimization problems

技术摘要：一种用于线性优化问题的非精确非可行弧搜索内点法

问题陈述
本文研究了使用内点法（IPM）求解线性优化问题（LOP）的问题。具体而言，本文关注的是非精确非可行内点法（II-IPMs），这类方法旨在从非可行初始点开始求解 LOP，并对牛顿系统进行非精确求解（例如，通过共轭梯度法等迭代求解器）。虽然非精确求解器可以降低大规模问题每次迭代的计算成本，但现有的非精确非可行直线搜索方法存在一个显著缺陷：沿直线搜索方向会累积线性化误差（来自对中心路径的近似）和非精确性误差（来自求解器）。这种误差的累积迫使算法只能采取非常小的步长，导致其最坏情况下的迭代复杂度界限相对较松，为 $O(n^2 L)$，其中 $n$ 是变量数量，$L$ 是输入数据的二进制长度。

方法论
作者提出了一种被称为 II-arc（非精确非可行弧搜索内点法）的新方法。其核心创新在于使用椭圆弧搜索策略取代了标准的直线搜索。

1. 弧搜索框架： 该方法不再沿直线移动，而是利用二阶泰勒展开定义的椭圆弧来近似中心路径。下一个迭代点 $(x_{k+1}, y_{k+1}, s_{k+1})$ 计算如下：
   $$x(\alpha) = x_k - \dot{x} \sin(\alpha) + \ddot{x}(1 - \cos(\alpha))$$
   （对于 $y$ 和 $s$ 亦然），其中 $\dot{x}, \ddot{x}$ 分别是中心路径的一阶导数和二阶导数。
2. 非精确求解： 该方法对一阶导数（$\dot{x}, \dot{y}, \dot{s}$）和二阶导数（$\ddot{x}, \ddot{y}, \ddot{s}$）的牛顿系统进行非精确求解。作者在理论分析中利用了修正正规方程系统（MNES）表述来放宽残差要求，但在数值实验中，由于在处理大规模问题时观察到 MNES 实现存在数值不稳定性，因此采用了带有 Jacobi 预处理器的标准正规方程系统（NES）。
3. 步长选择： 步长 $\alpha$ 的选择需满足特定的邻域条件（确保迭代点保持在中心路径的特定区域内）以及类 Armijo 条件（以确保对偶间隙有足够的下降）。
4. 理论分析： 作者证明了弧搜索的曲线轨迹比直线能更有效地抑制线性化误差。这使得即使在牛顿系统求解具有显著非精确性的情况下，步长仍能保持较大。

主要贡献

• 首个非精确弧搜索 IPM： 据作者所知，这是第一篇在弧搜索框架下讨论非精确 IPM 的论文。
• 改进的复杂度界限： 本文为所提出的 II-arc 方法建立了 $O(n^{1.5} L)$ 的多项式迭代复杂度界限。这在理论上比现有非精确非可行直线搜索方法（$O(n^2 L)$）提升了 $n^{0.5}$ 倍。
• 缓解误差累积： 作者证明了弧搜索策略能够减轻线性化误差和非精确性误差的累积，而这正是现有非精确非可行方法的主要瓶颈。

数值结果
作者使用 Python 实现，并采用预处理共轭梯度法（CG）作为线性求解器，在 NETLIB 基准测试集（包括 DFL001、QAP15、STOCFOR3 和 Kennington 问题）的大规模问题上进行了数值实验。

• 对比： 将提出的 II-arc 方法（特别是使用 Yang 启发式初始点的变体“II-arc-Yang”）与现有的非精确非可行直线搜索方法（“II-line-Yang”）进行了对比。
• 性能：
  • 迭代次数： II-arc-Yang 所需的迭代次数始终少于 II-line-Yang。对于近 25% 的测试问题，直线搜索方法的迭代次数是弧搜索方法的两倍或更多。
  • 计算时间： II-arc-Yang 在 75% 的问题中减少了总计算时间。迭代次数的减少补偿了求解二阶导数系统的额外开销。
  • 鲁棒性： 该方法成功解决了 18 个测试问题中的 17 个，展示了数值稳定性。
• 初始点： 研究还将常数初始点与 Yang 的启发式初始点进行了比较，发现启发式方法（II-arc-Yang）在迭代次数和时间方面通常表现更好。

意义与主张
论文声称，所提出的 II-arc 方法提供了比现有非精确非可行直线搜索方法更紧的证明性最坏情况迭代界限。这项工作的意义在于弥合了弧搜索（更好的中心路径近似）的理论优势与大规模问题中必须使用非精确求解器的实际需求之间的差距。

作者谦虚地指出，虽然理论复杂度得到了提升，但主要目标是提出该框架并讨论其收敛性。他们承认，可以通过以下方式进一步提高数值性能：

• 在更快的语言（如 C++、Julia）中实现该方法。
• 研究更先进的非精确线性系统求解器和预处理器。
• 探索与 Nesterov 重启策略或可行内点法的结合。

论文得出结论，椭圆弧近似允许在存在非精确性的情况下采取更大的步长，从而在理论上降低了迭代复杂度，并在实践中提高了求解大规模线性优化问题的效率。