近接勾配法

近接勾配法（きんせつこうばいほう、英: Proximal gradient methods）とは微分不可能凸最適化問題を解くための射影を用いた解法である。以下のような凸最適化問題として定式化されたとする:

各反復における射影勾配法（赤）と簡約勾配法（緑）の比較。

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

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

近接勾配法は分離ステップから開始され、関数 $f_{1},...,f_{n}$ を個別の問題として扱うことで実装が容易なアルゴリズムによって問題を解く。近接という名称は $f_{1},...,f_{n}$ に含まれる微分不可能な関数それぞれが近接作用素を介して扱うことから名づけられている。反復縮小しきい値アルゴリズム（英: Iterative shrinkage thresholding algorithm）、射影ランドウェバー法、射影勾配法、交互射影法、 交互乗数法、交互分離ブレグマン法は近接勾配法の特別な例として知られている。

近接勾配法の理論は統計的学習理論に応用されており、詳細は近接勾配法による学習を参照。

例

近接勾配法の例として:

• 射影ランドウェバー法
• 交互射影法
• 交互乗数法

参考文献

• Rockafellar, R. T. (1970). Convex analysis. Princeton: Princeton University Press 
• Combettes, Patrick L.; Pesquet, Jean-Christophe (2011). Fixed-Point Algorithms for Inverse Problems in Science and Engineering. 49. pp. 185–212 

関連項目

• 近接作用素
• 近接勾配法による学習
• 簡約勾配法

外部リンク

• 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.