フランク・ウルフのアルゴリズム
f ( x ∗ ) ≥ f ( x ) + ( x ∗ − x ) T ∇ f ( x ) ≥ min y ∈ D { f ( x ) + ( y − x ) T ∇ f ( x ) } = f ( x ) − x T ∇ f ( x ) + min y ∈ D y T ∇ f ( 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}}}
フランク・ウルフのアルゴリズムは、各反復において上式最終項の最適化問題を解くので、降下方向決定部分問題における解 s k {\displaystyle \mathbf {s} _{k}} を用いて解の下限 l k {\displaystyle l_{k}} を徐々に更新していくことができる。すなわち、 l 0 = − ∞ {\displaystyle l_{0}=-\infty } とおくと次のように更新すればよい。