# Solvers

Solvers can be applied to Problems with solver specific Options.

# List of Algorithms

The following algorithms are currently available

SolverFileProblem & Option
Alternating Gradient Descentalterating_gradient_descent.jlAlternatingGradientProblem, AlternatingGradientDescentOptions
Chambolle-PockChambolle-Pock.jlPrimalDualProblem, ChambollePockOptions
Cyclic Proximal Pointcyclic_proximal_point.jlProximalProblem, CyclicProximalPointOptions
Douglas–RachfordDouglasRachford.jlProximalProblem, DouglasRachfordOptions
Gradient Descentgradient_descent.jlGradientProblem, GradientDescentOptions
Nelder-MeadNelderMead.jlCostProblem, NelderMeadOptions
Particle Swarmparticle_swarm.jlCostProblem, ParticleSwarmOptions
Quasi-Newton Methodquasi_newton.jlGradientProblem, QuasiNewtonOptions
Subgradient Methodsubgradient_method.jlSubGradientProblem, SubGradientMethodOptions
Steihaug-Toint Truncated Conjugate-Gradient Methodtruncated_conjugate_gradient_descent.jlHessianProblem, TruncatedConjugateGradientOptions
The Riemannian Trust-Regions Solvertrust_regions.jlHessianProblem, TrustRegionsOptions

Note that the solvers (or their Options to be precise) can also be decorated to enhance your algorithm by general additional properties, see Decorated Solvers.

## StoppingCriteria

Stopping criteria are implemented as a functor, i.e. inherit from the base type

Manopt.StoppingCriterionType
StoppingCriterion

An abstract type for the functors representing stopping criteria, i.e. they are callable structures. The naming Scheme follows functions, see for example StopAfterIteration.

Every StoppingCriterion has to provide a constructor and its function has to have the interface (p,o,i) where a Problem as well as Options and the current number of iterations are the arguments and returns a Bool whether to stop or not.

By default each StoppingCriterion should provide a fields reason to provide details when a criterion is met (and that is empty otherwise).

source
Manopt.StopAfterType
StopAfter <: StoppingCriterion

store a threshold when to stop looking at the complete runtime. It uses time_ns() to measure the time and you provide a Period as a time limit, i.e. Minute(15)

Constructor

StopAfter(t)

initialize the stopping criterion to a Period t to stop after.

source
Manopt.StopAfterIterationType
StopAfterIteration <: StoppingCriterion

A functor for an easy stopping criterion, i.e. to stop after a maximal number of iterations.

Fields

• maxIter – stores the maximal iteration number where to stop at
• reason – stores a reason of stopping if the stopping criterion has one be reached, see get_reason.

Constructor

StopAfterIteration(maxIter)

initialize the stopafterIteration functor to indicate to stop after maxIter iterations.

source
Manopt.StopWhenAllType
StopWhenAll <: StoppingCriterion

store an array of StoppingCriterion elements and indicates to stop, when all indicate to stop. The reason is given by the concatenation of all reasons.

Constructor

StopWhenAll(c::NTuple{N,StoppingCriterion} where N)
StopWhenAll(c::StoppingCriterion,...)
source
Manopt.StopWhenAnyType
StopWhenAny <: StoppingCriterion

store an array of StoppingCriterion elements and indicates to stop, when any single one indicates to stop. The reason is given by the concatenation of all reasons (assuming that all non-indicating return "").

Constructor

StopWhenAny(c::NTuple{N,StoppingCriterion} where N)
StopWhenAny(c::StoppingCriterion...)
source
Manopt.StopWhenChangeLessType
StopWhenChangeLess <: StoppingCriterion

stores a threshold when to stop looking at the norm of the change of the optimization variable from within a Options, i.e o.x. For the storage a StoreOptionsAction is used

Constructor

StopWhenChangeLess(ε[, a])

initialize the stopping criterion to a threshold ε using the StoreOptionsAction a, which is initialized to just store :x by default.

source
Manopt.StopWhenCostLessType
StopWhenCostLess <: StoppingCriterion

store a threshold when to stop looking at the cost function of the optimization problem from within a Problem, i.e get_cost(p,o.x).

Constructor

StopWhenCostLess(ε)

initialize the stopping criterion to a threshold ε.

source

as well as the functions

Base.:&Method
&(s1,s2)
s1 & s2

Combine two StoppingCriterion within an StopWhenAll. If either s1 (or s2) is already an StopWhenAll, then s2 (or s1) is appended to the list of StoppingCriterion within s1 (or s2).

Example

a = StopAfterIteration(200) & StopWhenChangeLess(1e-6)
b = a & StopWhenGradientNormLess(1e-6)

Is the same as

a = StopWhenAll(StopAfterIteration(200), StopWhenChangeLess(1e-6))
b = StopWhenAll(StopAfterIteration(200), StopWhenChangeLess(1e-6), StopWhenGradientNormLess(1e-6))
source
Base.:|Method
|(s1,s2)
s1 | s2

Combine two StoppingCriterion within an StopWhenAny. If either s1 (or s2) is already an StopWhenAny, then s2 (or s1) is appended to the list of StoppingCriterion within s1 (or s2)

Example

a = StopAfterIteration(200) | StopWhenChangeLess(1e-6)
b = a | StopWhenGradientNormLess(1e-6)

Is the same as

a = StopWhenAny(StopAfterIteration(200), StopWhenChangeLess(1e-6))
b = StopWhenAny(StopAfterIteration(200), StopWhenChangeLess(1e-6), StopWhenGradientNormLess(1e-6))
source
Manopt.get_active_stopping_criteriaFunction
get_active_stopping_criteria(c)

returns all active stopping criteria, if any, that are within a StoppingCriterion c, and indicated a stop, i.e. their reason is nonempty. To be precise for a simple stopping criterion, this returns either an empty array if no stop is indicated or the stopping criterion as the only element of an array. For a StoppingCriterionSet all internal (even nested) criteria that indicate to stop are returned.

source
Manopt.are_these_stopping_critera_activeFunction
are_these_stopping_critera_active(c::StoppingCriterion, cond)

Return true if any criterion from the given set is both active and fulfils the given condition cond (cond(c) returns true).

source

further stopping criteria might be available for individual Solvers.

## Decorated Solvers

The following decorators are available.

### Debug Solver

The decorator to print debug during the iterations can be activated by decorating the Options with DebugOptions and implementing your own DebugActions. For example printing a gradient from the GradientDescentOptions is automatically available, as explained in the gradient_descent solver.

### Record Solver

The decorator to record certain values during the iterations can be activated by decorating the Options with RecordOptions and implementing your own RecordActions. For example recording the gradient from the GradientDescentOptions is automatically available, as explained in the gradient_descent solver.

## Technical Details

The main function a solver calls is

which is a framework, that you in general should not change or redefine. It uses the following methods, which also need to be implemented on your own algorithm, if you want to provide one.