フランク・ウルフのアルゴリズム
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)} が成立することが知られている。