Non-Negative Conjugate Gradients

技術要約：非負共役勾配法（Non-Negative Conjugate Gradients）

問題設定
本論文は、厳密に凸な非負二次計画問題（NNQP）を扱う：
$$\min_{x \in \mathbb{R}^n} f(x) = \frac{1}{2}x^\top A x - b^\top x \quad \text{subject to} \quad x \ge 0,$$
ここで、$A$は対称正定値（SPD）行列である。著者らはまた、線形制約 $Bx = c$ を伴う等式拡張型についても検討している。共役勾配法（CG）は、制約のないSPD系 $Ax=b$に対する標準的なソルバーであるが、非負制約$x \ge 0$ を本質的に遵守するものではない。既存の実行可能点法（例：射影勾配法、MPRGP）は、しばしば収束速度が遅くなる（$O(\kappa)$）か、あるいは外部の拡張ラグランジュ・ループを導入することなく一般的な等式制約を扱うことに苦慮する。本研究の目的は、CGの $O(\sqrt{\kappa})$ の収束率や行列フリー（matrix-free）の能力を犠牲にすることなく、この問題を解くことである。

手法
提案手法である**非負共役勾配法（NNCG）**は、CGソルバーを原始・双対活性集合（primal-dual active-set）の外側ループ内に包摂するものである。コアとなる戦略は以下の通りである：

1. 活性集合の縮小（Active-Set Reduction）: アルゴリズムは、$x_i > 0$ となるインデックスの「自由集合（free set）」$F$ を保持する。この集合上では、境界制約は不活性となり、問題は非制約のSPD系 $A_F x_F = b_F$ （または等式拡張ケースにおける鞍点系）へと簡略化される。
2. 行列フリーの内側解法（Matrix-Free Inner Solve）: 内側の系はCGを用いて解かれる。極めて重要な点は、本手法が行列フリーであることである。もし $A = M^\top M$ であれば、演算子 $v \mapsto A_F v$ は $M_F^\top (M_F v)$ として計算され、$M$ との2回の行列ベクトル積のみを必要とし、$A$ の $O(n^2)$ のストレージを回避できる。
3. 原始・双対の切り替え（Primal-Dual Toggling）:
   • 原始ステップ: 自由変数 $x_i$ が負になった場合、そのインデックスは $F$ から除外される（$x_i = 0$ とされる）。
   • 双対ステップ: 境界変数 $x_i = 0$ であり、かつ減少勾配 $s_i = (Ax)_i - b_i$ が負である場合、そのインデックスは $F$ に採用される。
   • これらの切り替えは、線形相補性問題（LCP）$(A, -b)$ における主ピボット操作に対応している。
4. 終了戦略: 縮退（degeneracy）条件下でも有限終了を保証するために、本手法はブロック主ピボット（block-principal-pivoting）パス（高速なバッチ交換）を採用し、それを最小インデックス・ブランド・フォールバック（least-index Bland fallback）（単一インデックス交換）によってガードしている。J´udiceおよびPires [21]、ならびにMurty [25] に基づくこの構成は、一意なグローバル最適解への収束を保証する。
5. 不正確性の取り扱い: 主要な理論的貢献は、CGの内側残差が「決定マージン（decision margin）」（正確な軌跡において遭遇する最小の非ゼロの原始または双対の値）に対して十分に小さい場合、不正確なループが正確なループと同一の符号決定を行うことを証明した点にある。これにより、有限終了の保証が、行列フリーかつ不正確なレジームへと転移される。
6. 正則化と前処理: 条件数 $\kappa$ を圧縮し、元の $A$ がランク不足であっても $A_\alpha$ がP行列（主部分行列が厳密に正定値であること）であり続けるように、リッジ/ティコノフ分割 $A_\alpha = (1-\alpha)A + \alpha R^\top R$ が使用される。内側のCG解法を加速するために、前処理（例：Jacobi、Nyström）が適用される。

主な貢献

