フランク・ウルフのアルゴリズム
たとえば最急降下法など、他の条件付き最適化問題の解法においては各反復毎に許容範囲を射影する必要があるのに対し、フランク・ウルフのアルゴリズムは全ての反復で同一の範囲について部分問題を解けば、解は自動的に許容範囲に収まる。
フランク・ウルフのアルゴリズムの収束性は一般には劣線形である。勾配がなんらかのノルムについてリプシッツ連続であれば、k 回の反復の後の目的関数の値と最適値との誤差は O ( 1 / k ) {\displaystyle O(1/k)} となる。部分問題を近似的に解いた場合でも同様の収束速度を実現することが示されている。
本アルゴリズムの各反復は、つねに許容範囲の極点の疎凸結合で表現することができる。このため、機械学習や信号処理および、例えば最小コストフロー問題などの輸送ネットワーク(英語版)によく用いられる疎貪欲法アルゴリズムを応用することができる。
許容範囲がもし一連の線形拘束条件により与えられている場合、各反復における部分問題は線型計画法により解くことができる。
一般の問題について最悪収束速度 O ( 1 / k ) {\displaystyle O(1/k)} を改善することは不可能であるが、たとえば強凸問題など特定の種類の問題について、より早い収束速度を得ることはできる。