Frank–Wolfe algorithm: Difference between revisions

Revision as of 05:58, 24 January 2011

Revision as of 05:59, 24 January 2011

Line 19:

:(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>\nabla f(x_k)^T(\bar{x}_k-x_k) \ge 0 \!</math> then Stop, we have found the minimum in <math> x_k\!<\/math>.

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