• 不正確な解に対する有限終了の保証: 本論文は、ブロック主ピボット（以前は正確な解に対してのみ有効であった）の有限終了保証を、不正確な行列フリーCGレジームへと拡張した。補題4.1は、内側の残差が決定マージンに結びついたとき、近似ループが正確な自由集合の軌跡を辿ることを示している。
• 等式制約の直接的な取り扱い: 一般的な等式 $Bx=c$ に対して外部の拡張ラグランジュ・ループを必要とする実行可能点法とは異なり、本手法はシューア補行列を用いて乗数を解析的に消去し、等式拡張問題を活性集合の枠組み内で直接解く。
• 行列フリーの効率性: ソルバーは $A$ を組み立てることなく動作し、$O(n)$ のワーキングメモリと、各外側ステップあたり $O(\sqrt{\kappa})$ の内側イテレーションのみを必要とする。
• ウォームスタート（Warm-Starting）: 本手法はパラメトリックなファミリー（例：効率的フロンティア）間でのウォームスタートをサポートしており、前ステップの自由集合と解を初期推測値として用いることで、サポートが安定している場合の外部イテレーションを劇的に削減できる。

結果

• 合成性能: 植え付けられた最適解を持つ合成SPD問題において、アルゴリズムは最大6回の外側ステップで最適解に到達した。総CG内側イテレーション数は条件数 $\kappa$ に対して劣線形に増加し（対数対数グラフで傾き $\approx 0.35$）、$O(\sqrt{\kappa})$ の挙動を確認した。
• 縮退とサイクリング: ガードなしのバッチピボットにおいてサイクリングを引き起こすように設計された敵対的なアンチ相関デザインのファミリーにおいて、提案されたフォールバックメカニズムはループの終了に成功したが、ガードなしのパスはサイクリングした。
• ランク不足: ランク不足のレジーム（$m < n$）では、未正則化のソルバーは収束しないか、最適性を証明できない。小さな正則化パラメータ $\alpha > 0$ を導入することで、P行列の性質が回復し、収束とKKT証明が保証される。
• ベースラインとの比較:
  • vs. 射影勾配法: NNCGは、不良設定の問題において射影勾配法よりも $\sqrt{\kappa}$ 倍優れた性能を示す。
  • vs. Lawson-Hanson および 内部点法: 組み立て済みの高密度問題において、NNCG（直接内側解を使用）は、ブロックピボットが単桁の外部ステップで最適なサポートに到達するため、Lawson-Hansonよりも大幅に高速である（例：$n=2000$ においてLawson-Hansonより48倍高速）。
  • 大規模スケールでの高密度ソルバーとの比較: 行列フリーのデブラーリング適用（$n=65,536$）において、高密度ソルバー（Lawson-Hanson, Clarabel）はメモリ制約（$O(n^2)$ ストレージ）により失敗する。NNCGは $O(n)$ メモリと数秒でこれを解決するが、高密度ソルバーは演算子をインスタンス化することすらできない。
• 実世界への応用: ハイパースペクトルアンミキシング問題（Cupriteシーン、$n=498$ のシグネチャ）において、本手法はウォームスタートを通じてコールドスタートの実行に対して672倍の高速化を達成し、かつ正確なKKT証明（単一鉱物のサポートの特定）を提供した。これに対し、実行可能点法は閾値処理を必要とする近似解を返す。

意義と主張
本論文は、NNCGが、縮退や不正確な内側解が存在する場合でも、非負二次計画問題に対して無条件の有限終了保証を提供することを主張している。これは、クリロフ部分空間法（CG）の効率性と、活性集合法の組合せ最適化の保証との間の溝を埋めるものである。

著者らは、本手法がアプリケーションに依存しないことを強調している。すなわち、境界制約と一般的な線形等式を、外部ループを必要とせずに直接扱うことができる。本手法は非負直交錐（non-negative orthant）のみを扱う（一般的なボックス制約は対象外）が、実行可能点法（MPRGPなど）と比較して、正確なKKT証明を提供し、等式制約をネイティブに扱うという明確な利点を持つ。本研究は、「決定対決定（decision-for-decision）」の転移が、正確な解から不正確な解へと可能であることを確立し、主ピボット法の堅牢性と、行列フリー・クリロフソルバーの拡張性を組み合わせることを可能にした。