Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Frank–Wolfe algorithm
open-in-new
<h2 id="problem-statement">Problem statement</h2> <p>Suppose D {\displaystyle {\mathcal {D}}} is a <a href="/facts/Compact_space/d0cgXJH7">compact</a> <a href="/facts/Convex_set/vdAuJRJl">convex set</a> in a <a href="/facts/Vector_space/M1pxMLx2">vector space</a> and f : D → R {\displaystyle f\colon {\mathcal {D}}\to \mathbb {R} } is a <a href="/facts/Convex_function/IbzG5SLF">convex</a>, <a href="/facts/Differentiable_function/jQqTgLk1">differentiable</a> <a href="/facts/Real-valued_function/jetqlJpK">real-valued function</a>. The Frank–Wolfe algorithm solves the <a href="/facts/Optimization_problem/QzwJfFEE">optimization problem</a> </p> Minimize f ( x ) {\displaystyle f(\mathbf {x} )} subject to x ∈ D {\displaystyle \mathbf {x} \in {\mathcal {D}}} . <h2 id="algorithm">Algorithm</h2> <i>Initialization:</i> Let k ← 0 {\displaystyle k\leftarrow 0} , and let x 0 {\displaystyle \mathbf {x} _{0}\!} be any point in D {\displaystyle {\mathcal {D}}} . Step 1. <i>Direction-finding subproblem:</i> Find s k {\displaystyle \mathbf {s} _{k}} solving 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}}} <i>(Interpretation: Minimize the linear approximation of the problem given by the first-order <a href="/facts/Taylor_series/M0aTuftH">Taylor approximation</a> of f {\displaystyle f} around x k {\displaystyle \mathbf {x} _{k}\!} constrained to stay within D {\displaystyle {\mathcal {D}}} .)</i> Step 2. <i>Step size determination:</i> Set α ← 2 k + 2 {\displaystyle \alpha \leftarrow {\frac {2}{k+2}}} , or alternatively find α {\displaystyle \alpha } that minimizes f ( x k + α ( s k − x k ) ) {\displaystyle f(\mathbf {x} _{k}+\alpha (\mathbf {s} _{k}-\mathbf {x} _{k}))} subject to 0 ≤ α ≤ 1 {\displaystyle 0\leq \alpha \leq 1} . Step 3. <i>Update:</i> Let 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})} , let k ← k + 1 {\displaystyle k\leftarrow k+1} and go to Step 1. <h2 id="properties">Properties</h2> <p>While competing methods such as <a href="/facts/Gradient_descent/pFFrek0F">gradient descent</a> for constrained optimization require a <a href="/facts/Projection_(mathematics)/QxxC9XTp">projection step</a> back to the feasible set in each iteration, the Frank–Wolfe algorithm only needs the solution of a convex problem over the same set in each iteration, and automatically stays in the feasible set. </p><p>The convergence of the Frank–Wolfe algorithm is sublinear in general: the error in the objective function to the optimum is O ( 1 / k ) {\displaystyle O(1/k)} after <i>k</i> iterations, so long as the gradient is <a href="/facts/Lipschitz_continuity/Hw20EPEU">Lipschitz continuous</a> with respect to some norm. The same convergence rate can also be shown if the sub-problems are only solved approximately.<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a> </p><p>The iterations of the algorithm can always be represented as a sparse convex combination of the extreme points of the feasible set, which has helped to the popularity of the algorithm for sparse greedy optimization in <a href="/facts/Machine_learning/e0w0XJTu">machine learning</a> and <a href="/facts/Signal_processing/Npaja6zb">signal processing</a> problems,<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> as well as for example the optimization of <a href="/facts/Flow_network/k0LCoRwD">minimum–cost flows</a> in <a href="/facts/Transport_network/xtFgRh60">transportation networks</a>.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> </p><p>If the feasible set is given by a set of linear constraints, then the subproblem to be solved in each iteration becomes a <a href="/facts/Linear_programming/GduXFQxT">linear program</a>. </p><p>While the worst-case convergence rate with O ( 1 / k ) {\displaystyle O(1/k)} can not be improved in general, faster convergence can be obtained for special problem classes, such as some strongly convex problems.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> </p> <h2 id="lower-bounds-on-the-solution-value-and-primal-dual-analysis">Lower bounds on the solution value, and primal-dual analysis</h2> <p>Since f {\displaystyle f} is <a href="/facts/Convex_function/IbzG5SLF">convex</a>, for any two points x , y ∈ D {\displaystyle \mathbf {x} ,\mathbf {y} \in {\mathcal {D}}} we have: </p> 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} )} <p>This also holds for the (unknown) optimal solution x ∗ {\displaystyle \mathbf {x} ^{*}} . That is, 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} )} . The best lower bound with respect to a given point x {\displaystyle \mathbf {x} } is given by </p> 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}}} <p>The latter optimization problem is solved in every iteration of the Frank–Wolfe algorithm, therefore the solution s k {\displaystyle \mathbf {s} _{k}} of the direction-finding subproblem of the k {\displaystyle k} -th iteration can be used to determine increasing lower bounds l k {\displaystyle l_{k}} during each iteration by setting l 0 = − ∞ {\displaystyle l_{0}=-\infty } and </p> 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}))} <p>Such lower bounds on the unknown optimal value are important in practice because they can be used as a stopping criterion, and give an efficient certificate of the approximation quality in every iteration, since always l k ≤ f ( x ∗ ) ≤ f ( x k ) {\displaystyle l_{k}\leq f(\mathbf {x} ^{*})\leq f(\mathbf {x} _{k})} . </p><p>It has been shown that this corresponding <a href="/facts/Duality_gap/xwCQ15DL">duality gap</a>, that is the difference between f ( x k ) {\displaystyle f(\mathbf {x} _{k})} and the lower bound l k {\displaystyle l_{k}} , decreases with the same convergence rate, i.e. f ( x k ) − l k = O ( 1 / k ) . {\displaystyle f(\mathbf {x} _{k})-l_{k}=O(1/k).} </p> <h2 id="notes">Notes</h2> <h2 id="bibliography">Bibliography</h2> <ul><li>Jaggi, Martin (2013). <a href="http://jmlr.csail.mit.edu/proceedings/papers/v28/jaggi13.html">"Revisiting Frank–Wolfe: Projection-Free Sparse Convex Optimization"</a>. <i>Journal of Machine Learning Research: Workshop and Conference Proceedings</i>. 28 (1): 427–435. (Overview paper)</li> <li><a href="http://www.math.chalmers.se/Math/Grundutb/CTH/tma946/0203/fw_eng.pdf">The Frank–Wolfe algorithm</a> description</li> <li>Nocedal, Jorge; Wright, Stephen J. (2006). <i>Numerical Optimization</i> (2nd ed.). Berlin, New York: <a href="/facts/Springer-Verlag/nAesf6nT">Springer-Verlag</a>. <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-387-30303-1..</li></ul> <h2 id="external-links">External links</h2> <ul><li><a href="https://conditional-gradients.org/">https://conditional-gradients.org/</a>: a survey of Frank–Wolfe algorithms.</li> <li><a href="https://www.youtube.com/watch?v=24e08AX9Eww">Marguerite Frank giving a personal account of the history of the algorithm</a></li></ul> <h2 id="see-also">See also</h2> <ul><li><a href="/facts/Proximal_gradient_methods/XgT8Mkvu">Proximal gradient methods</a></li></ul> <h2 id="references">References</h2> <ol> <li id="fn:1"><p>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. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li> <li id="fn:2"><p>Frank, M.; Wolfe, P. (1956). "An algorithm for quadratic programming". Naval Research Logistics Quarterly. 3 (1–2): 95–110. doi:10.1002/nav.3800030109. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li> <li id="fn:3"><p>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. <a href="https://doi.org/10.1016%2F0022-247X%2878%2990137-3" target="_blank">https://doi.org/10.1016%2F0022-247X%2878%2990137-3</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li> <li id="fn:4"><p>Clarkson, K. L. (2010). "Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm". ACM Transactions on Algorithms. 6 (4): 1–30. CiteSeerX 10.1.1.145.9299. doi:10.1145/1824777.1824783. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li> <li id="fn:5"><p>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. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li> <li id="fn:6"><p>Bertsekas, Dimitri (1999). Nonlinear Programming. Athena Scientific. p. 215. ISBN 978-1-886529-00-7. <a href="978-1-886529-00-7" target="_blank">978-1-886529-00-7</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li> </ol>