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

フランク・ウルフのアルゴリズム () とは、付き凸最適化問題を反復的一次最適化により解くアルゴリズム である。条件付き勾配法 ()、 簡約勾配法 ()、 凸結合法 () とも呼ばれ、1956年におよびにより提案された。このアルゴリズムでは、各反復毎に目的関数の線形近似を行い、この（定義域を同じくする）線形関数を最適化する方向へと移動する。
問題定義.
formula_1 をベクトル空間上のコンパクトな凸集合とし、formula_2 を微分可能な凸実関数とする。フランク・ウルフのアルゴリズムは、以下の最適化問題を解く。
性質.
たとえば最急降下法など、他の条件付き最適化問題の解法においては各反復毎に許容範囲を射影する必要があるのに対し、フランク・ウルフのアルゴリズムは全ての反復で同一の範囲について部分問題を解けば、解は自動的に許容範囲に収まる。
フランク・ウルフのアルゴリズムの収束性は一般には劣線形である。勾配がなんらかのノルムについてリプシッツ連続であれば、"k" 回の反復の後の目的関数の値と最適値との誤差は formula_18 となる。部分問題を近似的に解いた場合でも同様の収束速度を実現することが示されている。
本アルゴリズムの各反復は、つねに許容範囲の極点の疎凸結合で表現することができる。このため、機械学習や信号処理および、例えば最小コストフロー問題などのによく用いられる疎貪欲法アルゴリズムを応用することができる。
許容範囲がもし一連の線形拘束条件により与えられている場合、各反復における部分問題は線型計画法により解くことができる。
一般の問題について最悪収束速度 formula_18 を改善することは不可能であるが、たとえば強凸問題など特定の種類の問題について、より早い収束速度を得ることはできる。
解の値の下限と主双対解析.
formula_11 は凸関数であるから、任意の二点 formula_21 に対し次の不等式が成立する。
この不等式は（未知の）最適解 formula_23formula_24ある点 formula_25 について、最適な下限は次のように与えられる。
フランク・ウルフのアルゴリズムは、各反復において上式最終項の最適化問題を解くので、降下方向決定部分問題における解 formula_8 を用いて解の下限 formula_28 を徐々に更新していくことができる。すなわち、 formula_29 とおくと次のように更新すればよい。
このように未知の最適値の下限を知ることができると、終止条件として用いることができるため実用上有用である。また、各反復においてつねに formula_31 が成立するため、近似の精度を効率的にみつもることができる。
この、すなわち formula_32 と formula_28 との差も同一の収束速度で減少すること、つまり formula_34 が成立することが知られている。