Locally-averaged McCormick relaxations for discretization-regularized inverse problems

この論文「Locally-averaged McCormick Relaxations for Discretization-regularized Inverse Problems（離散化正則化された逆問題のための局所平均化 McCormick リラックス）」は、偏微分方程式（PDE）における係数同定問題、特に非凸な最適化問題に対する大域最適解の探索と、そのための双対境界（下限）の計算手法を提案したものです。

以下に、問題設定、手法、主要な貢献、結果、および意義について詳細な技術的サマリーを記述します。

1. 問題設定

• 対象問題: 間接的な観測データから偏微分方程式（PDE）の係数（ここではポテンシャル $w$）を同定する逆問題。
• 数学的定式化:
  • 状態方程式: $Au + f_0 uw = f_1$ （$A$ は有界線形作用素、$u$ は状態、$w$ は同定したい係数）。
  • 目的関数: 観測誤差 $\|Tu - y^\delta\|_Y$ の最小化（$y^\delta$ はノイズを含む観測データ）。
  • 制約: $w$ は事前知識に基づく有界制約（$w_\ell \le w \le w_u$）を満たす。
• 課題:
  1. 非凸性: 状態方程式における $uw$ の積項により、最適化問題が非凸となり、勾配法などの局所最適化アルゴリズムでは大域最適解の保証が得られない。
  2. 不適切性: 逆問題は本質的に不適切（ill-posed）であり、正則化が必要。
  3. 大域最適化の計算コスト: 空間分枝限定法（spatial branch-and-bound）などの大域最適化アルゴリズムを用いるには、 tight な双対境界（下限）の計算が必要だが、McCormick リラックスをそのまま適用すると制約数が膨大になり計算不可能になる。

2. 提案手法

論文は、**「離散化による正則化」と「局所平均化された McCormick リラックス」**を組み合わせるアプローチを提案しています。

A. 離散化による正則化 (Regularization by Discretization)

• 係数 $w$ を有限次元の空間（メッシュサイズ $h$ の要素）に制限することで、問題を正則化します。
• ノイズレベル $\delta$ とメッシュサイズ $h$ の関係を適切に調整（$h(\delta)$）することで、ノイズが減少するにつれて真の解に収束することを理論的に保証します。

B. McCormick リラックスと局所平均化 (Locally-averaged McCormick Relaxations)

• McCormick リラックス: 非線形項 $z = uw$を新しい変数$z$に置き換え、$u$と$w$の上下界（$u_\ell, u_u, w_\ell, w_u$）を用いて 4 つの線形不等式（McCormick 不等式）を追加することで、凸緩和（Convex Relaxation）を行います。これにより双対境界（下限）が得られます。
• 局所平均化 (Local Averaging):
  • 従来の McCormick リラックスを全領域で適用すると、メッシュの節点数に比例して制約数が膨大になり、計算が不可能になります。
  • 解決策として、領域を部分集合 $Q_\tau$ に分割し、その部分集合内で状態 $u$ と係数 $w$ を局所的に平均化（$P_\tau u, P_\tau w$）した上で McCormick 不等式を適用します。
  • これにより、不等式の数が大幅に削減され、有限個の線形制約を持つ凸最適化問題（$(McC_{\delta\tau})$）として定式化できます。

C. 最適化ベースの境界絞り込み (OBBT: Optimization-Based Bound Tightening)

• 初期の $u$ の上下界は PDE 理論から得られるが、非常に緩い（保守的）ため、緩和の精度が低くなります。
• OBBT を用いて、線形計画問題を反復的に解くことで、$u$ の上下界を絞り込み、McCormick 不等式による緩和の精度を向上させます。
• 局所平均化により制約数が減っているため、OBBT の計算コストを現実的な範囲に抑えることができます。

3. 主要な理論的貢献

1. 収束性の証明:
   • 提案された緩和問題 $(McC_{\delta\tau})$ の解が、元の非凸問題 $(I)$ および離散化問題 $(I_\delta)$ の近似下限を提供することを証明しました。
   • ノイズレベル $\delta \to 0$、メッシュサイズ $h, \tau \to 0$ の極限において、解が真の係数 $w^\dagger$ に収束し、その収束速度（誤差評価）を導出しました。
   • 収束速度は、問題の ill-posedness の度合い（$s$）と次元 $d$ に依存し、$O(\delta^{\frac{1}{1+4s}})$ などのレートが得られます。
2. 誤差のバランス取り:
   • 離散化誤差、緩和誤差、ノイズ誤差、および最適化精度（$\varepsilon$）をバランスさせるためのメッシュサイズ $h, \tau$ の選択条件を導出しました。
3. 正則化としての離散化:
   • 単なる数値近似ではなく、離散化自体が逆問題の正則化として機能し、ノイズの伝播を制御することを示しました。

4. 数値実験結果

• 設定: 1 次元の楕円型 PDE における係数同定問題（$w(x) = \cos(2\pi x)^2$ の回復）。ノイズレベル $\delta$ を $10^{-1}$ から $10^{-5}$ まで変化させました。
• 比較対象:
  • O: OBBT を適用した局所平均化 McCormick リラックスの解を初期値とする L-BFGS-B（局所最適化）。
  • P: OBBT 無しの緩和解を初期値。
  • N: 定数関数（0.5）を初期値。
• 結果:
  • 精度: O 初期化は、他の手法に比べて圧倒的に低い再構成誤差（reconstruction error）を示しました。特にノイズが小さい場合、誤差は理論予測レートに近い減少傾向を示しました。
  • 大域最適解への到達: O 初期化では、真の解 $w^\dagger$ に非常に近い解が得られましたが、P や N では局所解に陥り、解の形状が著しく異なっていました。
  • 計算コスト: 厳密な双対境界の計算（OBBT）には時間がかかりますが、空間分枝限定法全体を実行するよりも遥かに安価であり、かつ局所最適化の初期値として極めて有効であることが示されました。

5. 意義と結論

• 実用的な大域最適化: 非凸な PDE 逆問題において、空間分枝限定法のような高コストな大域最適化アルゴリズムを直接実行しなくても、**「局所平均化 McCormick リラックス + OBBT + 局所最適化」**という組み合わせにより、高品質な大域最適解（またはその近似）を効率的に得られることを実証しました。
• 理論と実践の統合: 離散化正則化の理論（収束性）と、大域最適化のための凸緩和手法を統合し、両者の誤差を定量的に評価・バランスさせる枠組みを提供しました。
• 将来展望: 高次元問題への拡張には、OBBT の計算コスト（線形計画問題の数）が課題となりますが、ウォームスタート、並列化、カット平面法などの技術で対応可能であるとしています。

総じて、この論文は、逆問題の非凸性と不適切性を同時に扱い、理論的に保証された収束性を持ちながら、計算的に実行可能な大域最適化アプローチを提案した重要な研究です。