Subgradient method

subgradient_method(M, f, ∂f, p=rand(M); kwargs...)
subgradient_method(M, sgo, p=rand(M); kwargs...)
subgradient_method!(M, f, ∂f, p; kwargs...)
subgradient_method!(M, sgo, p; kwargs...)

perform a subgradient method $p^{(k+1)} = \operatorname{retr}\bigl(p^{(k)}, -s^{(k)}∂f(p^{(k)})\bigr)$, where $\operatorname{retr}$ is a retraction, $s^{(k)}$ is a step size.

Though the subgradient might be set valued, the argument ∂f should always return one element from the subgradient, but not necessarily deterministic. For more details see [FO98].

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
• ∂f: the subgradient $∂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. This function should always only return one element from the subgradient.
• p::P: a point on the manifold $\mathcal{M}$

alternatively to f and ∂f a ManifoldSubgradientObjective sgo can be provided.

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
• evaluation::AbstractEvaluationType=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating their result (AllocatingEvaluation) or whether they modify their input argument to return the result therein (InplaceEvaluation). Since usually the first argument is the manifold, the modified argument is the second.
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize::Stepsize=default_stepsize(M,SubGradientMethodState): a functor inheriting from Stepsize to determine a step size
• stopping_criterion::StoppingCriterion=StopAfterIteration(5000): a functor indicating that the stopping criterion is fulfilled
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ to specify the representation of a tangent vector

and the ones that are passed to decorate_state! for decorators.

Output

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

subgradient_method(M, f, ∂f, p=rand(M); kwargs...)
subgradient_method(M, sgo, p=rand(M); kwargs...)
subgradient_method!(M, f, ∂f, p; kwargs...)
subgradient_method!(M, sgo, p; kwargs...)

perform a subgradient method $p^{(k+1)} = \operatorname{retr}\bigl(p^{(k)}, -s^{(k)}∂f(p^{(k)})\bigr)$, where $\operatorname{retr}$ is a retraction, $s^{(k)}$ is a step size.

Though the subgradient might be set valued, the argument ∂f should always return one element from the subgradient, but not necessarily deterministic. For more details see [FO98].

Input

• M::AbstractManifold: a Riemannian manifold $\mathcal{M}$
• f: a cost function $f: \mathcal{M}→ ℝ$ implemented as (M, p) -> v
• ∂f: the subgradient $∂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. This function should always only return one element from the subgradient.
• p::P: a point on the manifold $\mathcal{M}$

alternatively to f and ∂f a ManifoldSubgradientObjective sgo can be provided.

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given either as a single function (symbol, problem, state, k) called in every hook or as a (vector of) pairs :hook => function, which are processed by process_callbacks_arg. As key you can either pass single symbol or an array of symbols to indicate a callback should be added in multiple places
• evaluation::AbstractEvaluationType=AllocatingEvaluation(): specify whether the functions that return an array, for example a point or a tangent vector, work by allocating their result (AllocatingEvaluation) or whether they modify their input argument to return the result therein (InplaceEvaluation). Since usually the first argument is the manifold, the modified argument is the second.
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize::Stepsize=default_stepsize(M,SubGradientMethodState): a functor inheriting from Stepsize to determine a step size
• stopping_criterion::StoppingCriterion=StopAfterIteration(5000): a functor indicating that the stopping criterion is fulfilled
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ to specify the representation of a tangent vector

and the ones that are passed to decorate_state! for decorators.

Output

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

SubGradientMethodState <: AbstractManoptSolverState

stores option values for a subgradient_method solver

Fields

• callbacks::D: provided callback functions given as a dictionary with symbols as keys
• p::P: a point on the manifold $\mathcal{M}$ storing the current iterate
• p_star: the best point visited; the result is returned and, for the in-place variant, stored here
• retraction_method::AbstractRetractionMethod: a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize::Stepsize: a functor inheriting from Stepsize to determine a step size
• stop::StoppingCriterion: a functor indicating that the stopping criterion is fulfilled
• X: the current element from the possible subgradients at p that was last evaluated.

Constructor

SubGradientMethodState(M::AbstractManifold; kwargs...)

Initialize the Subgradient method state

Keyword arguments

• callbacks::D = Dict{Symbol,Function}(): provided callback functions given as a dictionary with symbols as keys
• p::P =rand(M): a point on the manifold $\mathcal{M}$ to specify the initial value
• retraction_method::AbstractRetractionMethod=default_retraction_method(M, typeof(p)): a retraction $\operatorname{retr}$ to use, see the section on retractions
• stepsize::Stepsize=default_stepsize(M,SubGradientMethodState): a functor inheriting from Stepsize to determine a step size
• stopping_criterion::StoppingCriterion=StopAfterIteration(5000): a functor indicating that the stopping criterion is fulfilled
• X::T =zero_vector(M, p): a tangent vector at the point $p$ on the manifold $\mathcal{M}$ to specify the representation of a tangent vector