ブレグマン法

ブレグマン法は、正則化を伴う特定の凸最適化問題を解く反復アルゴリズムです。^[1]元のバージョンは、1967年にレブ・M・ブレグマンによって発表されました。 ^[2]

このアルゴリズムは制約関数に一つずつアクセスする行アクション法であり、制約を効率的に列挙できる大規模な最適化問題に特に適しています^[要出典] 。このアルゴリズムは、ノルムなどの正規化関数に特に適しており、誤差キャンセル効果により非常に速く収束します。^[3]${\displaystyle \ell _{1}}$

ブレグマン法を使用するには、 （ は のような正規化関数）を見つけるという問題を設定する必要があります。[ 3 ^]${\displaystyle \min _{u}J(u)+f(u)}$${\displaystyle J}$${\displaystyle \ell _{1}}$

ブレグマン距離は、が におけるのサブ微分（ と表記）に属する場合と定義されます。 ^{[3] [4]}ユーザーが選択した定数で を反復し（最小化は通常の凸最適化アルゴリズムで実行します）、^[3]またはを反復します。この場合、 は のメンバーとして毎回選択されます。^[4]${\displaystyle D^{p}(u,v):=J(u)-(J(v)+\langle p,u-v\rangle )}$${\displaystyle p}$${\displaystyle J}$${\displaystyle u}$${\displaystyle \partial J(u)}$${\displaystyle u_{k+1}:=\min _{u}(\alpha D(u,u_{k})+f(u))}$${\displaystyle \alpha }$${\displaystyle u_{k+1}:=\min _{u}(D^{p_{k}}(u,u_{k})+f(u))}$${\displaystyle p_{k}}$${\displaystyle \partial J(u_{k})}$

このアルゴリズムは、主変数と双対変数のペアから開始します。次に、各制約に対して、その実行可能セットへの一般化投影が実行され、制約の双対変数と、制約関数の勾配に非ゼロ係数があるすべての主変数の両方が更新されます。目的関数が厳密に凸で、すべての制約関数が凸である場合、この反復投影の限界は、最適な主双対ペアに収束します。^{[引用が必要]}

基底追求型問題の場合、ブレグマン法は双対問題 における通常の勾配降下法と同等である。^[5]この場合、正確な正則化型効果も発生する。 が特定の閾値を超えると、 の最適値はの最適解とまったく同じになる。^{[3] [5]}${\displaystyle \min _{x:Ax=b}(|x|_{1}+{\frac {1}{2\alpha }}|x|_{2}^{2})}$${\displaystyle \min _{y}(-b^{t}y+{\frac {\alpha }{2}}|A^{t}y-{\text{Proj}}_{[-1,1]^{n}}(A^{t}y)|^{2})}$${\displaystyle \alpha }$${\displaystyle x}$${\displaystyle \min _{x:Ax=b}|x|_{1}}$

ブレグマン法またはその一般化は、以下に適用できます。

• 画像のぼかし除去またはノイズ除去^[3]（全変動ノイズ除去^[4]を含む）
• MR画像^[要説明]再構成^[3]
• 磁気共鳴画像法^{[1] [6]}
• レーダー^[1]
• ハイパースペクトルイメージング^[7]
• 圧縮センシング^[5]
• 最小絶対偏差または正規化線形回帰^[8]${\displaystyle \ell _{1}}$
• 共分散選択（疎共分散行列の学習）^[8]
• 行列補完^[9]
• 構造的リスク最小化^[8]

この方法は、乗数法や双対上昇法（いわゆるブレグマン交互方向乗数法^{[10] [7]}を介して、交互方向乗数法^[8]を一般化したもの）と関連しており、複数の一般化が存在します。

この方法の欠点の1つは、目的関数が厳密に凸である場合にのみ収束することが証明されていることです。線形計画法や非厳密に凸な2次計画法のように、これが保証できない場合は、近似勾配法などの追加の方法が開発されています。^[要出典]画像ノイズ除去のRudin-Osher-Fatemiモデルの場合^[要説明]、Bregman法は収束することが証明されています。^[11]

ブレグマン法の一般化には次のようなものがあります。

• 逆スケール空間法^{[説明が必要] [3]}
• 線形化ブレグマン^[3]
• ロジスティックブレグマン^[3]
• スプリット・ブレグマン^[3]

線形化ブレグマン法では、中間目的関数を、第 2 項を(第 2 項を の近くで近似する) に置き換え、定数 のペナルティ項を追加することで線形化します。この結果は、特に基底追求型の問題では、計算がはるかに容易になります。^{[4] [5]}一般的な基底追求問題の場合、 各コンポーネント について反復を と表すことができます。ここで と定義します。 ^[4]${\displaystyle D^{p}(u,u_{k})+f(u)}$${\displaystyle f(u_{k})+\langle f'(u_{k}),u-u_{k}\rangle }$${\displaystyle u_{k}}$${\displaystyle {\frac {1}{2\delta }}|u-u_{k}|_{2}^{2}}$${\displaystyle \delta }$${\displaystyle \min \mu |u|_{1}+{\frac {1}{2}}|Au-f|_{2}^{2}}$${\displaystyle v_{k+1}:=v_{k}+A^{t}(f-Au_{k}),u_{k+1,i}:=\delta ~{\text{shrink}}(v_{k,i},\mu )}$${\displaystyle i}$${\displaystyle {\text{shrink}}(y,a):={\begin{cases}y-a,&y\in (a,\infty )\\0,&y\in [-a,a]\\y+a,&y\in (-\infty ,-a)\end{cases}}}$

線形化ブレグマン法を実行すると、残差^{[説明が必要]がほぼ一定である「停滞」期間が発生することがあります。この問題を軽減するには、}キッキングを伴う線形化ブレグマン法を使用します。この方法では、停滞期間の始まりを検出し、予測してその終わりまでスキップします。^{[4] [5]}

線形化ブレグマン法は数学的には勾配降下法と同等であるため、直線探索、L-BGFS、バルジライ・ボルワインステップ、ネステロフ法などの勾配降下法を加速する方法で加速することができる。ネステロフ法は加速線形化ブレグマン法として提案されている。^{[5] [9]}

スプリットブレグマン法は、と がともに凸である形式 の問題、特に の形式 の問題を解きます。 [ ^{4 ]}まず、これを制約付き最適化問題 として書き直し、次に に緩和します。ここでは定数です。 を定義することで、問題を通常のブレグマンアルゴリズムで解ける問題に縮小できます。^{[4] [6]}${\displaystyle \min _{u}|\Phi (u)|_{1}+H(u)}$${\displaystyle \Phi }$${\displaystyle H}$${\displaystyle \min _{u}|\Phi u|_{1}+|Ku-f|^{2}}$${\displaystyle \min _{u:d=\Phi (u)}|d|_{1}+H(u)}$${\displaystyle \min _{u,d}|d|_{1}+H(u)+{\frac {\lambda }{2}}|d-\Phi (u)|_{2}^{2}}$${\displaystyle \lambda }$${\displaystyle J(u,d):=|d|+H(u)}$

スプリットブレグマン法は、Wirtinger導関数を用いた複素数の最適化に一般化されている。^[1]