劣勾配法

劣勾配法（れつこうばいほう、英: Subgradient methods）とは、劣微分を用いた凸最適化の解法である。1960年代から1970年代にかけてナウム・ショアによって編み出された解法であり、微分不可能な目的関数に対して収束性を持つことが知られている。目的関数が微分可能な関数で無制約な問題の場合は最急降下法と同様の探索方向が使用される。

劣勾配法は2階微分可能な連続凸最小化問題に対してニュートン法より収束が遅いが、ニュートン法は微分不可能な点を持つ問題に対して適用することができないことから、汎用性が高い解法である。

近年では、凸最適化問題に対して内点法が提案されているが、射影劣勾配法やバンドル法といった解法も研究がなされている。劣勾配法などは計算にかかるメモリの量が比較的少量で済むことから、高次元の凸最適化問題に対しては適した解法である。

射影劣勾配法は大規模問題に対して分解法と共に使用されることが多い。分解法を用いることで問題を分割して問題を安易に扱うことができる。

古典的な劣勾配法の規則

定義域 $\mathbb {R} ^{n}.$ において凸関数を $f:\mathbb {R} ^{n}\to \mathbb {R}$ とする。 最も古典的な劣勾配法は以下の式によって反復点が更新される: $$x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\$$ ただし $g^{(k)}$ は 点 $x^{(k)}\$ における $f\$ の劣勾配を表し、$x^{(k)}$ は $k$ 回目の $x$ を表す。 もし $f\$ が微分可能関数であるならば、劣勾配は勾配 $\nabla f$ と等しい。 ある反復において劣勾配 $-g^{(k)}$ が $x^{(k)}$ の $f\$ における降下方向ではない可能性もあり得る。したがって反復を通じて最良の目的関数値 $f_{\rm {best}}\$ を記録する必要があり、これは: $$f_{\rm {best}}^{(k)}=\min\{f_{\rm {best}}^{(k-1)},f(x^{(k)})\}$$ と表される。

ステップサイズ規則

劣勾配法にはいくつかのステップサイズ規則が知られている。本記事では収束性が証明されている古典的なステップサイズ規則について説明する。

• Constant step size: $\alpha _{k}=\alpha .$
• Constant step length: $\alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2}.$ ただし、$\lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma .$
• Square summable but not summable step size: 以下の性質を満たすもの$$\alpha _{k}\geq 0,\qquad \sum _{k=1}^{\infty }\alpha _{k}^{2}<\infty ,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .$$
• Nonsummable diminishing: 以下の性質を満たすもの$$\alpha _{k}\geq 0,\qquad \lim _{k\to \infty }\alpha _{k}=0,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .$$
• Nonsummable diminishing step lengths: $\alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2}.$ ただし、$$\gamma _{k}\geq 0,\qquad \lim _{k\to \infty }\gamma _{k}=0,\qquad \sum _{k=1}^{\infty }\gamma _{k}=\infty .$$

上記のステップサイズの規則ではステップサイズは反復開始前にあらかじめ固定するオフライン型に分類される。つまり各ステップサイズは各反復における情報を利用しない。このオフライン型の規則は微分可能関数に対する降下法で用いられるオンライン型のステップサイズの規則とは異なった規則となっている。具体的には微分可能関数の最小化問題に対する手法ではウルフ条件を満たすステップサイズを選択する。このときステップサイズは各反復における点や探索方向を用いて決定される。（改良型を含む）劣勾配法におけるステップサイズの規則に関する内容は Bertsekasおよび Bertsekas、Nedic、Ozdaglar の著書にまとめられている。

収束の結果

constant step-length を使用し劣勾配のユークリッドノルムが1となるようにスケーリングした場合、劣勾配法は最小値に十分近い値へ収束することがショアにより示されている。すなわち、

$\lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}<\epsilon$

が成り立つ。古典的なこれらの劣勾配法は収束が遅いことから、現在では一般的な問題に対して推奨されていないが、特定の問題ではその問題特有の性質を活かすことで簡単に適応するできるため、広く用いられている。

射影劣勾配法とバンドル法

1970年代、凸最適化問題に対して降下法の一種のバンドル法をクロード・ルマレシャルとフィル・ウルフによって提案された。バンドル法は提案当時と現在において違う意味合いで用いられていた。現在知られている改良型のバンドル法や収束性の解析についてはKiwielによってによってまとめられた。 現在のバンドル法はボリス・ポリャク（1969）の射影劣勾配法から編み出されたステップサイズ決定のためのLevel Control規則を用いている。しかし、特定の問題では射影劣勾配法の方がバンドル法よりも優位性を持っている。

制約付き最適化問題

射影勾配法

劣勾配法を拡張させた解法として射影劣勾配法が挙げられる。以下の最適化問題:

minimize $f(x)\$ subject to $$x\in {\mathcal {C}}$$

を考える。ただし、${\mathcal {C}}$ は凸集合を表す。 射影劣勾配法は以下の式によって値を更新していく: $$x^{(k+1)}=P\left(x^{(k)}-\alpha _{k}g^{(k)}\right)$$ ただし、$P$ は ${\mathcal {C}}$ の射影、かつ $g^{(k)}$ は $x^{(k)}$ における $f\$ の劣勾配を表す。

一般の制約

劣勾配法は不等式制約付き最適化問題に対する解法として拡張することができる。以下の最適化問題を考える:

minimize $f_{0}(x)\$ subject to $$f_{i}(x)\leq 0,\quad i=1,\ldots ,m$$

ただし、$f_{i}$ は凸関数である。不等式制約付き最適化問題においても無制約最適化問題と同様に更新式は $$x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\$$ となる。ただし、$\alpha _{k}>0$ はステップサイズであり、$g^{(k)}$ は $x\$ における目的関数・制約の関数の劣勾配を表す。すなわち、 $$g^{(k)}={\begin{cases}\partial f_{0}(x)&{\text{ if }}f_{i}(x)\leq 0\;\forall i=1\dots m\\\partial f_{j}(x)&{\text{ for some }}j{\text{ such that }}f_{j}(x)>0\end{cases}}$$ と表される。ただし、$\partial f$ は $f\$ の劣微分である。現在の反復点が制約を満たす場合、劣勾配法は目的関数の劣勾配により値を更新する。現在の反復点が制約を満たさない場合、劣勾配法は違反している制約関数の劣勾配から値を更新する。

参考文献

• Bertsekas, Dimitri P. (1999). Nonlinear Programming. Belmont, MA.: Athena Scientific. ISBN 1-886529-00-0 
• Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003). Convex Analysis and Optimization (Second ed.). Belmont, MA.: Athena Scientific. ISBN 1-886529-45-0 
• Bertsekas, Dimitri P. (2015). Convex Optimization Algorithms. Belmont, MA.: Athena Scientific. ISBN 978-1-886529-28-1 
• Shor, Naum Z. (1985). Minimization Methods for Non-differentiable Functions. Springer-Verlag. ISBN 0-387-12763-1 
• Ruszczyński, Andrzej (2006). Nonlinear Optimization. Princeton, NJ: Princeton University Press. pp. xii+454. ISBN 978-0691119151. MR2199043 

関連項目

• 確率的勾配降下法

外部リンク

• EE364A and EE364B, Stanford's convex optimization course sequence.