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

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

問題定義

${\mathcal {D}}$ をベクトル空間上のコンパクトな凸集合とし、 $f\colon {\mathcal {D}}\to \mathbb {R}$ を微分可能な凸実関数とする。フランク・ウルフのアルゴリズムは、以下の最適化問題を解く。

Minimize

f(\mathbf {x} )

subject to

\mathbf {x} \in {\mathcal {D}}

.

アルゴリズム

初期化:

k\leftarrow 0

とし、

\mathbf {x} _{0}\!

を

{\mathcal {D}}

に含まれる任意の点とする。

ステップ 1. 降下方向の決定: 次の条件を満たす

\mathbf {s} _{k}

を解く。

Minimize

\mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})

Subject to

\mathbf {s} \in {\mathcal {D}}

（この部分問題は、

f

を

\mathbf {x} _{k}\!

近傍で1次までテイラー近似して得られる線形関数を最小化するものと捉えることができる。）

ステップ 2. ステップサイズの決定:

\alpha \leftarrow {\frac {2}{k+2}}

とする。もしくは、

0\leq \alpha \leq 1

を満す範囲内で、

f(\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k}))

を最小化するような

α

を算出する。

ステップ 3. 更新:

\mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k})

とし、

k\leftarrow k+1

とした上でステップ 1. に戻る。

性質

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

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

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

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

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

解の値の下限と主双対解析

$f$ は凸関数であるから、任意の二点 $\mathbf {x} ,\mathbf {y} \in {\mathcal {D}}$ に対し次の不等式が成立する。

f(\mathbf {y} )\geq f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )

この不等式は（未知の）最適解 $\mathbf {x} ^{*}$ $f(\mathbf {x} ^{*})\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )$ ある点 $\mathbf {x}$ について、最適な下限は次のように与えられる。

{\begin{aligned}f(\mathbf {x} ^{*})&\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )\\&\geq \min _{\mathbf {y} \in D}\left\{f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )\right\}\\&=f(\mathbf {x} )-\mathbf {x} ^{T}\nabla f(\mathbf {x} )+\min _{\mathbf {y} \in D}\mathbf {y} ^{T}\nabla f(\mathbf {x} )\end{aligned}}

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

l_{k}:=\max(l_{k-1},f(\mathbf {x} _{k})+(\mathbf {s} _{k}-\mathbf {x} _{k})^{T}\nabla f(\mathbf {x} _{k}))

このように未知の最適値の下限を知ることができると、終止条件として用いることができるため実用上有用である。また、各反復においてつねに $l_{k}\leq f(\mathbf {x} ^{*})\leq f(\mathbf {x} _{k})$ が成立するため、近似の精度を効率的にみつもることができる。

この双対ギャップ（英語版）、すなわち $f(\mathbf {x} _{k})$ と $l_{k}$ との差も同一の収束速度で減少すること、つまり $f(\mathbf {x} _{k})-l_{k}=O(1/k)$ が成立することが知られている。

出典

^ 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.
^ Frank, M.; Wolfe, P. (1956). “An algorithm for quadratic programming”. Naval Research Logistics Quarterly 3: 95. doi:10.1002/nav.3800030109.
^ 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.
^ 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.
^ 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.
^ Bertsekas, Dimitri (1999). Nonlinear Programming. Athena Scientific. p. 215. ISBN 1-886529-00-0

参考文献

Jaggi, Martin (2013). “Revisiting Frank–Wolfe: Projection-Free Sparse Convex Optimization”. Journal of Machine Learning Research: Workshop and Conference Proceedings 28 (1): 427–435. （概要論文）
The Frank–Wolfe algorithm 解説
Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization (2nd ed.). Berlin, New York: Springer-Verlag. ISBN 978-0-387-30303-1 .

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

問題定義

アルゴリズム

性質

解の値の下限と主双対解析

出典

参考文献

外部リンク

関連項目