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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s