Immunity to Increasing Condition Numbers of Linear Superiorization versus Linear Programming

技術要約：線形計画法に対する線形・スペリアリゼーションの条件数の増大に対する免疫性

問題提起
本論文は、条件数が増大する線形計画問題に適用された際、線形計画法（LP）アルゴリズムと線形・スペリアリゼーション（LinSup）手法の比較性能について論じている。古典的なLPが最適点（制約条件下での目的関数の最小化）を見出すことを目的とするのに対し、LinSupは「優れた（最小ではないが低減された）目的関数値」を持つ実行可能点を見出すことを目的とする。本研究で調査されている中心的な問題は、不適切性（ill-posedness）に対する両アプローチの感度、具体的には、制約行列の条件数の増大が各アルゴリズムの実行時間、実行可能性の達成、および目的関数の減少にどのように影響するかである。

手法
著者らは、確立されたLPソルバーに対してLinSupを比較検討するために、制御された実験研究を実施した。

• 問題生成: 研究者らは、$\min \langle c, x \rangle$ subject to $Ax \le b$ and $\ell \le x \le u$ という形式の線形計画問題を構築した。異なる条件数間での構造的類似性を確保するため、特異値分解（SVD）を利用した。ランダムな半直交行列 $U$ および $V$ を生成し、特定の条件数 $\kappa$（良好な条件から極めて不良な条件まで）を実現するように、特異値が分布した対角行列 $\Sigma_\kappa$ を構築した。行列サイズは $80 \times 100$ から $4000 \times 5000$ までとした。
• テストされたアルゴリズム:
  • LinSup: 基底となる実行可能性を探索するアルゴリズムとして、Agmon-Motzkin-Schönberg (AMS) 投影法を用いて実装された。目的関数の正規化負勾配を用いて摂動が導入された。このアルゴリズムは、有界な摂動、および特定のステップサイズ・スケジュールと再起動メカニズムを備えた巡回投影を採用している。
  • LPソルバー: LinSupを scipy.simplex、scipy.revised simplex、scipy.interior-point、および gurobi.primal simplex と比較した。
• 実験プロトコル: 公平な比較を期すため、著者らは統一された停止基準（固定された不実行閾値 $\varepsilon = 10^{-8}$）を課した。
  • LinSupは、この閾値に達するまで実行された。
  • LPソルバーも同様の閾値の下で実行された。もしLPソルバーが時間 $T_{sup}$（LinSupが終了するまでの時間）以内に閾値に達しなかった場合、その時点での反復回数で停止させ、その時点のイテレートを記録した。
  • 記録された指標には、実行時間、目的関数値、および終了時および反復中における最大制約違反（不実行性）が含まれる。

主な貢献と結果
本研究は、さまざまな問題の難易度に対して、古典的なLPソルバーと比較したLinSupの堅牢性に関する経験的な証拠を提供している。

1. 次元の増加に伴うパフォーマンス（固定 $\kappa$）:

   • 小規模な次元では、シンプレックス法ベースのソルバーの方が高速であった。
   • 問題の次元が増大するにつれ（$4000 \times 5000$ まで）、シンプレックス実装（Gurobiを含む）の実行時間は著しく増加した。高次元においては、LinSupはシンプレックス・アルゴリズムよりも速く終了した。
   • 特に、テストされた最大規模の次元において、LinSupはシンプレックス・アルゴリズムが実行可能性を達成する前に、実行可能性の閾値に到達した。

2. 条件数の増大に対する免疫性（固定次元）:

   • シンプレックス法: 条件数が増大するにつれ、scipy のシンプレックス実装は深刻な劣化を示した。これらはしばしば、劣った目的関数値を持つ状態で早期に終了し、問題の困難さゆえに実質的に「降参」した。
   • 内点法: この手法は、低い目的関数値を迅速に見つけるようには見えたが、高い条件数において、必要なレベルの実行可能性を達成することに苦慮し、高い不実行性（最大 $10^1$ まで）をもたらした。
   • LinSup: スペリアリゼーション手法は、顕著な安定性を示した。その実行時間は条件数に関わらず比較的一定であり、テストされたすべての条件数において、目標とする実行可能レベル（$\varepsilon = 10^{-8}$）を一貫して達成した。
   • 目的関数: 条件が悪いシナリオにおいて、LinSupは終了時点において、シンプレックス法よりも一貫して優れた（より低い）目的関数値を生成した。

3. 近接度・ターゲット分析:

   • 不実行性と目的関数値のプロット（近接度・ターゲット曲線）は、LinSupが目的関数を減少させつつ、実行可能性に向かって着実な経路を維持していることを裏付けた。対照的に、内点法は、不適切な設定において、低い目的関数値を見つけることと制約を満たすことの間の断絶を示した。

意義と主張
本論文は、線形計画問題、特に大規模なシナリオにおいて、古典的なLPソルバーに対して線形・スペリアリゼーションが明確な優位性を持つことを主張している。

• 堅牢性: 著者らは、LinSupがテストされたLPソルバーよりも高い条件数の影響を受けにくいと結論付けている。これはアルゴリズムの性質に起因すると考えている。すなわち、LinSupはシステム全体を同時に解くのではなく、半空間への個別の投影を行うことであり、「有界な摂動への耐性」を持つ基底アルゴリズムが、条件数の悪化によって増幅されかねない計算誤差を吸収するのに役立っている。
• 実用的有用性: 本研究は、実行可能な点かつ低減された目的関数値を見つけることが十分である場合（厳密な最適化ではなく「満足」を目指すアプローチ）、LinSupが不適切な問題に対してより信頼性の高い効率的なツールであることを示唆している。
• 限定的な範囲: 著者らは、観察された結果が特定の実験設定と問題サイズに基づいていることを明示している。彼らは、観察された傾向がより大きなインスタンスでも保持されると確信しているが、LinSupがすべての最適化タスクにおいてLPソルバーに取って代わるものであるとは主張していない。また、LinSupはLPソルバーではなく、制約付き最適性を目指すものではなく、あくまで「優れた」実行可能点を目指すものであることも注記している。
• 今後の課題: 論文は、線形設定におけるLinSupの観察された堅牢性が、非線形設定（特に内点法が条件数の悪化に苦戦することが知られている強度変調放射線治療など）においても調査される価値があることを示唆している。