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

技術要約：線形最適化問題のための不正確な非実行可能アーク探索内点法

問題提起
本論文は、線形最適化問題（LOP）を解くための内点法（IPM）について論じている。具体的には、不実行な初期点から開始し、ニュートン系を不正確に（例：共役勾配法などの反復解法を用いて）解く手法である**不正確な非実行可能内点法（II-IPM）**に焦点を当てている。不正確なソルバーは大規模な問題に対する計算コストを削減できる一方で、既存の不正確な非実行可能ラインサーチ法には重大な欠点がある。それは、直線的な探索方向において、中心経路の近似による線形化誤差と、ソルバーによる不正確さの誤差が蓄積してしまうことである。この蓄積により、アルゴリズムは非常に小さなステップサイズを取らざるを得なくなり、その結果、最悪ケースの反復計算量は $O(n^2 L)$ （$n$ は変数の数、$L$ は入力データのバイナリ長）という比較的緩い境界に留まってしまう。

手法
著者らは、II-arc（不正確な非実行可能アーク探索内点法）と称される新しい手法を提案している。その核心となる革新は、標準的な直線探索を楕円アーク探索戦略に置き換えることにある。

1. アーク探索フレームワーク： 直線上を移動する代わりに、2次テイラー展開によって定義される楕円アークを用いて中心経路を近似する。次のイテレート $(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}$ は中心経路の1次および2次の導関数である。
2. 不正確な求解： 1次導関数 ($\dot{x}, \dot{y}, \dot{s}$) および2次導関数 ($\ddot{x}, \ddot{y}, \ddot{s}$) のニュートン系を不正確に解く。理論解析においては残差要件を緩和するために修正正規方程式系（MNES）の定式化を利用しているが、数値実験では、大規模問題におけるMNESの実装の数値的不安定性が観察されたため、ヤコビ前処理を用いた標準的な正規方程式系（NES）を用いている。
3. ステップサイズの選択： ステップサイズ $\alpha$ は、特定の近傍条件（イテレートが中心経路の特定の領域内に留まることを保証する）およびアルモリオ型の条件（双対ギャップの十分な減少を保証する）を満たすように選択される。
4. 理論的解析： 著者らは、アーク探索の曲線軌道が、直線よりも効果的に線形化誤差を抑制することを証明している。これにより、ニュートン系がかなりの不正確さで解かれている場合でも、ステップサイズを大きく保つことが可能になる。

主な貢献

• 初の不正確なアーク探索IPM： 著者らの知る限り、アーク探索の枠組みの中で不正確なIPMについて論じたのは本論文が初めてである。
• 改善された計算量境界： 本論文は、提案されたII-arc法に対して $O(n^{1.5} L)$ の多項式反復計算量境界を確立している。これは、既存の不正確な非実行可能ラインサーチ法の最良の既知の境界である $O(n^2 L)$ に対し、理論的に $n^{0.5}$ の係数分だけ改善されている。
• 誤差蓄積の軽減： 著者らは、アーク探索戦略が、既存の不正確な非実行可能手法における主要なボトルネックである線形化誤差と不正確さの誤差の蓄積を軽減することを実証している。

数値結果
著者らは、Preconditioned Conjugate Gradient (CG) を線形ソルバーとして用いたPython実装を使用し、NETLIBベンチマークコレクション（DFL001, QAP15, STOCFOR3, Kennington問題を含む）の大型問題を用いて数値実験を行った。

• 比較： 提案手法であるII-arc法（特にYangのヒューリスティック初期点を用いたバリアントである「II-arc-Yang」）を、既存の不正確な非実行可能ラインサーチ法（「II-line-Yang」）と比較した。
• パフォーマンス：
  • 反復回数： II-arc-Yangは、II-line-Yangよりも一貫して少ない反復回数を必要とした。テスト問題の約25%において、ラインサーチ法はアーク探索法よりも2倍以上の反復回数を必要とした。
  • 計算時間： II-arc-Yangは、75%の問題で総計算時間を短縮した。反復回数の減少が、2次導関数の系を解くための追加コストを相殺した。
  • 堅牢性： 本手法は18問中17問のテスト問題を正常に解き、数値的安定性を示した。
• 初期点： 定数初期点とYangのヒューリスティック初期点を比較したところ、ヒューリスティックなアプローチ（II-arc-Yang）が、反復回数と時間の両面において一般に優れたパフォーマンスを示すことが分かった。

意義と主張
本論文は、提案されたII-arc法が、既存の不正確な非実行可能ラインサーチ法よりも証明可能なほどタイトな最悪ケース反復境界を提供すると主張している。本研究の意義は、アーク探索（より優れた中心経路近似）の理論的利点と、大規模問題のための不正確なソルバーの現実的な必要性ととの間の溝を埋めることにある。

著者らは、計算量は改善されているものの、主な目的はフレームワークを提案しその収束を議論することであったと謙虚に述べている。また、以下の点によって数値的パフォーマンスがさらに向上する可能性があることを認めている：

• より高速な言語（C++、Juliaなど）での実装。
• より高度な不正確線形システムソルバーおよび前処理の研究。
• ネステロフの再起動戦略や実行可能IPMとの組み合わせの検討。

結論として、楕円アーク近似は不正確な状況下でも大きなステップサイズを許容し、それが大規模な線形最適化問題を解く上での理論的な反復計算量の削減と、実用的な性能向上の両方につながると述べている。