劣勾配法

サブグラディエント法は、サブ微分を使用する凸最適化法です。1960年代から 1970 年代にかけてNaum Z. Shorらによって開発されたサブグラディエント法は、微分不可能な目的関数に適用しても収束します。目的関数が微分可能である場合、制約のない問題に対するサブグラディエント法は、最急降下法と同じ探索方向を使用します。

2 回連続的に微分可能な凸関数を最小化するために適用する場合、サブグラディエント法はニュートン法よりも遅くなります。ただし、ニュートン法は微分不可能なキンクを持つ問題では収束しません。

近年、凸最小化問題に対していくつかの内点法が提案されていますが、サブグラディエント射影法と関連するバンドル降下法は依然として競争力があります。非常に大きな次元数の凸最小化問題の場合、サブグラディエント射影法は必要なストレージが小さいため適しています。

サブグラディエント投影法は、分解技術を用いた大規模な問題によく適用されます。このような分解法では、多くの場合、問題に対して単純な分散法が使用可能になります。

を定義域を持つ凸関数とする。古典 的な劣勾配法は、 が におけるの任意の劣勾配を表し、が の反復である ところを繰り返す。 が微分可能であれば、その唯一の劣勾配は勾配ベクトルそのものである。 が におけるの降下方向ではない場合もあり得る。したがって、これまでに見つかった目的関数の最小値を追跡するリストを 維持する。すなわち、${\displaystyle f:\mathbb {R} ^{n}\to \mathbb {R} }$${\displaystyle \mathbb {R} ^{n}.}$$${\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }$$${\displaystyle g^{(k)}}$ ${\displaystyle f\}$${\displaystyle x^{(k)},\ }$${\displaystyle x^{(k)}}$${\displaystyle k^{th}}$${\displaystyle x.}$${\displaystyle f\}$${\displaystyle \nabla f}$${\displaystyle -g^{(k)}}$${\displaystyle f\}$${\displaystyle x^{(k)}.}$${\displaystyle f_{\rm {best}}\ }$$${\displaystyle f_{\rm {best}}^{(k)}=\min\{f_{\rm {best}}^{(k-1)},f(x^{(k)})\}.}$$

サブグラディエント法では、さまざまな種類のステップ サイズ ルールが使用されます。この記事では、収束の証明が知られている 5 つの古典的なステップ サイズ ルールについて説明します。

• 一定のステップサイズ、${\displaystyle \alpha _{k}=\alpha .}$
• 一定のステップ長は、${\displaystyle \alpha _{k}=\gamma /\lVert g^{(k)}\rVert _{2},}$${\displaystyle \lVert x^{(k+1)}-x^{(k)}\rVert _{2}=\gamma .}$
• 平方和可能だが和可能ではないステップサイズ、すなわち、$${\displaystyle \alpha _{k}\geq 0,\qquad \sum _{k=1}^{\infty }\alpha _{k}^{2} <\infty ,\qquad \sum _{k=1}^{\infty }\alpha _{k}=\infty .}$$
• 非加算的減少、すなわち、$${\displaystyle \alpha _{k}\geq 0,\qquad \lim _{k\to \infty }\alpha _{k}=0,\qquad \sum _{k=1}^{\infty }\アルファ _{k}=\infty .}$$
• 加算不可能な減少ステップ長、すなわち${\displaystyle \alpha _{k}=\gamma _{k}/\lVert g^{(k)}\rVert _{2},}$$${\displaystyle \gamma _{k}\geq 0,\qquad \lim _{k\to \infty }\gamma _{k}=0,\qquad \sum _{k=1}^{\infty }\ガンマ _{k}=\infty .}$$

5 つのルールすべてにおいて、ステップ サイズは、メソッドが反復される前に「オフライン」で決定されます。ステップ サイズは、前の反復には依存しません。サブグラディエント メソッドのこの「オフライン」特性は、微分可能関数の降下メソッドで使用される「オンライン」ステップ サイズ ルールとは異なります。微分可能関数を最小化する多くのメソッドは、ステップ サイズが通常現在のポイントと現在の検索方向に依存する、Wolfe の収束の十分条件を満たしています。サブグラディエント メソッドのステップ サイズ ルール (増分バージョンを含む) に関する詳細な説明は、Bertsekas ^[1]および Bertsekas、Nedic、および Ozdaglar の著書に記載されています。^[2]

