フランク・ウルフのアルゴリズム
フランク・ウルフのアルゴリズム (英: Frank–Wolfe algorithm) とは、条件付き凸最適化問題を反復的一次最適化により解くアルゴリズム である。条件付き勾配法 (conditional gradient method)、[1] 簡約勾配法 (reduced gradient algorithm)、 凸結合法 (convex combination algorithm) とも呼ばれ、1956年にマルグリート・フランクおよびフィリップ・ウルフにより提案された[2]。このアルゴリズムでは、各反復毎に目的関数の線形近似を行い、この(定義域を同じくする)線形関数を最適化する方向へと移動する。
問題定義
一般 | |
---|---|
微分可能 |
凸最小化 | |||||||
---|---|---|---|---|---|---|---|
線形 および 二次 |
|
系列範例 (Paradigms) | |||||
---|---|---|---|---|---|
グラフ理論 |
| ||||
ネットワークフロー (最大流問題) |