# How to show convergence of Frank-Wolfe algorithm ( or conditional gradient method)?

Let $$g(w)$$ be a differentiable convex function. Frank-Wolfe algorithm over a convex set $$C \in \mathbb{R}^n$$ is defined so as to find the local minimum of the function:

$$s_{t+1}=\arg\min_{s \in C} \langle s, \nabla g(w_t) \rangle \tag{1}$$ $$w_{t+1} = (1-\eta_t)w_{t}+\eta_ts_t \tag{2}$$

where $$\eta_t$$ is the step size and is in $$[0,1]$$ and $$t=1,2,\cdots,T$$.

The intuition behind the the first step of Frank-Wolfe algorithm is that we find the closest vector to the negative gradient (by closest I mean the projection of $$s_{t+1}$$ onto $$-\nabla g(w_t)$$ is maximum). The intuition behind the second step arises from the fact that we start off from $$s_1$$ which is in $$C$$ and chose $$w_{1}$$ so as to be in $$C$$ using the convex combination.

I have drawn the following picture to better understanding.

Note: If $$C$$ was a polytope, then $$s_1$$ is at the vertex of the polytpoe because $$(1)$$ became Linear Programming.

My questions are:

1- Why this works?

2- What is the proof of convergence?

3- When $$-\nabla g(w_t)$$ is not in $$C$$, why $$s_{t+1}$$ is on the boundary of $$C$$?

• This blog post has a section on convergence theory of the FW algorithm that may help answer your question. – David M. Feb 3 at 2:40