一定のステップ長とユークリッドノルムが1に等しいスケールされた部分勾配の場合、部分勾配法は最小値に任意に近い近似値に収束します。

${\displaystyle \lim _{k\to \infty }f_{\rm {best}}^{(k)}-f^{*}$ショアの結果による。^[3]

これらの古典的なサブグラディエント法はパフォーマンスが低く、一般的な使用には推奨されなくなりました。^{[4] [5]}しかし、これらの方法は単純であり、問​​題の特殊な構造を利用するために簡単に適応できるため、特殊なアプリケーションでは依然として広く使用されています。

1970年代、クロード・ルマレシャルとフィル・ウルフは、凸最小化の問題に対する降下法「バンドル法」を提案した。^[6]「バンドル法」という用語の意味は、この頃から大きく変化した。現代版と完全な収束解析はキウィエルによって提供された。 ^[7]現代のバンドル法は、ステップサイズの選択に「レベル制御」ルールを使用することが多く、ボリス・T・ポリアック (1969) の「サブグラディエント射影」法から技術を発展させている。しかし、バンドル法がサブグラディエント射影法よりもあまり有利ではない問題もある。^{[4] [5]}

劣勾配法の拡張の一つに、制約付き最適化問題 を解く射影劣勾配法がある。

対象を最小限に抑える${\displaystyle f(x)\ }$$${\displaystyle x\in {\mathcal {C}}}$$

ここで は凸集合である。射影劣勾配法では、 が への射影であり がにおけるの任意の劣勾配 である反復を使用する 。${\displaystyle {\mathcal {C}}}$$${\displaystyle x^{(k+1)}=P\left(x^{(k)}-\alpha _{k}g^{(k)}\right)}$$${\displaystyle P}$${\displaystyle {\mathcal {C}}}$${\displaystyle g^{(k)}}$${\displaystyle f\}$${\displaystyle x^{(k)}.}$

劣勾配法は不等式制約問題を解くために拡張できる。

対象を最小限に抑える${\displaystyle f_{0}(x)\ }$$${\displaystyle f_{i}(x)\leq 0,\quad i=1,\ldots ,m}$$

ここで、は凸です。アルゴリズムは、 がステップ サイズ、 が目的関数または における制約関数の 1 つのサブ勾配である 場合、制約がない場合と同じ形式になります。 ここ で、はのサブ微分を表します。 現在のポイントが実行可能な場合、アルゴリズムは目的関数のサブ勾配を使用します。現在のポイントが実行不可能な場合、アルゴリズムは違反した制約のサブ勾配を選択します。 ${\displaystyle f_{i}}$$${\displaystyle x^{(k+1)}=x^{(k)}-\alpha _{k}g^{(k)}\ }$$${\displaystyle \alpha _{k}>0}$${\displaystyle g^{(k)}}$${\displaystyle x.\}$$${\displaystyle 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{ }}f_{j}(x)>0\end{cases}となるある }}j{\text{ に対して$$${\displaystyle \partial f}$${\displaystyle f.\}$

• 確率的勾配降下法 – 最適化アルゴリズム

• Bertsekas, Dimitri P. (1999).非線形プログラミング. ベルモント、マサチューセッツ州: Athena Scientific. ISBN 1-886529-00-0。
• Bertsekas, Dimitri P.; Nedic, Angelia; Ozdaglar, Asuman (2003)。凸解析と最適化（第 2 版）。ベルモント、マサチューセッツ州：Athena Scientific。ISBN 1-886529-45-0。
• Bertsekas, Dimitri P. (2015).凸最適化アルゴリズム. ベルモント、マサチューセッツ州: Athena Scientific. ISBN 978-1-886529-28-1。
• ショア、ナウム Z. (1985)。微分不可能な関数の最小化法。シュプリンガー・フェアラーク。ISBN 0-387-12763-1。
• Ruszczyński, Andrzej (2006).非線形最適化. プリンストン、ニュージャージー:プリンストン大学出版局. pp. xii+454. ISBN 978-0691119151MR  2199043 。

• EE364A と EE364B、スタンフォードの凸最適化コース シーケンス。