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

フランク・ウルフアルゴリズムは、制約付き凸最適化のための反復的な 一次 最適化 アルゴリズムです。条件付き勾配法、^[1]、縮小勾配アルゴリズム、凸結合アルゴリズムとしても知られるこの方法は、1956年にマーガレット・フランクとフィリップ・ウルフによって最初に提案されました。 ^[2]各反復において、フランク・ウルフアルゴリズムは目的関数の線形近似を考慮し、この線形関数の最小値（同じドメインで取得）に向かって進みます。

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

最小化${\displaystyle f(\mathbf {x} )}$

の対象となります。${\displaystyle \mathbf {x} \in {\mathcal {D}}}$

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

ステップ1. 方向探索サブ問題:解決方法 を見つける${\displaystyle \mathbf {s} _{k}}$

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

対象となる${\displaystyle \mathbf {s} \in {\mathcal {D}}}$

(解釈:内に留まるという制約の下で、 の周りの1 次テイラー近似によって与えられた問題の線形近似を最小化します。)${\displaystyle f}$${\displaystyle \mathbf {x} _{k}\!}$${\displaystyle {\mathcal {D}}}$

ステップ 2. ステップ サイズの決定:を設定するか、 の条件でが最小化されることを見つけます。${\displaystyle \alpha \leftarrow {\frac {2}{k+2}}}$${\displaystyle \alpha}$${\displaystyle f(\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k}))}$${\displaystyle 0\leq \alpha \leq 1}$

ステップ 3. 更新:、 を放して、ステップ 1 に戻ります。${\displaystyle \mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k})}$${\displaystyle k\leftarrow k+1}$

制約付き最適化のための勾配降下法などの競合方法では、各反復で実行可能セットへの投影ステップが必要ですが、Frank-Wolfe アルゴリズムでは、各反復で同じセット上の凸問題の解決のみが必要であり、自動的に実行可能セット内にとどまります。

フランク・ウルフ法の収束は一般に線形以下である。つまり、勾配が何らかのノルムに関してリプシッツ連続である限り、目的関数の最適値への誤差はk回の反復後にはゼロになる。部分問題が近似的に解かれる場合でも、同じ収束率を示すことができる。^[3]${\displaystyle O(1/k)}$

このアルゴリズムの反復は、常に実行可能集合の極値点のスパース凸結合として表現することができ、機械学習や信号処理問題におけるスパース貪欲最適化アルゴリズムの人気に貢献している^[4]ほか、例えば交通ネットワークにおける最小コストフローの最適化にも利用されている^[5]。

実行可能集合が線形制約の集合によって与えられる場合、各反復で解決されるサブ問題は線形計画法になります。

最悪の場合の収束率は一般に改善できないが、一部の強凸問題などの特殊な問題クラスではより速い収束が得られる。^[6]${\displaystyle O(1/k)}$

は凸なので、任意の 2 点に対して次の式が成り立ちます。 ${\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 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). 「Frank–Wolfe の再考: 射影のないスパース凸最適化」。機械学習研究ジャーナル: ワークショップおよび会議議事録。28 ( 1): 427–435。（概要論文）
• フランク・ウルフアルゴリズムの説明
• Nocedal, Jorge; Wright, Stephen J. (2006).数値最適化(第 2 版). ベルリン、ニューヨーク: Springer-Verlag . ISBN 978-0-387-30303-1。。

• https://conditional-gradients.org/: Frank–Wolfe アルゴリズムの調査。
• アルゴリズムの歴史について個人的な説明をするマーガレット・フランク

• 近位勾配法