フランク・ウルフのアルゴリズム
フランク＝ウルフアルゴリズムは、条件付き凸最適化問題を解くための反復的なアルゴリズムです。このアルゴリズムは、目的関数の線形近似を利用して、実行可能な領域内で線形関数を最適化する方向へと反復的に移動します。条件付き勾配法、簡約勾配法、凸結合法とも呼ばれ、1956年にマルグリート・フランクとフィリップ・ウルフによって提案されました。
ベクトル空間上のコンパクトな凸集合 \( \mathcal{D} \) と、微分可能な凸実関数 \( f: \mathcal{D} \rightarrow \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
abla f(\mathbf{x}_k) \)
subject to \( \mathbf{s} \in \mathcal{D} \)
この部分問題は、\( f \) を \( \mathbf{x}_k \) 近傍で一次までテイラー近似して得られる線形関数を最小化するものと解釈できます。
ステップ 2: ステップサイズの決定
\( \alpha \leftarrow \frac{2}{k+2} \) とします。または、\( 0 \leq \alpha \leq 1 \) の範囲内で、\( f(\mathbf{x}_k + \alpha(\mathbf{s}_k - \mathbf{x}_k)) \) を最小化するような \( \alpha \) を算出します。
ステップ 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) \) となります。部分問題を近似的に解いた場合でも、同様の収束速度が得られることが示されています。
このアルゴリズムの各反復は、常に許容範囲の極点の疎な凸結合で表現できます。そのため、機械学習や信号処理、最小コストフロー問題などの輸送ネットワークで利用される疎貪欲法アルゴリズムに応用できます。
許容範囲が線形制約条件で与えられている場合、各反復における部分問題は線形計画法で解くことができます。
一般の問題において、最悪収束速度 \( O(1/k) \) を改善することは不可能ですが、強凸問題など特定の種類の問題に対しては、より速い収束速度を得ることができます。
\( f \) が凸関数であるため、任意の二点 \( \mathbf{x}, \mathbf{y} \in \mathcal{D} \) に対して、以下の不等式が成立します。
\( f(\mathbf{y}) \geq f(\mathbf{x}) + (\mathbf{y} - \mathbf{x})^T
abla f(\mathbf{x}) \)
この不等式から、最適解 \( \mathbf{x}^ \) に対して、次の不等式が導かれます。
\( f(\mathbf{x}^) \geq f(\mathbf{x}) + (\mathbf{x}^ - \mathbf{x})^T
abla f(\mathbf{x}) \)
ある点 \( \mathbf{x} \) における最適な下限は、以下のように与えられます。
\( f(\mathbf{x}^) \geq f(\mathbf{x}) + (\mathbf{x}^ - \mathbf{x})^T
abla f(\mathbf{x}) \geq \min_{\mathbf{y} \in D} \{ f(\mathbf{x}) + (\mathbf{y} - \mathbf{x})^T
abla f(\mathbf{x}) \} = f(\mathbf{x}) - \mathbf{x}^T
abla f(\mathbf{x}) + \min_{\mathbf{y} \in D} \mathbf{y}^T
abla f(\mathbf{x}) \)
フランク＝ウルフアルゴリズムは、各反復で上記最終項の最適化問題を解くため、降下方向決定部分問題の解 \( \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
abla f(\mathbf{x}_k)) \) と更新できます。
このようにして得られる解の下限は、実用的な終了条件として利用できます。また、\( l_k \leq f(\mathbf{x}^) \leq f(\mathbf{x}_k) \) が常に成立するため、近似の精度を効率的に評価できます。双対ギャップ \( 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.
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".
関連項目
近接勾配法
問題定義
ベクトル空間上のコンパクトな凸集合 \( \mathcal{D} \) と、微分可能な凸実関数 \( f: \mathcal{D} \rightarrow \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
abla f(\mathbf{x}_k) \)
subject to \( \mathbf{s} \in \mathcal{D} \)
この部分問題は、\( f \) を \( \mathbf{x}_k \) 近傍で一次までテイラー近似して得られる線形関数を最小化するものと解釈できます。
ステップ 2: ステップサイズの決定
\( \alpha \leftarrow \frac{2}{k+2} \) とします。または、\( 0 \leq \alpha \leq 1 \) の範囲内で、\( f(\mathbf{x}_k + \alpha(\mathbf{s}_k - \mathbf{x}_k)) \) を最小化するような \( \alpha \) を算出します。
ステップ 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) \) となります。部分問題を近似的に解いた場合でも、同様の収束速度が得られることが示されています。
このアルゴリズムの各反復は、常に許容範囲の極点の疎な凸結合で表現できます。そのため、機械学習や信号処理、最小コストフロー問題などの輸送ネットワークで利用される疎貪欲法アルゴリズムに応用できます。
許容範囲が線形制約条件で与えられている場合、各反復における部分問題は線形計画法で解くことができます。
一般の問題において、最悪収束速度 \( O(1/k) \) を改善することは不可能ですが、強凸問題など特定の種類の問題に対しては、より速い収束速度を得ることができます。
解の値の下限と主双対解析
\( f \) が凸関数であるため、任意の二点 \( \mathbf{x}, \mathbf{y} \in \mathcal{D} \) に対して、以下の不等式が成立します。
\( f(\mathbf{y}) \geq f(\mathbf{x}) + (\mathbf{y} - \mathbf{x})^T
abla f(\mathbf{x}) \)
この不等式から、最適解 \( \mathbf{x}^ \) に対して、次の不等式が導かれます。
\( f(\mathbf{x}^) \geq f(\mathbf{x}) + (\mathbf{x}^ - \mathbf{x})^T
abla f(\mathbf{x}) \)
ある点 \( \mathbf{x} \) における最適な下限は、以下のように与えられます。
\( f(\mathbf{x}^) \geq f(\mathbf{x}) + (\mathbf{x}^ - \mathbf{x})^T
abla f(\mathbf{x}) \geq \min_{\mathbf{y} \in D} \{ f(\mathbf{x}) + (\mathbf{y} - \mathbf{x})^T
abla f(\mathbf{x}) \} = f(\mathbf{x}) - \mathbf{x}^T
abla f(\mathbf{x}) + \min_{\mathbf{y} \in D} \mathbf{y}^T
abla f(\mathbf{x}) \)
フランク＝ウルフアルゴリズムは、各反復で上記最終項の最適化問題を解くため、降下方向決定部分問題の解 \( \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
abla f(\mathbf{x}_k)) \) と更新できます。
このようにして得られる解の下限は、実用的な終了条件として利用できます。また、\( l_k \leq f(\mathbf{x}^) \leq f(\mathbf{x}_k) \) が常に成立するため、近似の精度を効率的に評価できます。双対ギャップ \( 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.
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".
関連項目
近接勾配法
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。