Frank–Wolfe algorithm: Difference between revisions

Revision as of 10:23, 15 November 2005

Revision as of 00:10, 22 January 2006

Line 15:

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> \mathbfbar{xx_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>).

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.

Line 24:

''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.

To be added.

==ReferenceReferences==

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

*[http://swutc.tamu.edu/Reports/472840-00074-1.pdf/ Lee and Machemehl: Combined traffic signal control and traffic assignment, Technical Report, March 2005]

[[Category:Optimization algorithms]]