Constrained Optimizatoin: The Frank-Wolfe Method

Question

A general convex optimization problem is framed as such:

$$\min f(x) : x \in \Omega$$ where $\Omega$ is convex.

The Frank-Wolfe method seeks a feasible descent direction $d_k$ (i.e. $x_k + d_k \in \Omega$) such that $\nabla(f_k)^Td_k < 0$

So I'm solving the subproblem: $$\min \nabla(f_k)^T(x-x_k) : x \in X$$

and in this instance am given the closed form solution:

$$X = \left\{x:x \ge0 \sum x_i=b\right\}$$ where $b > 0$

The problem is to find (given an $x_k$) an explicit solution for $d_k$ to the subproblem.

What I have done so far:

• Determined that $\sum d_i = 0$ since $x_k$ and $x_{k+1}$ must satisfy $\sum x_i=b$
• Determined that $d_i \ge -x_i$ so that $x \ge0$ is satisfied at each iteration
• I know that if this were an unconstrained optimization problem the solution would be the steepest descent direction: $d_k = -\nabla f_k$ (I realize this is probably irrelevant)

Any advice on how to solve this problem for the descent direction $d_k$ would be greatly appreciated. Thanks in advance!

Answer 1

Historically, in 50s people thought that linear programming is (relatively) easy, nonlinear is difficult. The original idea behind Frank-Wolfe algorithm [original paper] was to break difficult nonlinear problems into sequence of easy linear problems.

Given current iterate $x_k$, this was done by minimizing linear approximation to your function $f$, over your feasible set $X$. I.e., find $s_k$ such that $$ s_k = \arg\min_{x \in X} \nabla f(x_k)^T (x - x_k), $$ This was supposed to be easy, because you could just use a linear programming solver to find it.

And, then you make an update from $x_k$, in the direction of $s$. In other words, you take their linear combination. $$ x_{k+1} = (1 - \gamma_k) x_k + \gamma_k s_k, \quad \quad \text{where} \quad \quad \gamma_k = \frac{2}{k+2} $$ Note that there are more ways to set $\gamma_k$; this one works fine in general.

---

The Frank-Wolfe algorithms attracted renewed attention recently when people started assuming more about the feasible sets --- and this applies to your case. The motivation appeared in machine learning in from several sources.

If you can write you set $X$ as a convex hull of finite number of points (sparse points in particular), you know that solution to your subproblem must lie in one of these points. In your case, $$ X = \text{conv} \{ b e_i \,|\, i = 1, 2, \dots, d \}, $$ where $d$ is your dimension and $e_i$ is the $i^{th}$ unit length coordinate vector.

So, all you need to do is check value of the linear approximation in each of the corners of your simplex and you are done. You can find details on this topic in recent paper. Section 4 might be particularly interesting for you. A nice side property is that you have easily computable stopping criterion, because $$ f(x_k) - f(x_*) \leq f(x_k) - f(s_k). $$