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

フランク・ウルフのアルゴリズム () とは、付き凸最適化問題を反復的一次最適化により解くアルゴリズムである。条件付き勾配法 ()、簡約勾配法 ()、凸結合法 () とも呼ばれ、1956年におよびにより提案された。このアルゴリズムでは、各反復毎に目的関数の線形近似を行い、この（定義域を同じくする）線形関数を最適化する方向へと移動する。

問題定義をベクトル空間上のコンパクトな凸集合とし、を微分可能な凸実関数とする。フランク・ウルフのアルゴリズムは、以下の最適化問題を解く。

Minimize subject to .

アルゴリズムサムネイル|フランク・ウルフのアルゴリズムの1ステップ

初期化: とし、をに含まれる任意の点とする。

ステップ 1. 降下方向の決定: 次の条件を満たすを解く。 Minimize Subject to （この部分問題は、を近傍で1次までテイラー近似して得られる線形関数を最小化するものと捉えることができる。）ステップ 2. ステップサイズの決定: とする。もしくは、を満す範囲内で、を最小化するようなを算出する。ステップ 3. 更新: とし、とした上でステップ 1. に戻る。

性質たとえば最急降下法など、他の条件付き最適化問題の解法においては各反復毎に許容範囲を射影する必要があるのに対し、フランク・ウルフのアルゴリズムは全ての反復で同一の範囲について部分問題を解けば、解は自動的に許容範囲に収まる。

フランク・ウルフのアルゴリズムの収束性は一般には劣線形である。勾配がなんらかのノルムについてリプシッツ連続であれば、k 回の反復の後の目的関数の値と最適値との誤差はとなる。部分問題を近似的に解いた場合でも同様の収束速度を実現することが示されている。

本アルゴリズムの各反復は、つねに許容範囲の極点の疎凸結合で表現することができる。このため、機械学習や信号処理および、例えば最小コストフロー問題などのによく用いられる疎貪欲法アルゴリズムを応用することができる。

許容範囲がもし一連の線形拘束条件により与えられている場合、各反復における部分問題は線型計画法により解くことができる。

一般の問題について最悪収束速度を改善することは不可能であるが、たとえば強凸問題など特定の種類の問題について、より早い収束速度を得ることはできる。

解の値の下限と主双対解析は凸関数であるから、任意の二点に対し次の不等式が成立する。

この不等式は（未知の）最適解ある点について、最適な下限は次のように与えられる。

フランク・ウルフのアルゴリズムは、各反復において上式最終項の最適化問題を解くので、降下方向決定部分問題における解を用いて解の下限を徐々に更新していくことができる。すなわち、とおくと次のように更新すればよい。

このように未知の最適値の下限を知ることができると、終止条件として用いることができるため実用上有用である。また、各反復においてつねにが成立するため、近似の精度を効率的にみつもることができる。

この双対ギャップ、すなわちととの差も同一の収束速度で減少すること、つまりが成立することが知られている。

脚注

参考文献（概要論文） The Frank–Wolfe algorithm 解説 . Gábor Braun, Alejandro Carderera, Cyrille W. Combettes, Hamed Hassani, Amin Karbasi, Aryan Mokhtari, and Sebastian Pokutta: Conditional Gradient Methods: From Core Principles to AI Applications, SIAM, ISBN 978-1-61197-855-1 (2025).

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

Źródło i licencja