フランク・ウルフのアルゴリズム
f {\displaystyle f} は凸関数であるから、任意の二点 x , y ∈ D {\displaystyle \mathbf {x} ,\mathbf {y} \in {\mathcal {D}}} に対し次の不等式が成立する。
f ( y ) ≥ f ( x ) + ( y − x ) T ∇ f ( x ) {\displaystyle f(\mathbf {y} )\geq f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )}
この不等式は(未知の)最適解 x ∗ {\displaystyle \mathbf {x} ^{*}} f ( x ∗ ) ≥ f ( x ) + ( x ∗ − x ) T ∇ f ( x ) {\displaystyle f(\mathbf {x} ^{*})\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )} ある点 x {\displaystyle \mathbf {x} } について、最適な下限は次のように与えられる。
フランク・ウルフのアルゴリズム (英: Frank–Wolfe algorithm) とは、条件(英語版)付き凸最適化問題を反復的一次最適化により解くアルゴリズム である。条件付き勾配法 (conditional gradient method)、 簡約勾配法 (reduced gradient algorithm)、 凸結合法 (convex combination algorithm) とも呼ばれ、1956年にマルグリート・フランク(英語版)およびフィリップ・ウルフ(英語版)により提案された。このアルゴリズムでは、各反復毎に目的関数の線形近似を行い、この(定義域を同じくする)線形関数を最適化する方向へと移動する。