Over-Relaxed Projected-Forward Iterations for Cocoercive Variational Inequalities: Active-Face Spectral Tuning

技術要約：ココサークティブな変分不等式に対する過剰緩和投影前方反復法

問題設定
本論文は、実ヒルベルト空間における非空閉凸集合 $X$ とココサークティブ（cocoercive）な作用素 $f$ に対する変分不等式（VI）問題、すなわち、すべての $x \in X$ に対して $\langle f(p), x - p \rangle \geq 0$ を満たす $p \in X$ を求める問題を取り扱う。焦点は、固定点写像 $G_\gamma = P_X(I - \gamma f)$ で定義される投影前方反復（前方・後方分裂の等価形式）に置かれている。

緩和反復 $x_{n+1} = x_n + \lambda_n(G_\gamma x_n - x_n)$ の大域的収束は、$\lambda_n$ が特定の平均化間隔内にある場合、すでに確立されている。しかし、既存の理論では、アルゴリズムが能動的な制約（「能動的な面（active face）」）を特定した後の、最適な緩和パラメータ $\lambda$ を決定する方法については示されていない。本論文は、投影の面が安定化した後、局所的なスペクトル半径を最小化するように $\lambda$ を選択する方法、特にボックス制約の場合について調査している。

手法
著者らは、厳密な相補性（strict complementarity）および局所的な微分可能性の仮定の下で、反復の漸近的挙動を分析している。

1. 有限面特定（Finite Face Identification）: 厳密な相補性の下では、アルゴリズムは能動的な集合（下限または上限にある変数）と自由な集合（範囲内に厳密にある変数）を有限時間内に特定する。一度特定されると、投影演算子 $P_X$ は、能動的な変数に対しては定数マスクとして、自由な変数に対しては恒等写像として機能する。
2. 局所線形化: 本論文では、$C^1$ 作用素に対する緩和写像 $R_{\gamma, \lambda}(x) = (1-\lambda)x + \lambda P_X(x - \gamma f(x))$ の解 $p$ における正確な微分を導出している。ボックス制約の場合、この微分 $M_{\gamma, \lambda}$ は以下のブロック三角形式をとる：
   • 能動ブロックの固有値は $|1 - \lambda|$ である。
   • 自由ブロックは、自由変数に制限された $f$ のヤコビアン（$J_{FF}$）に依存する。もし $J_{FF}$ が対称正定値であり、その固有値を $\theta_j$ とするならば、自由ブロックの固有値は $|1 - \lambda \gamma \theta_j|$ となる。
3. スペクトル最小化: 局所的な収束率は $\rho(M_{\gamma, \lambda})$ によって支配される。著者らは、$\max(|1-\lambda|, \max_j |1 - \lambda \gamma \theta_j|)$ を最小化するスカラー・ミニマックス問題を定式化している。
4. セーフガード付き選択（Safeguarded Selection）: 全域的な収束性を確保しつつ局所的な速度を活用するために、著者らは適応型アルゴリズム（Algorithm 1）を提案している。このアルゴリズムは以下の手順を踏む：
   • 能動的な面のパターンを監視する。
   • パターンが $K$ 回連続して安定した場合、そのパターンをロックする。
   • 自由ブロックのスペクトル極値を推定する。
   • 最適な $\lambda^*_{loc}$ を計算し、それを大域的な平均化間隔 $[\lambda_{min}, 1/\eta_\gamma - \epsilon]$ 内にクリップする。これにより、面の特定が時期尚早であったとしても、大域的な安全性を保証する。

主な貢献
本論文には、以下の5つの具体的な貢献がある。

1. グローバル・ベースライン: 強単調性とココサークティブ性を備えた緩和投影前方写像に対する鋭い大域的線形収束証明を確立し、局所解析のベースラインとしている。
2. 特定後の導出: 有限面特定後の $C^1$ 作用素に対する緩和写像の正確な微分を導出し、能動的なダイナミクスと自由なダイナミクスを分離するブロック三角構造を示した。
3. 閉形式による最適緩和: 対称正定値な自由ヤコビアンを持つボックス制約に対し、局所スペクトル半径の閉形式のスカラー最小化解を導出した：
   $$\lambda^*_{loc} = \frac{2}{a_\gamma + b_\gamma}$$
   ここで $a_\gamma$ および $b_\gamma$ は、集合 $\{1\} \cup \{\gamma \theta_j\}$ の最小値および最大値である。著者らは、真の過剰緩和（$\lambda^*_{loc} > 1$）のための条件として $a_\gamma + b_\gamma < 2$ を明示している。
4. 共同チューニングの特性化: 結合的に最適なペア $(\gamma, \lambda)$ を特性化している。重要な知見として、もし前方のステップ $\gamma$ を面特定後に自由に再調整できるのであれば、最適な $\gamma$ を用いた無緩和の選択（$\lambda=1$）がすでに局所的に最適となることが挙げられる。したがって、外側の緩和（outer relaxation）が最も価値を持つのは、$\gamma$ が固定されているか、あるいは保守的な設定となっている場合である。
5. セーフガード付き適応セレクター: 動的に能動的な面をロックし、スペクトルパラメータを推定し、緩和パラメータを安全な大域的区間にクリップして、大域的な収束性が決して損なわれないようにする実用的なアルゴリズムを提案している。

結果
高密度な120次元のアフィン・ベンチマークおよび80次元の非線形問題を用いた数値実験により、理論的知見が確認された。

• 制約付き前方ステップ: 前方のステップ $\gamma$ が大域的な境界を逸脱するベンチマークにおいて、適応型過剰緩和（固定 $\gamma$ を使用）は、無緩和法と比較して反復回数を約 33% 削減した。
• 再調整可能な前方ステップ: 最適な $\gamma$ が大域的に許容可能である非線形テストにおいて、$\gamma$ を再調整すること（$\lambda=1$）は、固定された保守的な $\gamma$ を用いた過剰緩和よりも優れた性能を示した。
• 安全性: パターン・リセット機構は、緩和パラメータが常に安全な区間にクリップされていたため、面の誤特定による一時的な変動が発生しても、大域的な収束性を損なうことなく対処できた。

意義と主張
本論文は、自身の貢献を、一般的な性能推定手法や汎用的な加速ヘリスティックの代替ではなく、メカニズムに特化した解析的ルールとして控えめに位置づけている。

• 適用範囲: 結果は、ココサークティブな作用素を持ち、自由な面のヤコビアンが対称正定値であるボックス制約付きのVIに適用される。
• 過剰緩和の役割: 著者らは、過剰緩和（$\lambda > 1$）が普遍的に優れているわけではないことを明確にしている。その独特の有用性は、前方のステップ $\gamma$ が事前に固定されているか、あるいは大域的な安定性の要件によって制約されている場合に生じる。このようなレジームにおいて、$\lambda$ は不適切な $\gamma$ を補償するための必要な制御変数として機能する。
• 限界: 解析は、行列の非正規性が多項式的なトランジェント（過渡現象）を引き起こす可能性を認め、一歩ごとのノルム縮小ではなく、スペクトル半径（漸近的なレート）に基づいている。また、閉形式の解はボックス制約の幾何学的構造に特有のものである。

結論として、本論文は過剰緩和が有益となる正確な基準を提供している。それは、前方ステップを局所的に最適化できない「固定前方ステップ・レジーム」における、標的を絞った加速ツールとしての役割である。