Frank–Wolfe algorithm

Suppose $\backslash mathcal\{D\}$ is a compact convex set in a vector space and $f\; \backslash colon\; \backslash mathcal\{D\}\; \backslash to\; \backslash mathbb\{R\}$ is a convex, differentiable real-valued function. The Frank–Wolfe algorithm solves the optimization problem

:Minimize $f(\backslash mathbf\{x\})$

:subject to $\backslash mathbf\{x\}\; \backslash in\; \backslash mathcal\{D\}$.

File:Frank-Wolfe Algorithm.png

:Initialization: Let $k\; \backslash leftarrow\; 0$, and let $\backslash mathbf\{x\}\_0\; \backslash !$ be any point in $\backslash mathcal\{D\}$.

:Step 1. Direction-finding subproblem: Find $\backslash mathbf\{s\}\_k$ solving

::Minimize $\backslash mathbf\{s\}^T\; \backslash nabla\; f(\backslash mathbf\{x\}\_k)$

::Subject to $\backslash mathbf\{s\}\; \backslash in\; \backslash mathcal\{D\}$

:(Interpretation: Minimize the linear approximation of the problem given by the first-order Taylor approximation of $f$ around $\backslash mathbf\{x\}\_k\; \backslash !$ constrained to stay within $\backslash mathcal\{D\}$.)

:Step 2. Step size determination: Set $\backslash alpha\; \backslash leftarrow\; \backslash frac\{2\}\{k+2\}$, or alternatively find $\backslash alpha$ that minimizes $f(\backslash mathbf\{x\}\_k+\backslash alpha(\backslash mathbf\{s\}\_k\; -\backslash mathbf\{x\}\_k))$ subject to $0\; \backslash le\; \backslash alpha\; \backslash le\; 1$ .

:Step 3. Update: Let $\backslash mathbf\{x\}\_\{k+1\}\backslash leftarrow\; \backslash mathbf\{x\}\_k+\backslash alpha(\backslash mathbf\{s\}\_k-\backslash mathbf\{x\}\_k)$, let $k\; \backslash leftarrow\; k+1$ and go to Step 1.

While competing methods such as gradient descent for constrained optimization require a projection step 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.

The convergence of the Frank–Wolfe algorithm is sublinear in general: the error in the objective function to the optimum is $O(1/k)$ after k iterations, so long as the gradient is Lipschitz continuous with respect to some norm. The same convergence rate can also be shown if the sub-problems are only solved approximately.{{Cite journal | last1 = Dunn | first1 = J. C. | last2 = Harshbarger | first2 = S. | doi = 10.1016/0022-247X(78)90137-3 | title = Conditional gradient algorithms with open loop step size rules | journal = Journal of Mathematical Analysis and Applications | volume = 62 | issue = 2 | pages = 432 | year = 1978 | doi-access = free }}

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 machine learning and signal processing problems,{{Cite journal | last1 = Clarkson | first1 = K. L. | title = Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm | doi = 10.1145/1824777.1824783 | journal = ACM Transactions on Algorithms | volume = 6 | issue = 4 | pages = 1–30 | year = 2010 | citeseerx = 10.1.1.145.9299 }} as well as for example the optimization of minimum–cost flows in transportation networks.{{Cite journal | last1 = Fukushima | first1 = M. | title = A modified Frank-Wolfe algorithm for solving the traffic assignment problem | doi = 10.1016/0191-2615(84)90029-8 | journal = Transportation Research Part B: Methodological | volume = 18 | issue = 2 | pages = 169–177| year = 1984 }}

If the feasible set is given by a set of linear constraints, then the subproblem to be solved in each iteration becomes a linear program.

While the worst-case convergence rate with $O(1/k)$ can not be improved in general, faster convergence can be obtained for special problem classes, such as some strongly convex problems.{{Cite book|title=Nonlinear Programming|first= Dimitri |last=Bertsekas|year= 1999|page= 215|publisher= Athena Scientific| isbn =978-1-886529-00-7}}

Since $f$ is convex, for any two points $\backslash mathbf\{x\},\; \backslash mathbf\{y\}\; \backslash in\; \backslash mathcal\{D\}$ we have:

:$$

f(\mathbf{y}) \geq f(\mathbf{x}) + (\mathbf{y} - \mathbf{x})^T \nabla f(\mathbf{x})

This also holds for the (unknown) optimal solution $\backslash mathbf\{x\}^*$. That is, $f(\backslash mathbf\{x\}^*)\; \backslash ge\; f(\backslash mathbf\{x\})\; +\; (\backslash mathbf\{x\}^*\; -\; \backslash mathbf\{x\})^T\; \backslash nabla\; f(\backslash mathbf\{x\})$. The best lower bound with respect to a given point $\backslash mathbf\{x\}$ is given by

:$$

\begin{align}

f(\mathbf{x}^*)

& \ge 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{align}

The latter optimization problem is solved in every iteration of the Frank–Wolfe algorithm, therefore the solution $\backslash mathbf\{s\}\_k$ of the direction-finding subproblem of the $k$-th iteration can be used to determine increasing lower bounds $l\_k$ during each iteration by setting $l\_0\; =\; -\; \backslash infty$ and

:$$

l_k := \max (l_{k - 1}, f(\mathbf{x}_k) + (\mathbf{s}_k - \mathbf{x}_k)^T \nabla f(\mathbf{x}_k))

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\; \backslash leq\; f(\backslash mathbf\{x\}^*)\; \backslash leq\; f(\backslash mathbf\{x\}\_k)$.

It has been shown that this corresponding duality gap, that is the difference between $f(\backslash mathbf\{x\}\_k)$ and the lower bound $l\_k$, decreases with the same convergence rate, i.e.

f(\mathbf{x}_k) - l_k = O(1/k) .

{{Reflist}}

• {{cite journal|last=Jaggi|first=Martin|title=Revisiting Frank–Wolfe: Projection-Free Sparse Convex Optimization|journal=Journal of Machine Learning Research: Workshop and Conference Proceedings |volume=28|issue=1|pages=427–435|year= 2013 |url=http://jmlr.csail.mit.edu/proceedings/papers/v28/jaggi13.html}} (Overview paper)
• [http://www.math.chalmers.se/Math/Grundutb/CTH/tma946/0203/fw_eng.pdf The Frank–Wolfe algorithm] description
• {{Cite book | last1=Nocedal | first1=Jorge | last2=Wright | first2=Stephen J. | title=Numerical Optimization | publisher=Springer-Verlag | location=Berlin, New York | edition=2nd | isbn=978-0-387-30303-1 | year=2006 }}.

• https://conditional-gradients.org/: a survey of Frank–Wolfe algorithms.
• [https://www.youtube.com/watch?v=24e08AX9Eww Marguerite Frank giving a personal account of the history of the algorithm]

• Proximal gradient methods

{{Optimization algorithms|convex}}

{{DEFAULTSORT:Frank-Wolfe algorithm}}

Category:Optimization algorithms and methods

Category:Iterative methods

Category:First order methods

Category:Gradient methods