Problems

A problem usually contains its cost function and provides and implementation to access the cost

Manopt.ProblemType
Problem{T}

Describe the problem that should be optimized by stating all properties, that do not change during an optimization or that are dependent of a certain solver.

The parameter T can be used to distinguish problems with different representations or implementations. The default parameter AllocatingEvaluation, which might be slower but easier to use. The usually faster parameter value is MutatingEvaluation

See Options for the changing and solver dependent properties.

source

A problem can be of different type, more specifically, whether its containing functions, for example to compute the gradient work with allocation or without. To be precise, an allocation function X = gradF(x) allocates memory for its result X, while gradF!(X,x) does not.

Manopt.AllocatingEvaluationType
AllocatingEvaluation <: AbstractEvaluationType

A parameter for a Problem indicating that the problem uses functions that allocate memory for their result, i.e. they work out of place.

source
Manopt.MutatingEvaluationType
MutatingEvaluation

A parameter for a Problem indicating that the problem uses functions that do not allocate memory but work on their input, i.e. in place.

source

Cost based problem

Manopt.CostProblemType
CostProblem{T, Manifold, TCost} <: Problem{T}

speficy a problem for solvers just based on cost functions, i.e. gradient free ones.

Fields

  • M – a manifold $\mathcal M$
  • cost – a function $F: \mathcal M → ℝ$ to minimize

Constructors

CostProblem(M, cost; evaluation=AllocatingEvaluation())

Generate a problem. While this Problem does not have any allocating functions, the type T can be set for consistency reasons with other problems.

See also

NelderMead

source

Gradient based problem

Manopt.GradientProblemType
GradientProblem{T} <: AbstractGradientProblem{T}

specify a problem for gradient based algorithms.

Fields

  • M – a manifold $\mathcal M$
  • cost – a function $F: \mathcal M → ℝ$ to minimize
  • gradient!! – the gradient $\operatorname{grad}F:\mathcal M → \mathcal T\mathcal M$ of the cost function $F$.

Depending on the AbstractEvaluationType T the gradient has to be provided

Constructors

GradientProblem(M, cost, gradient; evaluation=AllocatingEvaluation())

See also

gradient_descent, GradientDescentOptions

source
Manopt.StochasticGradientProblemType
StochasticGradientProblem <: Problem

A stochastic gradient problem consists of

  • a Manifold M
  • a(n optional) cost function ``f(x) = \displaystyle\sum{i=1}^n fi(x)
  • an array of gradients, i.e. a function that returns and array or an array of functions

$\{\operatorname{grad}f_i\}_{i=1}^n$, where both variants can be given in the allocating variant and the array of function may also be provided as mutating functions (X,x) -> X.

Constructors

StochasticGradientProblem(M::AbstractManifold, gradF::Function;
    cost=Missing(), evaluation=AllocatingEvaluation()
)
StochasticGradientProblem(M::AbstractManifold, gradF::AbstractVector{<:Function};
    cost=Missing(), evaluation=AllocatingEvaluation()
)

Create a Stochastic gradient problem with an optional cost and the gradient either as one function (returning an array) or a vector of functions.

source
Manopt.get_gradientFunction
get_gradient(O::Options)

