Frank–Wolfe algorithm: Difference between revisions

Revision as of 10:48, 15 January 2007

Revision as of 00:13, 16 January 2007

Line 13:

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_kx}_k</math>:

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

:Subject to <math>\bar{x_kx}_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_kx}_k</math> and is equivalent to minimization of <math>\nabla^T f(x_k) \bar{x_kx}_k</math>).

Step 4. Step size determination. Find <math>\lambda</math> that minimizes <math> f(x_k+\lambda(\bar{x_kx}_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_kx}_k-x_k)</math>, let <math>k \leftarrow k+1</math> and go back to Step 2.

''Comments''