フランク・ウルフのアルゴリズム

出典: フリー百科事典『ウィキペディア(Wikipedia)』

出典: フリー百科事典『ウィキペディア(Wikipedia)』

フランク・ウルフのアルゴリズム (: Frank–Wolfe algorithm) とは、条件英語版付き凸最適化問題を反復的一次最適化により解くアルゴリズム である。条件付き勾配法 (conditional gradient method)、[1] 簡約勾配法 (reduced gradient algorithm)、 凸結合法 (convex combination algorithm) とも呼ばれ、1956年にマルグリート・フランク英語版およびフィリップ・ウルフ英語版により提案された[2]。このアルゴリズムでは、各反復毎に目的関数の線形近似を行い、この(定義域を同じくする)線形関数を最適化する方向へと移動する。

問題定義[編集]

 をベクトル空間上のコンパクト集合とし、 を微分可能実関数とする。フランク・ウルフのアルゴリズムは、以下の最適化問題を解く。

Minimize
subject to .

アルゴリズム[編集]

フランク・ウルフのアルゴリズムの1ステップ
初期化:   とし、 を  に含まれる任意の点とする。
ステップ 1. 降下方向の決定: 次の条件を満たす  を解く。
Minimize
Subject to
(この部分問題は、 を  近傍で1次までテイラー近似して得られる線形関数を最小化するものと捉えることができる。)
ステップ 2. ステップサイズの決定:   を  の範囲内で最小化するような を算出し、利用する。
ステップ 3. 更新:   のように代入し、ステップ 1. に戻る。

性質[編集]

たとえば最急降下法など、他の条件付き最適化問題の解法においては各反復毎に許容範囲を射影する必要があるのに対し、フランク・ウルフのアルゴリズムは全ての反復で同一の範囲について部分問題を解けば、解は自動的に許容範囲に収まる。

フランク・ウルフのアルゴリズムの収束性は一般には劣線形である。勾配がなんらかのノルムについてリプシッツ連続であれば、k 回の反復の後の目的関数の値と最適値との誤差は  となる。部分問題を近似的に解いた場合でも同様の収束速度を実現することが示されている[3]

本アルゴリズムの各反復は、つねに許容範囲の極点の疎凸結合で表現することができる。このため、機械学習信号処理[4]および、例えば最小コストフロー問題などの輸送ネットワーク英語版[5]によく用いられる疎貪欲法アルゴリズムを応用することができる。

許容範囲がもし一連の線形拘束条件により与えられている場合、各反復における部分問題は線型計画法により解くことができる。

一般の問題について最悪収束速度  を改善することは不可能であるが、たとえば強凸問題など特定の種類の問題について、より早い収束速度を得ることはできる[6]

解の値の下限と主双対解析[編集]

 は凸関数であるから、任意の二点  に対し次の不等式が成立する。

この不等式は(未知の)最適解 ある点  について、最適な下限は次のように与えられる。

フランク・ウルフのアルゴリズムは、各反復において上式最終項の最適化問題を解くので、降下方向決定部分問題における解  を用いて解の下限  を徐々に更新していくことができる。すなわち、  とおくと次のように更新すればよい。

このように未知の最適値の下限を知ることができると、終止条件として用いることができるため実用上有用である。また、各反復においてつねに  が成立するため、近似の精度を効率的にみつもることができる。

この双対ギャップ英語版、すなわち  と  との差も同一の収束速度で減少すること、つまり が成立することが知られている。

出典[編集]

  1. ^ Levitin, E. S.; Polyak, B. T. (1966). “Constrained minimization methods”. USSR Computational Mathematics and Mathematical Physics 6 (5): 1. doi:10.1016/0041-5553(66)90114-5. 
  2. ^ Frank, M.; Wolfe, P. (1956). “An algorithm for quadratic programming”. Naval Research Logistics Quarterly 3: 95. doi:10.1002/nav.3800030109. 
  3. ^ Dunn, J. C.; Harshbarger, S. (1978). “Conditional gradient algorithms with open loop step size rules”. Journal of Mathematical Analysis and Applications 62 (2): 432. doi:10.1016/0022-247X(78)90137-3. 
  4. ^ Clarkson, K. L. (2010). “Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm”. ACM Transactions on Algorithms 6 (4): 1. doi:10.1145/1824777.1824783. 
  5. ^ Fukushima, M. (1984). “A modified Frank-Wolfe algorithm for solving the traffic assignment problem”. Transportation Research Part B: Methodological 18 (2): 169–177. doi:10.1016/0191-2615(84)90029-8. 
  6. ^ Bertsekas, Dimitri (1999). Nonlinear Programming. Athena Scientific. p. 215. ISBN 1-886529-00-0. 

参考文献[編集]

関連項目[編集]