Frank–Wolfe algorithm

The Frank-Wolfe algorithm, also known as the Convex Combination algorithm, is a classic algorithm in Operations Research. It was originally proposed by Marguerite Frank and Phil Wolfe in 1956 as a procedure for solving quadratic programming problems with linear constraints. At each step the objective function is linearized and then a step is take in a direction that reduces the objective while maintaining feasibility. The algorithm can be seen as a generalization of the primal Simplex Algorithm for Linear Programming. In recent years it has been widely used for determining the equilibrium flows in transportation networks.

Problem statement

Minimize ${\displaystyle f(\mathbf {x} )={\frac {1}{2}}\mathbf {x} ^{\mathrm {T} }E\mathbf {x} +\mathbf {h} ^{\mathrm {T} }\mathbf {x} }$

subject to ${\displaystyle \mathbf {x} \epsilon \mathbf {P} }$.

Where the n×n matrix E is positive semidefinite, h is an n×1 vector, and ${\displaystyle \mathbf {P} }$ represents a feasible region defined by a mix of linear inequality and equality constraints (for example Ax ≤ b, Cx = d).

Algorithm

Step 1. Initialization. Let ${\displaystyle k\leftarrow 0}$ and let ${\displaystyle x_{0}}$ be any point in ${\displaystyle \mathbf {P} }$.

Step 2. Convergence test. If ${\displaystyle \nabla f(x_{k})=0}$ then Stop, we have found the minimum.

Step 3. Direction-finding subproblem. Solve for ${\displaystyle {\bar {x_{k}}}}$

Minimize ${\displaystyle \nabla ^{T}f(x_{k}){\bar {x_{k}}}}$

Subject to to ${\displaystyle \mathbf {x} \epsilon \mathbf {P} }$

(note that this is a Linear Program).

Step 4. Step size determination. Find ${\displaystyle \lambda }$ that minimizes ${\displaystyle f(x_{k}+\lambda ({\bar {x_{k}}}-x_{k}))}$ subject to ${\displaystyle 0\leq \lambda \leq 1}$ . If ${\displaystyle \lambda =0}$ then Stop, we have found the minimum.

Step 5. Update. Let ${\displaystyle x_{k+1}\leftarrow x_{k}+\lambda ({\bar {x_{k}}}-x_{k})}$, let ${\displaystyle k\leftarrow k+1}$ and go back to Step 2.

Comments

To be added.

References

M. Frank and P. Wolfe, An algorithm for quadratic programming, Naval Research Logistics Quarterly, 3 (1956), pp. 95--110.