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

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

問題定義

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

Minimize ${\displaystyle f(\mathbf {x} )}$

subject to ${\displaystyle \mathbf {x} \in {\mathcal {D}}}$.

アルゴリズム

初期化:  ${\displaystyle k\leftarrow 0}$ とし、${\displaystyle \mathbf {x} _{0}\!}$ を ${\displaystyle {\mathcal {D}}}$ に含まれる任意の点とする。

ステップ 1. 降下方向の決定: 次の条件を満たす ${\displaystyle \mathbf {s} _{k}}$ を解く。

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

Subject to ${\displaystyle \mathbf {s} \in {\mathcal {D}}}$

（この部分問題は、${\displaystyle f}$ を ${\displaystyle \mathbf {x} _{k}\!}$ 近傍で1次までテイラー近似して得られる線形関数を最小化するものと捉えることができる。）

ステップ 2. ステップサイズの決定: ${\displaystyle \alpha \leftarrow {\frac {2}{k+2}}}$ とする。もしくは、 ${\displaystyle 0\leq \alpha \leq 1}$ を満す範囲内で、 ${\displaystyle f(\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k}))}$ を最小化するような α を算出する。

ステップ 3. 更新: ${\displaystyle \mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k})}$ とし、 ${\displaystyle k\leftarrow k+1}$ とした上でステップ 1. に戻る。

性質

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

出典

参考文献

• Jaggi, Martin (2013). “Revisiting Frank–Wolfe: Projection-Free Sparse Convex Optimization”. Journal of Machine Learning Research: Workshop and Conference Proceedings 28 (1): 427–435. http://jmlr.csail.mit.edu/proceedings/papers/v28/jaggi13.html.  （概要論文）
• 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 .

外部リンク

• Marguerite Frank giving a personal account of the history of the algorithm
• "Some comments on Wilfe's away step", Mathematical Programming, vol.35 (1986),pp.110-119.
• "Pairwise Away Steps for the Frank-Wolfe Algorithm".

関連項目

• 近接勾配法（英語版）

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形(無制約)	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP法 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） ドッグレッグ法 … ヘッセ行列 最適化におけるニュートン法（英語版）
非線形(制約付き)	一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）
凸最適化	凸縮小化 切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および 二次 内点法 カチヤンの楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂単体法（英語版） 十文字法（英語版） レムケの主ピボット操作法（英語版）
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 分枝カット法) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）
メタヒューリスティクス	進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ ベイスンホッピング法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）