GitHub

Frank-Wolfe method

Manopt.Frank_Wolfe_method — Function
Frank_Wolfe_method(M, f, grad_f, p=rand(M); kwargs...)
Frank_Wolfe_method(M, gradient_objective, p=rand(M); kwargs...)
Frank_Wolfe_method!(M, f, grad_f, p; kwargs...)
Frank_Wolfe_method!(M, gradient_objective, p; kwargs...)

Perform the Frank-Wolfe algorithm to compute for $\mathcal{C} ⊂ \mathcal{M}$ the constrained problem

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

where the main step is a constrained optimization within the algorithm, that is the sub problem (Oracle)

\[ \operatorname*{arg\,min}_{q ∈ C} ⟨\operatorname{grad} f(p_k), \log_{p_k}q⟩.\]

for every iterate $p_k$ together with a stepsize $s_k≤1$. The algorithm can be performed in-place of p.

This algorithm is inspired by but slightly more general than [WS22].

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.

Input

  • M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
  • f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
  • grad_f: the (Riemannian) gradient $\operatorname{grad}f: \mathcal{M} → T\mathcal{M}$ of f as a function (M, p) -> X or a function (M, X, p) -> X computing X in-place
  • p::P: a point on the manifold $\mathcal{M}$

Alternatively to f and grad_f you can provide the corresponding AbstractManifoldFirstOrderObjective gradient_objective directly.

Keyword arguments

All other keyword arguments are passed to decorate_state! for state decorators or decorate_objective! for objective decorators, respectively.

If you provide a ManifoldFirstOrderObjective directly, the evaluation= keyword only determines how a closed form solution passed as sub_problem is called. The decorations are still applied to the objective.

Output

The obtained approximate minimizer $p^*$. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

source
Manopt.Frank_Wolfe_method! — Function
Frank_Wolfe_method(M, f, grad_f, p=rand(M); kwargs...)
Frank_Wolfe_method(M, gradient_objective, p=rand(M); kwargs...)
Frank_Wolfe_method!(M, f, grad_f, p; kwargs...)
Frank_Wolfe_method!(M, gradient_objective, p; kwargs...)

Perform the Frank-Wolfe algorithm to compute for $\mathcal{C} ⊂ \mathcal{M}$ the constrained problem

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

where the main step is a constrained optimization within the algorithm, that is the sub problem (Oracle)

\[ \operatorname*{arg\,min}_{q ∈ C} ⟨\operatorname{grad} f(p_k), \log_{p_k}q⟩.\]

for every iterate $p_k$ together with a stepsize $s_k≤1$. The algorithm can be performed in-place of p.

This algorithm is inspired by but slightly more general than [WS22].

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.

Input

  • M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
  • f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
  • grad_f: the (Riemannian) gradient $\operatorname{grad}f: \mathcal{M} → T\mathcal{M}$ of f as a function (M, p) -> X or a function (M, X, p) -> X computing X in-place
  • p::P: a point on the manifold $\mathcal{M}$

Alternatively to f and grad_f you can provide the corresponding AbstractManifoldFirstOrderObjective gradient_objective directly.

Keyword arguments

All other keyword arguments are passed to decorate_state! for state decorators or decorate_objective! for objective decorators, respectively.

If you provide a ManifoldFirstOrderObjective directly, the evaluation= keyword only determines how a closed form solution passed as sub_problem is called. The decorations are still applied to the objective.

Output

The obtained approximate minimizer $p^*$. To obtain the whole final state of the solver, see get_solver_return for details, especially the return_state= keyword.

source

State

Manopt.FrankWolfeState — Type
FrankWolfeState <: AbstractGradientSolverState

A struct to store the current state of the Frank_Wolfe_method

It comes in two forms, depending on the realization of the sub_problem.

Fields

The sub task requires a method to solve

\[ \operatorname*{arg\,min}_{q ∈ C} ⟨\operatorname{grad} f(p_k), \log_{p_k}q⟩.\]

Constructor

FrankWolfeState(M, sub_problem, sub_state; kwargs...)

Initialize the Frank Wolfe method state.

FrankWolfeState(M, sub_problem; evaluation=AllocatingEvaluation(), kwargs...)

Initialize the Frank Wolfe method state, where sub_problem is a closed form solution with evaluation as type of evaluation.

Input

Keyword arguments

where the remaining fields from before are keyword arguments.

source

Helpers

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

Manopt.FrankWolfeCost — Type
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 p and X are stored within this functor and should be references to the iterate and gradient from within FrankWolfeState.

source
Manopt.FrankWolfeGradient — Type
FrankWolfeGradient{P,T}

A structure to represent the gradient of the oracle sub problem in the Frank_Wolfe_method, that is for a given point p and a tangent vector X the function reads

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

Its gradient can be computed easily using adjoint_differential_log_argument.

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

source

Literature

[WS22]
M. Weber and S. Sra. Riemannian Optimization via Frank-Wolfe Methods. Mathematical Programming 199, 525–556 (2022).