Frank Wolfe Method

Manopt.Frank_Wolfe_methodFunction
Frank_Wolfe_method(M, F, grad_F, p)

Perform the Frank-Wolfe algorithm to compute for $\mathcal C \subset \mathcal M$

\[ \operatorname*{arg\,min}_{p∈\mathcal C} f(p)\]

Where the main step is a constrained optimisation is within the algorithm, that is the sub problem (Oracle)

\[ q_k = \operatorname{arg\,min}_{q \in C} ⟨\operatorname{grad} F(p_k), \log_{p_k}q⟩.\]

for every iterate $p_k$ together with a stepsize $s_k≤1$, by default $s_k = \frac{2}{k+2}$.

The next iterate is then given by $p_{k+1} = γ_{p_k,q_k}(s_k)$, where by default $γ$ is the shortest geodesic between the two points but can also be changed to use a retraction and its inverse.

Keyword Arguments

  • evaluation (AllocatingEvaluation) whether grad_F is an inplace or allocating (default) funtion
  • initial_vector=zero_vector (zero_vectoir(M,p)) how to initialize the inner gradient tangent vector
  • stopping_criterionStopAfterIteration(500) |StopWhenGradientNormLess(1.0e-6)
  • retraction_method – (default_retraction_method(M, typeof(p))) a type of retraction
  • stepsize (DecreasingStepsize(; length=2.0, shift=2) a Stepsize to use; but it has to be always less than 1. The default is the one proposed by Frank & Wolfe: $s_k = \frac{2}{k+2}$.

all further keywords are passed down to decorate_state!, e.g. debug.

Output

the obtained (approximate) minimizer $x^*$, see get_solver_return for details

source

State

Manopt.FrankWolfeStateType
FrankWolfeState <: AbstractManoptSolverState

A struct to store the current state of the Frank_Wolfe_method

It comes in two forms, depending on the realisation of the subproblem.

Fields

  • p – the current iterate, i.e. a point on the manifold
  • X – the current gradient $\operatorname{grad} F(p)$, i.e. a tangent vector to p.
  • evalulation AllocatingEvaluation specify the type if it is a function.
  • inverse_retraction_method – (default_inverse_retraction_method(M, typeof(p))) an inverse retraction method to use within Frank Wolfe.
  • sub_problem – an AbstractManoptProblem problem for the subsolver
  • sub_state – an AbstractManoptSolverState for the subsolver
  • stop – (StopAfterIteration(200) |StopWhenGradientNormLess(1.0e-6)) a StoppingCriterion
  • stepsize - (DecreasingStepsize(; length=2.0, shift=2)) $s_k$ which by default is set to $s_k = \frac{2}{k+2}$.
  • retraction_method – (default_retraction_method(M, typeof(p))) a retraction to use within Frank-Wolfe

For the subtask, we need a method to solve

\[ \operatorname*{argmin}_{q∈\mathcal M} ⟨X, \log_p q⟩,\qquad \text{ where }X=\operatorname{grad} f(p)\]

Constructor

FrankWolfeState(M, p, X, sub_problem, sub_task)

where the remaining fields from above are keyword arguments with their defaults already given in brackets.

source

Helpers

For the inner sub-problem you can easily create the corresponding cost and gradient using

Manopt.FrankWolfeCostType
FrankWolfeCost{P,T}

A structure to represent the oracle sub problem in the Frank_Wolfe_method. The cost function reads

\[F(q) = ⟨X, \log_p q⟩\]

The values pand X are stored within this functor and hsould be references to the iterate and gradient from within FrankWolfeState.

source
Manopt.FrankWolfeGradientType
FrankWolfeGradient{P,T}

A structure to represent the gradeint of the oracle sub problem in the Frank_Wolfe_method, that is for a given point p and a tangent vector X we have

\[F(q) = ⟨X, \log_p q⟩\]

Its gradient can be computed easily using adjoint_differential_log_argument.

The values pand X are stored within this functor and hsould be references to the iterate and gradient from within FrankWolfeState.

source