# Solvers

Solvers can be applied to `Problem`

s with solver specific `Options`

.

# List of Algorithms

The following algorithms are currently available

Solver | File | Problem & Option |
---|---|---|

steepest Descent | `steepestDescent.jl` | `GradientProblem` , `GradientDescentOptions` |

Cyclic Proximal Point | `cyclicProximalPoint.jl` | `ProximalProblem` , `CyclicProximalPointOptions` |

Douglas–Rachford | `DouglasRachford.jl` | `ProximalProblem` , `DouglasRachfordOptions` |

Nelder-Mead | `NelderMead.jl` | `CostProblem` , `NelderMeadOptions` |

Subgradient Method | `subGradientMethod.jl` | `SubGradientProblem` , `SubGradientMethodOptions` |

Steihaug-Toint Truncated Conjugate-Gradient Method | `truncatedConjugateGradient.jl` | `HessianProblem` , |

`TruncatedConjugateGradientOptions`

The Riemannian Trust-Regions Solver | `trustRegions.jl`

| `HessianProblem`

, `TrustRegionsOptions`

Note that the `Options`

can also be decorated to enhance your algorithm by general additional properties.

## StoppingCriteria

Stopping criteria are implemented as a `functor`

, i.e. inherit from the base type

`Manopt.StoppingCriterion`

— Type.`StoppingCriterion`

An abstract type for the functors representing stoping 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 fiels `reason`

to provide details when a criteion is met (and that is empty otherwise).

`Manopt.StoppingCriterionSet`

— Type.`StoppingCriterionGroup <: StoppingCriterion`

An abstract type for a Stopping Criterion that itself consists of a set of Stopping criteria. In total it acts as a stopping criterion itself. Examples are `stopWhenAny`

and `stopWhenAll`

that can be used to combine stopping criteria.

`Manopt.stopAfter`

— Type.`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.

`Manopt.stopAfterIteration`

— Type.`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`getReason`

.

**Constructor**

`stopAfterIteration(maxIter)`

initialize the stopafterIteration functor to indicate to stop after `maxIter`

iterations.

`Manopt.stopWhenAll`

— Type.`stopWhenAll <: StoppingCriterion`

store an array of `StoppingCriterion`

elements and indicates to stop, when *all* indicate to stop. The `reseason`

is given by the concatenation of all reasons.

**Constructor**

```
stopWhenAll(c::Array{StoppingCriterion,1})
stopWhenAll(c::StoppingCriterion,...)
```

`Manopt.stopWhenAny`

— Type.`stopWhenAny <: StoppingCriterion`

store an array of `StoppingCriterion`

elements and indicates to stop, when *any* single one indicates to stop. The `reseason`

is given by the concatenation of all reasons (assuming that all non-indicating return `""`

).

**Constructor**

```
stopWhenAny(c::Array{StoppingCriterion,1})
stopWhenAny(c::StoppingCriterion,...)
```

`Manopt.stopWhenChangeLess`

— Type.`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.

`Manopt.stopWhenCostLess`

— Type.`stopWhenCostLess <: StoppingCriterion`

store a threshold when to stop looking at the cost function of the optimization problem from within a `Problem`

, i.e `getCost(p,o.x)`

.

**Constructor**

`stopWhenCostLess(ε)`

initialize the stopping criterion to a threshold `ε`

.

`Manopt.stopWhenGradientNormLess`

— Type.`stopWhenGradientNormLess <: StoppingCriterion`

stores a threshold when to stop looking at the norm of the gradient from within a `GradientProblem`

.

as well as the functions

`Manopt.getReason`

— Function.`getReason(o)`

return the current reason stored within the `StoppingCriterion`

from within the `Options`

This reason is empty if the criterion has never been met.

`getReason(c)`

return the current reason stored within a `StoppingCriterion`

`c`

. This reason is empty if the criterion has never been met.

`Manopt.getStoppingCriteriaArray`

— Function.`getStoppingCriteriaArray(c)`

return the array of internally stored `StoppingCriterion`

s for a `StoppingCriterionSet`

`c`

.

`Manopt.getActiveStoppingCriteria`

— Function.`getActiveStoppingCriteria(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 incated 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.

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 `DebugAction`

s. For example printing a gradient from the `GradientDescentOptions`

is automatically available, as explained in the `steepestDescent`

solver.

`Manopt.initializeSolver!`

— Method.`initializeSolver!(p,o)`

Initialize the solver to the optimization `Problem`

by initializing all values in the `DebugOptions`

`o`

.

`Manopt.doSolverStep!`

— Method.`Manopt.getSolverResult`

— Method.`getSolverResult(o)`

Return the final result after all iterations that is stored within the (modified during the iterations) `Options`

`o`

.

`Manopt.stopSolver!`

— Method.`stopSolver!(p,o,i)`

determine whether the solver for `Problem`

`p`

and the `DebugOptions`

`o`

should stop at iteration `i`

. If so, print all debug from `:All`

and `:Final`

.

### Record Solver

The decorator to record certain values during the iterations can be activated by decorating the `Options`

with `RecordOptions`

and implementing your own `RecordAction`

s. For example recording the gradient from the `GradientDescentOptions`

is automatically available, as explained in the `steepestDescent`

solver.

`Manopt.initializeSolver!`

— Method.`initializeSolver!(p,o)`

Initialize the solver to the optimization `Problem`

by initializing the encapsulated `options`

from within the `RecordOptions`

`o`

.

`Manopt.doSolverStep!`

— Method.`Manopt.getSolverResult`

— Method.`getSolverResult(o)`

Return the final result after all iterations that is stored within the (modified during the iterations) `Options`

`o`

.

`Manopt.stopSolver!`

— Method.`stopSolver!(p,o,i)`

determine whether the solver for `Problem`

`p`

and the `RecordOptions`

`o`

should stop at iteration `i`

. If so, do a (final) record to `:All`

and `:Stop`

.

## Technical Details

The main function a solver calls is

`Manopt.solve`

— Method.`solve(p,o)`

run the solver implemented for the `Problem`

`p`

and the `Options`

`o`

employing `initializeSolver!`

, `doSolverStep!`

, as well as the `stopSolver!`

of the solver.

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.

`Manopt.initializeSolver!`

— Method.`Manopt.doSolverStep!`

— Method.`Manopt.getSolverResult`

— Method.`getSolverResult(o)`

Return the final result after all iterations that is stored within the (modified during the iterations) `Options`

`o`

.

`Manopt.stopSolver!`

— Method.`stopSolver!(p,o,i)`

depending on the current `Problem`

`p`

, the current state of the solver stored in `Options`

`o`

and the current iterate `i`

this function determines whether to stop the solver by calling the `StoppingCriterion`

.