Frank–Wolfe algorithm: Difference between revisions

Revision as of 01:22, 17 January 2007

Revision as of 00:08, 11 February 2007

Line 4:

: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_matrixsemidefinite matrix|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===

Line 23:

===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. 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.{{factFact|date=February 2007}}

==References==