近接勾配法

近接勾配法（きんせつこうばいほう、テンプレート:Lang-en-short）とは微分不可能凸最適化問題を解くための射影を用いた解法である。以下のような凸最適化問題として定式化されたとする: ファイル:Frank Wolfe vs Projected Gradient.webm

$\min_{x \in ℝ^{N}} \sum_{i = 1}^{n} f_{i} (x)$

ただし、 $f_{i} : ℝ^{N} \to ℝ, i = 1, \dots, n$ は微分不可能な凸関数を含んでいるとする。微分不可能な凸関数を含んでいる場合は最急降下法や共役勾配法は使用できないため、この場合に近接勾配法が使用される。

近接勾配法は分離ステップから開始され、関数 $f_{1}, . . ., f_{n}$ を個別の問題として扱うことで実装が容易なアルゴリズムによって問題を解く。近接という名称は $f_{1}, . . ., f_{n}$ に含まれる微分不可能な関数それぞれがテンプレート:仮リンクを介して扱うことから名づけられている。反復縮小しきい値アルゴリズム（テンプレート:Lang-en-short）^[1]、テンプレート:仮リンク、射影勾配法、テンプレート:仮リンク、交互乗数法、交互分離テンプレート:仮リンクは近接勾配法の特別な例として知られている^[2]。

近接勾配法の理論はテンプレート:仮リンクに応用されており、詳細はテンプレート:仮リンクを参照。

例

近接勾配法の例として:

Stephen Boyd and Lieven Vandenberghe Book, Convex optimization
EE364a: Convex Optimization I and EE364b: Convex Optimization II, Stanford course homepages
EE227A: Lieven Vandenberghe Notes Lecture 18
ProximalOperators.jl: a Julia package implementing proximal operators.
ProximalAlgorithms.jl: a Julia package implementing algorithms based on the proximal operator, including the proximal gradient method.
Proximity Operator repository: a collection of proximity operators implemented in MATLAB and Python.