Content deleted Content added
m The bar should be centered over the x (typesetting improvement) |
pure editing stuff (sections, bold,...) |
||
Line 1:
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 taken 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.
: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).
'''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. The approximation of the problem that is obtained by replacing the function f with its first-order Taylor expansion around <math>x_k</math> is found. Solve for <math>\bar{x}_k</math>:
:Minimize <math>f(x_k) + \nabla^T f(x_k) \bar{x}_k</math>
:Subject to <math>\bar{x}_k \epsilon \mathbf{P}</math>
:(note that this is a Linear Program. <math>x_k</math> is fixed during Step 3, while the minimization takes place by varying <math>\bar{x}_k</math> and is equivalent to minimization of <math>\nabla^T f(x_k) \bar{x}_k</math>).
'''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.
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. It can be shown that the worst case convergence rate is sublinear; however, in practice the convergence rate has been observed to improve in case of many constraints.{{fact}}
==References==
Line 30 ⟶ 29:
*M. Frank and P. Wolfe, ''An algorithm for quadratic programming'', Naval Research Logistics Quarterly, 3 (1956), pp. 95--110.
*[http://www.math.chalmers.se/Math/Grundutb/CTH/tma946/0203/fw_eng.pdf The Frank-Wolfe algorithm] description
*[http://swutc.tamu.edu/Reports/472840-00074-1.pdf/ Lee and Machemehl: Combined traffic signal control and traffic assignment, Technical Report, March 2005]
| |||