Frank–Wolfe algorithm

From Wikipedia, the free encyclopedia

The Frank–Wolfe algorithm, also known as the convex combination algorithm, is a classic algorithm in operations research (OR). 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 $f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^{\mathrm{T}} E\mathbf{x} + \mathbf{h}^{\mathrm{T}} \mathbf{x}$

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

Where the n×n matrix E is positive semidefinite, h is an n×1 vector, and $\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 $k \leftarrow 0$ and let $x 0$ be any point in $\mathbf{P}$ .

Step 2. Convergence test. If $\nabla f(x_k)=0$ then Stop, we have found the minimum.

Step 3. Direction-finding subproblem. Solve for $\bar{x_k}$

Minimize $\nabla^T f(x_k) \bar{x_k}$

Subject to $\bar{x_k} \epsilon \mathbf{P}$

(note that this is a Linear Program. $x k$ is fixed during Step 3, while the minimization takes place by varying $\bar{x_k}$ ).

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

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

Comments

The algorithm generally makes good progress towards the optimum during the first few iterations, but convergence often slows down substantially when close to the minimum point. For this reason the algorithm is perhaps best used to find an approximate solution.