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