Frank–Wolfe algorithm: Difference between revisions

Revision as of 20:39, 13 November 2005

Revision as of 18:35, 14 November 2005

Line 1:

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. TheAt methodeach is astep feasiblethe directionobjective methodfunction andis eachlinearized stepand involvesthen a linearizationstep ofis thetake objective function; it ends afterin a finitedirection numberthat of steps whenreduces the Karush-Kuhn-Tuckerobjective conditionswhile aremaintaining satisfiedfeasibility. ItThe algorithm can be seen as a generalization of the primal [[Simplex Algorithm]] for [[Linear Programming]]. ItIn recent years it has been foundwidely especially usefulused for determining the equilibrium flows forin transportation networks.

''Problem statement''

:Minimize <math> f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^{\mathrm{T}} E\mathbf{x} + \mathbf{h}^{\mathrm{T}} \mathbf{x} </math>

:subject to <math> \mathbf{x} \epsilon \mathbf{P}</math>.

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

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

Step 3. Direction-finding subproblem. Solve for <math>\bar{x_k}</math>

:Minimize <math>\nabla^T f(x_k) \bar{x_k}</math>

:Subject to to <math> \mathbf{x} \epsilon \mathbf{P}</math>

(note that this is a Linear Program).

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

Step 5. Update. Let <math>x_{k+1}\leftarrow x_k+\lambda(\bar{x_k}-x_k)</math>, let <math>k \leftarrow k+1</math> 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.

{{Math-stub}}