6
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ Out of curiosity, where did you find this problem? $\endgroup$
    – littleO
    Nov 13, 2014 at 21:56
  • $\begingroup$ Old assignments from an optimization course $\endgroup$
    – user192348
    Nov 13, 2014 at 22:02
  • $\begingroup$ Thanks. Are any course materials online? What textbook was used? I'd be interested in checking it out. $\endgroup$
    – littleO
    Nov 14, 2014 at 2:08

1 Answer 1

3
$\begingroup$

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). $$

$\endgroup$
2
  • $\begingroup$ Thanks a lot for all that information! I'll be giving that paper a look very shortly. Just to be clear on my question, I'm just trying to solve: $$d_k = argmin \nabla f(x_k)^T(x_k+d_k-x_k)$$ subject to the constraints on $x$ being in $X$. This may seem like a trivial exercise, but it's currently causing me a lot of grief. $\endgroup$
    – user192348
    Nov 13, 2014 at 22:33
  • 2
    $\begingroup$ Great answer and perspective, you should post here more often. $\endgroup$
    – littleO
    Nov 14, 2014 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy