Take some convex optimization problem:

minimize $f(x)$
subject to $x \in C$

Here, $C$ is some convex set. If $C$ is hard to characterize, this optimization problem might be hard to handle in a direct fashion. For example, $C$ might require enforcing some exponential number of constraints. In some problems, it nevertheless turns out to be possible to solve the following problem:

minimize $c^T x$
subject to $x \in C$

That is, for linear objective functions, the problem is solvable. (This might be, for example, by some graph algorithm). Anyway, the Conditional-Gradient method solves the original problem by repeatedly relinearizing it, and solving the linear optimization. One can then take a step to some point between the current position, and the solution to the linearized problem.

Initialize $x \in C$ anywhere.
Repeat:
1) $f_\text{lin}(x')=f(x)+\nabla f(x) (x'-x)$
2) $x_\text{lin} = \arg\min f_\text{lin}(x_\text{lin}) \text{ s.t. } x_\text{lin} \in C$
3) $x \leftarrow \alpha x + (1-\alpha) x_\text{lin}$, for some $0 \leq \alpha \leq 1$.

In step 3, $\alpha$ controls how far $x$ moves towards $x_\text{lin}$. Notice that because $C$ is convex, for any $\alpha$, $\alpha x + (1-\alpha) x_\text{lin} \in C$

The information I can find doesn’t make any argument for convergence. Clearly, $x$ never gets worse, so (assuming the objective is bounded below) the algorithm will converge, but I haven’t found what under conditions it converges to the optimal value, or at what rate.

### One Response to Conditional Gradient Method

1. Suresh says:

Convergence rate of the method is sublinear unfortunately. This is shown in Bertsekas’s book on nonlinear optimization.