フランク・ウルフのアルゴリズム (英 : Frank–Wolfe algorithm ) とは、条件 （英語版 ） 凸最適化 問題を反復 的一次最適化 により解くアルゴリズム である。条件付き勾配法 (conditional gradient method )、[ 1] 簡約勾配法 (reduced gradient algorithm )、 凸結合法 (convex combination algorithm ) とも呼ばれ、1956年にマルグリート・フランク （英語版 ） フィリップ・ウルフ （英語版 ） [ 2] 定義域 を同じくする）線形関数 を最適化する方向へと移動する。
D
{\displaystyle {\mathcal {D}}}
ベクトル空間 上のコンパクト な凸 集合とし、
f
:
D
→
R
{\displaystyle f\colon {\mathcal {D}}\to \mathbb {R} }
微分可能 な凸 実関数 とする。フランク・ウルフのアルゴリズムは、以下の最適化問題 を解く。
Minimize
f
(
x
)
{\displaystyle f(\mathbf {x} )}
subject to
x
∈
D
{\displaystyle \mathbf {x} \in {\mathcal {D}}}
フランク・ウルフのアルゴリズムの1ステップ 初期化:
k
←
0
{\displaystyle k\leftarrow 0}
x
0
{\displaystyle \mathbf {x} _{0}\!}
D
{\displaystyle {\mathcal {D}}}
ステップ 1. 降下方向の決定: 次の条件を満たす
s
k
{\displaystyle \mathbf {s} _{k}}
Minimize
s
T
∇
f
(
x
k
)
{\displaystyle \mathbf {s} ^{T}\nabla f(\mathbf {x} _{k})}
Subject to
s
∈
D
{\displaystyle \mathbf {s} \in {\mathcal {D}}}
（この部分問題は、
f
{\displaystyle f}
x
k
{\displaystyle \mathbf {x} _{k}\!}
テイラー近似 して得られる線形関数を最小化するものと捉えることができる。） ステップ 2. ステップサイズの決定:
α
←
2
k
+
2
{\displaystyle \alpha \leftarrow {\frac {2}{k+2}}}
0
≤
α
≤
1
{\displaystyle 0\leq \alpha \leq 1}
f
(
x
k
+
α
(
s
k
−
x
k
)
)
{\displaystyle f(\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k}))}
α を算出する。ステップ 3. 更新:
x
k
+
1
←
x
k
+
α
(
s
k
−
x
k
)
{\displaystyle \mathbf {x} _{k+1}\leftarrow \mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k})}
k
←
k
+
1
{\displaystyle k\leftarrow k+1}
たとえば最急降下法 など、他の条件付き最適化問題の解法においては各反復毎に許容範囲を射影 する必要があるのに対し、フランク・ウルフのアルゴリズムは全ての反復で同一の範囲について部分問題を解けば、解は自動的に許容範囲に収まる。
フランク・ウルフのアルゴリズムの収束性は一般には劣線形である。勾配がなんらかのノルム についてリプシッツ連続 であれば、k 回の反復の後の目的関数の値と最適値との誤差は
O
(
1
/
k
)
{\displaystyle O(1/k)}
[ 3]
本アルゴリズムの各反復は、つねに許容範囲の極点 の疎凸結合 で表現することができる。このため、機械学習 や信号処理 [ 4] 最小コストフロー 問題などの輸送ネットワーク （英語版 ） [ 5] 貪欲法 アルゴリズムを応用することができる。
許容範囲がもし一連の線形拘束条件により与えられている場合、各反復における部分問題は線型計画法 により解くことができる。
一般の問題について最悪収束速度
O
(
1
/
k
)
{\displaystyle O(1/k)}
[ 6]
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} }
f
(
x
∗
)
≥
f
(
x
)
+
(
x
∗
−
x
)
T
∇
f
(
x
)
≥
min
y
∈
D
{
f
(
x
)
+
(
y
−
x
)
T
∇
f
(
x
)
}
=
f
(
x
)
−
x
T
∇
f
(
x
)
+
min
y
∈
D
y
T
∇
f
(
x
)
{\displaystyle {\begin{aligned}f(\mathbf {x} ^{*})&\geq f(\mathbf {x} )+(\mathbf {x} ^{*}-\mathbf {x} )^{T}\nabla f(\mathbf {x} )\\&\geq \min _{\mathbf {y} \in D}\left\{f(\mathbf {x} )+(\mathbf {y} -\mathbf {x} )^{T}\nabla f(\mathbf {x} )\right\}\\&=f(\mathbf {x} )-\mathbf {x} ^{T}\nabla f(\mathbf {x} )+\min _{\mathbf {y} \in D}\mathbf {y} ^{T}\nabla f(\mathbf {x} )\end{aligned}}}
フランク・ウルフのアルゴリズムは、各反復において上式最終項の最適化問題を解くので、降下方向決定部分問題における解
s
k
{\displaystyle \mathbf {s} _{k}}
l
k
{\displaystyle l_{k}}
l
0
=
−
∞
{\displaystyle l_{0}=-\infty }
l
k
:=
max
(
l
k
−
1
,
f
(
x
k
)
+
(
s
k
−
x
k
)
T
∇
f
(
x
k
)
)
{\displaystyle l_{k}:=\max(l_{k-1},f(\mathbf {x} _{k})+(\mathbf {s} _{k}-\mathbf {x} _{k})^{T}\nabla f(\mathbf {x} _{k}))}
このように未知の最適値の下限を知ることができると、終止条件として用いることができるため実用上有用である。また、各反復においてつねに
l
k
≤
f
(
x
∗
)
≤
f
(
x
k
)
{\displaystyle l_{k}\leq f(\mathbf {x} ^{*})\leq f(\mathbf {x} _{k})}
この双対ギャップ （英語版 ）
f
(
x
k
)
{\displaystyle f(\mathbf {x} _{k})}
l
k
{\displaystyle l_{k}}
f
(
x
k
)
−
l
k
=
O
(
1
/
k
)
{\displaystyle f(\mathbf {x} _{k})-l_{k}=O(1/k)}
^ Levitin, E. S.; Polyak, B. T. (1966). “Constrained minimization methods”. USSR Computational Mathematics and Mathematical Physics 6 (5): 1. doi :10.1016/0041-5553(66)90114-5 . ^ Frank, M.; Wolfe, P. (1956). “An algorithm for quadratic programming”. Naval Research Logistics Quarterly 3 : 95. doi :10.1002/nav.3800030109 . ^ Dunn, J. C.; Harshbarger, S. (1978). “Conditional gradient algorithms with open loop step size rules”. Journal of Mathematical Analysis and Applications 62 (2): 432. doi :10.1016/0022-247X(78)90137-3 . ^ Clarkson, K. L. (2010). “Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm”. ACM Transactions on Algorithms 6 (4): 1. doi :10.1145/1824777.1824783 . ^ Fukushima, M. (1984). “A modified Frank-Wolfe algorithm for solving the traffic assignment problem”. Transportation Research Part B: Methodological 18 (2): 169–177. doi :10.1016/0191-2615(84)90029-8 . ^ Bertsekas, Dimitri (1999). Nonlinear Programming . Athena Scientific. p. 215. ISBN 1-886529-00-0
