Path Following in the Exact Penalty Method of Convex Programming

技術要約：凸計画問題における厳密ペナルティ法のパス・フォローイング

問題提起
本論文は、制約付き凸最適化問題、具体的にはアフィン等式制約および凸不等式制約の下での凸目的関数の最小化という課題に取り組んでいる。古典的なペナルティ法は、ペナルティ項（通常は二次形式）を無限に増大させることで、これらを一連の無制約問題へと変換するものであるが、制約を満たす解を得るためには $\rho \to \infty$ とする必要があり、これがしばしば悪条件（ill-conditioning）を引き起こす。**厳密ペナルティ法（Exact Penalty Method）**は、二乗ペナルティの代わりに絶対値ペナルティ（不等式には $L_1$ ノルム、等式にも同様の形式を使用）を用いる代替案を提示しており、理論的には有限の $\rho$ の値で厳密な制約解を回復できる。しかし、厳密ペナルティ関数の非微分性（キンク／折れ曲がり）や、必要とされる有限な $\rho$ の大きさの不明さが、歴史的に非線形計画における実用的な適用を妨げてきた。

手法
著者らは、ペナルティ定数 $\rho$ を連続的なパラメータとして扱うことにより、厳密ペナルティ法の困難を回避するパス・フォローイング（経路追跡）戦略を提案している。単一の大きな $\rho$ において最適化を行うのではなく、アルゴリズムは無制約解（$\rho=0$）から出発し、制約が満たされるまで $\rho$ を増加させながら、解 $x(\rho)$ の連続的な関数をトレースする。

本手法の核心は、以下のステップに基づくものである：

1. 定常条件： 解の経路は、サロゲート関数 $E_\rho(x) = f(x) + \rho \sum |g_i(x)| + \rho \sum \max\{0, h_j(x)\}$ の定常条件によって特徴付けられる。これには、非微分なペナルティ項に対する劣勾配が含まれる。
2. 区分的滑らかさ： 解の経路は区分的に滑らかである。「キンク」は、解が制約境界に接触したとき、境界に沿って移動するとき、あるいは境界から離脱するときに発生する。
3. 常微分方程式 (ODE)： キンクの間、経路は滑らかである。著者らは、変数 $x$ とラグランジュ乗数（$\lambda, \omega$）の進化を $\rho$ に対して記述するODEを導出している。これは、定常条件と活性制約方程式の系に陰関数定理を適用することで達成される。
   • 一般的な凸計画問題の場合、このODEは目的関数のヘッセ行列と活性な制約の勾配を含む。
   • 二次計画問題 (QP) かつアフィン制約を持つ場合、経路は区分線形となり、数値積分を行うことなく、次の「イベント」（制約への接触または離脱）を正確に計算できる。
   • 一般的な凸問題の場合、著者らは標準的なODEソルバー（例：Matlabの ODE45）を使用して、セグメントごとに解を進め、必要に応じてニュートン法による補正を行うことを提案している。
4. ランク不足の処理： 目的関数が厳密に凸でない場合や制約が冗長な場合（例：画像デノイジング）、著者らは再パラメータ化（例：零空間法や正則化項の追加）を提案し、ODEに必要なシステム行列の可逆性を確保する。

主な貢献

• 厳密パス・フォローイングの実現可能性： 本論文は、厳密なペナルティの非微分性が、解の経路を連続的に追跡すれば最適化の障壁にはならないことを示している。キンクは、制約が活性化または非活性化する「イベント」を検出することで管理される。
• パスODEの導出： 著者らは、一般的な凸計画問題における解の経路を支配する微分方程式を導出し、ペナルティ定数の変化と原始変数および双対変数の変化を結びつけた。
• QPへの特化： 二次計画問題（アフィン制約付き）において、経路が区分線形であることを強調しており、Lasso回帰などで用いられる「ラージジャンプ」アルゴリズムと同様の、極めて効率的な計算を可能にしている。
• 多様な応用： 本フレームワークは、以下を含む幅広い問題に適用されている：
  • 凸集合への射影。
  • 非負最小二乗法 (NNLS) および非負行列因子分解 (NNMF)。
  • 二次制約付き二次計画問題 (QCQP)。
  • 幾何計画法（対数・指数変換による）。
  • 半正定値計画法 (SDP)（最小固有値を凸制約として利用）。
  • 画像デノイジング： 本手法をRudin-Osher-Fatemi (ROF) モデルおよび異方性全変動（anisotropic total variation）に適用し、パス・フォローイングが、空白の画像からデノイズされた結果に至るまでの全レギュラライゼーション・パスをどのように明らかにするかを示している。

結果
論文内の数値例は、アルゴリズムのメカニズムを例証している：

• 射影： 経路は実行可能領域に向かってベクトル場に従い、境界に接触し、その上を滑る。
• NNLS/NNMF： アルゴリズムは部分問題を効率的に解き、その経路は区分線形となる。
• QCQPおよび幾何計画法： 軌跡は複雑な実行可能領域（円盤の交わり）や非線形制約を巧みにナビゲートし、制約付き最小値へと収束する。
• 画像デノイジング： 本手法は、灯台のノイズを含んだ画像の再構成に成功している。経路は $\rho$ が減少する過程（正則化の文脈において）を追跡し、ノイズが除去されるにつれて画像の構造が現れる様子を示す。計算コストは、単一の $\rho$ に対する最先端の手法と同等であることが示されているが、得られるメリットは「解の経路全体」を提供できる点にある。

意義と主張
著者らは、本研究を、制約付き最適化における厳密パス・フォローイングの実現可能性と汎用性に関する控えめな評価として位置づけている。内点法との直接的な性能比較については、より実践的な観点からの将来の研究として保留している。

主張されている意義は以下の通りである：

1. 概念的連結： 本研究は、厳密ペナルティ法の実装としてのパス・フォローイングを具体的に探索した最初の試みであり、ペナルティ法とホモトピー／継続法の間の溝を埋めるものである。
2. 正則化への洞察： 逆問題（画像デノイジングなど）の文脈において、本手法は解の経路の完全なビューを提供し、ペナルティと予測因子がどのように相互作用するかについての洞察を与える。
3. アルゴリズムの簡潔さ： このアプローチは、内点法の複雑なバリア機構を避けつつ、古典的な二次ペナルティ法の悪条件を回避しながら、堅牢なODEソルバー（Matlabなど）を用いた実装が容易である。
4. 堅牢性： 著者らは、非凸の設定において、グローバルな最小値とローカルな最小値を分離する上で、パス・フォローイングが競合する手法よりも信頼性が高い可能性があることを示唆している（ただし、これは現在のテキストにおける証明された結果ではなく、将来の方向性として述べられている）。

結論として、著者らは、非常に多くの制約を扱う際の過度な計算コストなどの限界を認め、非凸問題や異なるペナルティ構造へのさらなる一般化を示唆している。