return the (last stored) gradient within Options`O. By default also undecorates the options beforehand

source
get_gradient(p::AbstractGradientProblem{T},x)
get_gradient!(p::AbstractGradientProblem{T}, X, x)

evaluate the gradient of a AbstractGradientProblem{T}p at the point x.

The evaluation is done in place of X for the !-variant. The T=AllocatingEvaluation problem might still allocate memory within. When the non-mutating variant is called with a T=MutatingEvaluation memory for the result is allocated.

source
get_gradient(p::StochasticGradientProblem, k, x)
get_gradient!(p::StochasticGradientProblem, Y, k, x)

Evaluate one of the summands gradients $\operatorname{grad}f_k$, $k∈\{1,…,n\}$, at x (in place of Y).

Note that for the MutatingEvaluation based problem and a single function for the stochastic gradient mutating variant is not available, since it would require too many allocations.

source
get_gradient(P::AlternatingGradientProblem, x)
get_gradient!(P::AlternatingGradientProblem, Y, x)

Evaluate all summands gradients at a point x on the ProductManifold M (in place of Y)

source
get_gradient(p::AlternatingGradientProblem, k, x)
get_gradient!(p::AlternatingGradientProblem, Y, k, x)

Evaluate one of the component gradients $\operatorname{grad}f_k$, $k∈\{1,…,n\}$, at x (in place of Y).

source
Manopt.get_gradientsFunction
get_gradients(P::StochasticGradientProblem, x)
get_gradients!(P::StochasticGradientProblem, Y, x)

Evaluate all summands gradients $\{\operatorname{grad}f_i\}_{i=1}^n$ at x (in place of Y).

Note that for the MutatingEvaluation based problem and a single function for the stochastic gradient, the allocating variant is not available.

source

Subgradient based problem

Manopt.SubGradientProblemType
SubGradientProblem <: Problem

A structure to store information about a subgradient based optimization problem

Fields

  • manifold – a Manifold
  • cost – the function $F$ to be minimized
  • subgradient – a function returning a subgradient $\partial F$ of $F$

Constructor

SubGradientProblem(M, f, ∂f)

Generate the [Problem] for a subgradient problem, i.e. a function f on the manifold M and a function ∂f that returns an element from the subdifferential at a point.

source

Proximal Map(s) based problem

Manopt.ProximalProblemType
ProximalProblem <: Problem

specify a problem for solvers based on the evaluation of proximal map(s).

Fields

  • M - a Riemannian manifold
  • cost - a function $F:\mathcal M→ℝ$ to minimize
  • proxes - proximal maps $\operatorname{prox}_{λ\varphi}:\mathcal M→\mathcal M$ as functions (λ,x) -> y, i.e. the prox parameter λ also belongs to the signature of the proximal map.
  • number_of_proxes - (length(proxes)) number of proximal Maps, e.g. if one of the maps is a combined one such that the proximal Maps functions return more than one entry per function

See also

cyclic_proximal_point, get_cost, get_proximal_map

source
Manopt.get_proximal_mapFunction
get_proximal_map(p,λ,x,i)

evaluate the ith proximal map of ProximalProblem p at the point x of p.M with parameter $λ>0$.

source

Hessian based problem

Manopt.HessianProblemType
HessianProblem <: Problem

specify a problem for hessian based algorithms.

Fields

  • M : a manifold $\mathcal M$
  • cost : a function $F:\mathcal M→ℝ$ to minimize
  • gradient : the gradient $\operatorname{grad}F:\mathcal M → \mathcal T\mathcal M$ of the cost function $F$
  • hessian : the hessian $\operatorname{Hess}F(x)[⋅]: \mathcal T_{x} \mathcal M → \mathcal T_{x} \mathcal M$ of the cost function $F$
  • precon : the symmetric, positive definite preconditioner (approximation of the inverse of the Hessian of $F$)

See also

truncated_conjugate_gradient_descent, trust_regions

source
Manopt.get_hessianFunction
get_hessian(p::HessianProblem{T}, q, X)
get_hessian!(p::HessianProblem{T}, Y, q, X)

evaluate the Hessian of a HessianProblem p at the point q applied to a tangent vector X, i.e. $\operatorname{Hess}f(q)[X]$.

The evaluation is done in place of Y for the !-variant. The T=AllocatingEvaluation problem might still allocate memory within. When the non-mutating variant is called with a T=MutatingEvaluation memory for the result is allocated.

source
Manopt.get_preconditionerFunction
get_preconditioner(p,x,ξ)

evaluate the symmetric, positive definite preconditioner (approximation of the inverse of the Hessian of the cost function F) of a HessianProblem p at the point xapplied to a tangent vector ξ.

source

Primal dual based problem

Manopt.PrimalDualProblemType
PrimalDualProblem {T, mT <: AbstractManifold, nT <: AbstractManifold} <: AbstractPrimalDualProblem

Describes a Problem for the linearized or exact Chambolle-Pock algorithm.[BergmannHerzogSilvaLouzeiroTenbrinckVidalNunez2020][ChambollePock2011]

Fields

All fields with !! can either be mutating or nonmutating functions, which should be set depenting on the parameter T <: AbstractEvaluationType.

  • M, N – two manifolds $\mathcal M$, $\mathcal N$
  • cost $F + G(Λ(⋅))$ to evaluate interims cost function values
  • linearized_forward_operator!! linearized operator for the forward operation in the algorithm $DΛ$
  • linearized_adjoint_operator!! The adjoint differential $(DΛ)^* : \mathcal N → T\mathcal M$
  • prox_F!! the proximal map belonging to $f$
  • prox_G_dual!! the proximal map belonging to $g_n^*$
  • Λ!! – (fordward_operator) the forward operator (if given) $Λ: \mathcal M → \mathcal N$

Either $DΛ$ (for the linearized) or $Λ$ are required usually.

Constructor

LinearizedPrimalDualProblem(M, N, cost, prox_F, prox_G_dual, adjoint_linearized_operator;
    linearized_forward_operator::Union{Function,Missing}=missing,
    Λ::Union{Function,Missing}=missing,
    evaluation::AbstractEvaluationType=AllocatingEvaluation()
)

The last optional argument can be used to provide the 4 or 5 functions as allocating or mutating (in place computation) ones. Note that the first argument is always the manifold under consideration, the mutated one is the second.

source
Manopt.PrimalDualSemismoothNewtonProblemType
PrimalDualSemismoothNewtonProblem {T,mT <: AbstractManifold, nT <: AbstractManifold} <: AbstractPrimalDualProblem{T}

Describes a Problem for the Primal-dual Riemannian semismooth Newton algorithm. [DiepeveenLellmann2021]

Fields

  • M, N – two manifolds $\mathcal M$, $\mathcal N$
  • cost $F + G(Λ(⋅))$ to evaluate interims cost function values
  • linearized_operator the linearization $DΛ(⋅)[⋅]$ of the operator $Λ(⋅)$.
  • linearized_adjoint_operator The adjoint differential $(DΛ)^* \colon \mathcal N \to T\mathcal M$
  • prox_F the proximal map belonging to $f$
  • diff_prox_F the (Clarke Generalized) differential of the proximal maps of $F$
  • prox_G_dual the proximal map belonging to $g_n^*$
  • diff_prox_dual_G the (Clarke Generalized) differential of the proximal maps of $G^\ast_n$
  • Λ – the exact forward operator. This operator is required if Λ(m)=n does not hold.

Constructor

PrimalDualSemismoothNewtonProblem(M, N, cost, prox_F, prox_G_dual, forward_operator, adjoint_linearized_operator,Λ)
source
Manopt.get_primal_proxFunction
y = get_primal_prox(p::AbstractPrimalDualProblem, σ, x)
get_primal_prox!(p::AbstractPrimalDualProblem, y, σ, x)

Evaluate the proximal map of $F$ stored within AbstractPrimalDualProblem

\[\operatorname{prox}_{σF}(x)\]

which can also be computed in place of y.

source
Manopt.get_dual_proxFunction
y = get_dual_prox(p::AbstractPrimalDualProblem, n, τ, ξ)
get_dual_prox!(p::AbstractPrimalDualProblem, y, n, τ, ξ)

Evaluate the proximal map of $G_n^*$ stored within AbstractPrimalDualProblem

\[\operatorname{prox}_{τG_n^*}(ξ)\]

which can also be computed in place of y.

source
Manopt.linearized_forward_operatorFunction
Y = linearized_forward_operator(p::AbstractPrimalDualProblem, m X, n)
linearized_forward_operator!(p::AbstractPrimalDualProblem, Y, m, X, n)

Evaluate the linearized operator (differential) $DΛ(m)[X]$ stored within the AbstractPrimalDualProblem (in place of Y), where n = Λ(m).

source
Manopt.adjoint_linearized_operatorFunction
X = adjoint_linearized_operator(p::AbstractPrimalDualProblem, m, n, Y)
adjoint_linearized_operator(p::AbstractPrimalDualProblem, X, m, n, Y)

Evaluate the adjoint of the linearized forward operator of $(DΛ(m))^*[Y]$ stored within the AbstractPrimalDualProblem (in place of X). Since $Y∈T_n\mathcal N$, both $m$ and $n=Λ(m)$ are necessary arguments, mainly because the forward operator $Λ$ might be missing in p.

source
Manopt.get_differential_primal_proxFunction
y = get_differential_primal_prox(p::PrimalDualSemismoothNewtonProblem, σ, x)
get_differential_primal_prox!(p::PrimalDualSemismoothNewtonProblem, y, σ, x)

Evaluate the differential proximal map of $F$ stored within PrimalDualSemismoothNewtonProblem

\[D\operatorname{prox}_{σF}(x)[X]\]

which can also be computed in place of y.

source
Manopt.get_differential_dual_proxFunction
y = get_differential_dual_prox(p::PrimalDualSemismoothNewtonProblem, n, τ, ξ, Ξ)
get_differential_dual_prox!(p::PrimalDualSemismoothNewtonProblem, y, n, τ, ξ, Ξ)

Evaluate the differential proximal map of $G_n^*$ stored within PrimalDualSemismoothNewtonProblem

\[D\operatorname{prox}_{τG_n^*}(ξ)[Ξ]\]

which can also be computed in place of y.

source