Conditional Gradient Method

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, but I want a proof of the following:

If x is not at the global minimum, the line search will find some \alpha > 0.

Leave a Reply