Frank-Wolfe Method

The following problem is given:

min_{x} f (x)

subjet to

A x = b, x \geq 0

from which we get the solution $\hat{x}$ .

where:

$f (x) : R^{n} \to R$
$A \in R^{n} \times R^{n}$
$x \in R^{n}$
$b \in R^{n}$

The Frank-Wolfe is an iterative method to solve the problem with the following steps

0. Find a feasible solution

The first step is to find any feasible solution $x^{(k)}$ . In the first iteration, $k = 0$ .

This solution has to meet the condition $A x = b, x \geq 0$

1. Define the subproblem

The Frank-Wolfe method works generating a new problem, called a subproblem. This is still an optimization problem but is allegedly easier to solve.

In order to define the new problem, we first need to find the Gradient of $f (x)$ . Then, the subproblem is:

min_{y} \nabla f {(x^{(k)})}^{T} \cdot y

subj to:

A y = b, y \geq 0

from which we get the value $\hat{y}$ .

Calculate the descent direction

The, we need to calculate a new vector, called the direction, that will allow us to get the solution for the next step of the algorithm.

d^{(k)} = \hat{y} - x^{(k)}

2. Stopping criteria

We need some sort of stopping criteria to know if the solution $x^{(k)}$ is close enough to the actual solution $\hat{x}$ of the original problem.

We calculate a relative gap, $r$ as

r = - \frac{\nabla f {(x^{(k)})}^{T} \cdot d^{(k)}}{\nabla f {(x^{(k)})}^{T} \cdot x^{(k)}}

We define a relative gap that we find suitable. This is going to be a very small value, $ε$ ( $= 10^{- 2}, 10^{- 4}, . . .$ )

If $r < ε$ than we stop and accept $x^{(k)}$ as a solution ( $x^{(k)} \approx \hat{x}$ ). Otherwise, we go the next step

3. Line search

The new solution will be given by

x^{(k + 1)} = x^{(k)} + α^{*} d^{(k)}

where $α^{*}$ is the solution to the problem:

min_{0 \leq α \leq 1} h (α) = min_{0 \leq α \leq 1} f (x^{(k)} + α d^{(k)})

This can be solved finding the first derivative of $h (α)$ , imposing it equal to 0 and then solving for $α$ . This last step is often impossible to do analitically, so we rely on numeric methods to find $α^{*}$ (like: Metodo di Newton o Il metodo delle Tangenti, Metodo di Bisezione, Il metodo delle Secanti).

In the particular case that all elements of $\nabla f (x^{(k)}) \overset{△}{=} s (x^{(k)})$ are in the form $a + b x$ , then $α^{*}$ can be taken equal to
$min {1, \tilde{α}}$
where:
$\tilde{α} = \frac{\sum_{i} s_{i} (x_{i}) \cdot d_{i}^{(k)}}{\sum_{i} b_{i} \cdot {(d_{i}^{(k)})}^{2}}$

4. Update

After having found $α^{*}$ is time to update the solution to the next step: $x^{(k)}$ and repeat the method from step #0. Find a feasible solution