近位勾配法

近似勾配法は、微分不可能な凸最適化問題を解決するために使用される投影の一般化された形式です。

多くの興味深い問題は、次のような形の凸最適化問題として定式化できる。

${\displaystyle \operatorname {min} \limits _{x\in \mathbb {R} ^{N}}\sum _{i=1}^{n}f_{i}(x)}$

ここで、 はおそらく微分不可能な凸関数です。微分不可能なため、最急降下法や共役勾配法などの従来の滑らかな最適化手法は使用できませんが、代わりに近似勾配法を使用できます。 ${\displaystyle f_{i}:\mathbb {R} ^{N}\rightarrow \mathbb {R} ,\ i=1,\dots ,n}$

近似勾配法は分割ステップから始まり、関数を個別に使用して簡単に実装できるアルゴリズムを生成します。これらの関数が近似と呼ばれるのは、微分不可能な関数のそれぞれがその近接演算子を介して関係するためです。反復収縮閾値アルゴリズム、^[1]、投影ランドウェーバー、投影勾配、交互投影、交互方向乗数法、交互分割ブレグマンは、近似アルゴリズムの特殊な例です。^[2]${\displaystyle f_{1},...,f_{n}}$${\displaystyle f_{1},...,f_{n}}$

統計学習理論の観点からの近似勾配法の理論と統計学習理論への応用については、「学習のための近似勾配法」を参照してください。

広く使用されている凸最適化アルゴリズムの 1 つに、凸集合への射影(POCS) があります。このアルゴリズムは、複数の凸制約を同時に満たす信号を回復/合成するために使用されます。制約をモデル化する空でない閉じた凸集合のインジケータ関数を とします。これは凸実行可能性問題に帰着し、すべての凸集合の交差にあるような解を見つけることが求められます。POCS 法では、各集合はその射影演算子によって組み込まれます。したがって、各反復では は次のように更新されます。 ${\displaystyle f_{i}}$${\displaystyle C_{i}}$${\displaystyle C_{i}}$${\displaystyle C_{i}}$ ${\displaystyle P_{C_{i}}}$ ${\displaystyle x}$

${\displaystyle x_{k+1}=P_{C_{1}}P_{C_{2}}\cdots P_{C_{n}}x_{k}}$

しかし、このような問題を超えると、射影演算子は適切ではなく、より一般的な演算子で対処する必要があります。存在する凸射影演算子の概念のさまざまな一般化の中で、近似演算子は他の目的に最適です。

近接勾配法の特別な例としては、

• 投影されたランドウェーバー
• 交互投影
• 乗数の交互方向法

• 近位演算子
• 学習のための近似勾配法
• フランク・ウルフアルゴリズム

• Rockafellar, RT (1970)。凸解析。プリンストン：プリンストン大学出版局。
• Combettes, Patrick L.; Pesquet, Jean-Christophe (2011).科学と工学における逆問題のための固定小数点アルゴリズム。第 49 巻。pp. 185–212。

• Stephen Boyd と Lieven Vandenberghe の書籍、凸最適化
• EE364a: 凸最適化 I および EE364b: 凸最適化 II、スタンフォード大学のコースホームページ
• EE227A: リーベン・ヴァンデンバーグ・ノート 講義 18
• ProximalOperators.jl:近似演算子を実装するJuliaパッケージ。
• ProximalAlgorithms.jl:近似勾配法を含む、近似演算子に基づくアルゴリズムを実装するJuliaパッケージ。
• 近接演算子リポジトリ: MatlabおよびPythonで実装された近接演算子のコレクション。