Plans for solvers

getOptions(O)

return the undecorated Options of the (possibly) decorated O. As long as your decorated options stores the options within o.options and implements the SimpleTrait IsOptionsDecorator, this is behaviour is optained automatically.

decorateOptions(o)

decorate the Optionso with specific decorators.

Optional Arguments

optional arguments provide necessary details on the decorators. A specific one is used to activate certain decorators.

• debug – (Array{Union{Symbol,DebugAction,String,Int},1}()) a set of symbols representing DebugActions, Strings used as dividers and a subsampling integer. These are passed as a DebugGroup within :All to the DebugOptions decorator dictionary. Only excention is :Stop that is passed to :Stop.
• record – (Array{Union{Symbol,RecordAction,Int},1}()) specify recordings by using Symbols or RecordActions directly. The integer can again be used for only recording every $i$th iteration.

See also

DebugOptions, RecordOptions

Action

a common Type for Actions that might be triggered in decoraters, for example DebugOptions or RecordOptions.

StoreTupleAction <: Action

internal storage for Actions to store a tuple of fields from an Optionss

This functor posesses the usual interface of functions called during an iteration, i.e. acts on (p,o,i), where p is a Problem, o is an Options and i is the current iteration.

Fields

• values – a dictionary to store interims values based on certain Symbols
• keys – an NTuple of Symbols to refer to fields of Options
• once – whether to update the internal values only once per iteration
• lastStored – last iterate, where this Action was called (to determine once

Constructiors

StoreOptionsAction([keys=(), once=true])

Initialize the Functor to an (empty) set of keys, where once determines whether more that one update per iteration are effective

StoreOptionsAction(keys, once=true])

Initialize the Functor to a set of keys, where the dictionary is initialized to be empty. Further, once determines whether more that one update per iteration are effective, otherwise only the first update is stored, all others are ignored.

DebugAction

A DebugAction is a small functor to print/issue debug output. The usual call is given by (p,o,i) -> s that performs the debug based on a Problem p, Options o and the current iterate i.

By convention i=0 is interpreted as "For Initialization only", i.e. only debug info that prints initialization reacts, i<0 triggers updates of variables internally but does not trigger any output. Finally typemin(Int) is used to indicate a call from stopSolver! that returns true afterwards.

Fields (assumed by subtypes to exist)

• print method to perform the actual print. Can for example be set to a file export,

or to @info. The default is the print function on the default Base.stdout.

DebugChange(a,prefix,print)

debug for the amount of change of the iterate (stored in o.x of the Options) during the last iteration. See DebugEntryChange

Parameters

• x0 – an initial value to already get a Change after the first iterate. Can be left out
• a – (StoreOptionsAction( (:x,) )) – the storage of the previous action
• prefix – ("Last Change:") prefix of the debug output
• print – (print) default method to peform the print.

DebugCost <: DebugAction

print the current cost function value, see getCost.

Constructors

DebugCost(long,print)

where long indicated whether to print F(x): (default) or costFunction:

DebugCost(prefix,print)

set a prefix manually.

DebugDivider <: DebugAction

print a small divider (default " | ").

Constructor

DebugDivider(div,print)

DebugEntry <: RecordAction

print a certain fields entry of type {T} during the iterates

Addidtional Fields

• field – Symbol the entry can be accessed with within Options

Constructor

DebugEntry(f[, prefix="$f:", print=print])

DebugEntryChange{T} <: DebugAction

print a certain entries change during iterates

Additional Fields

• print – (print) function to print the result
• prefix – ("Change of :x") prefix to the print out
• field – Symbol the field can be accessed with within Options
• distance – function (p,o,x1,x2) to compute the change/distance between two values of the entry
• storage – a StoreOptionsAction to store the previous value of :f

Constructors

DebugEntryChange(f,d[, a, prefix, print])

initialize the Debug to a field f and a distance d.

DebugEntryChange(v,f,d[, a, prefix="Change of $f:", print])

initialize the Debug to a field f and a distance d with initial value v for the history of o.field.

DebugEvery <: DebugAction

evaluate and print debug only every $i$th iteration. Otherwise no print is performed. Whether internal variables are updates is determined by alwaysUpdate.

This method does not perform any print itself but relies on it's childrens print.

DebugIterate <: DebugAction

debug for the current iterate (stored in o.x).

Parameters

• long::Bool whether to print x: or current iterate

DebugIteration <: DebugAction

debug for the current iteration (prefixed with #)

DebugOptions <: Options

The debug options append to any options a debug functionality, i.e. they act as a decorator pattern. Internally a Dictionary is kept that stores a DebugAction for several occasions using a Symbol as reference. The default occasion is :All and for example solvers join this field with :Start, :Step and :Stop at the beginning, every iteration or the end of the algorithm, respectively

The original options can still be accessed using the getOptions function.

Fields (defaults in brackets)

• options – the options that are extended by debug information
• debugDictionary – a Dict{Symbol,DebugAction} to keep track of Debug for different actions

Constructors

DebugOptions(o,dA)

construct debug decorated options, where dD can be

• a DebugAction, then it is stored within the dictionary at :All
• an Array of DebugActions, then it is stored as a debugDictionary within :All.
• a Dict{Symbol,DebugAction}.
• an Array of Symbols, String and an Int for the DebugFactory

DebugStoppingCriterion <: DebugAction

print the Reason provided by the stopping criterion. Usually this should be empty, unless the algorithm stops.

DebugActionFactory(s)

create a DebugAction where

• a Stringyields the correspoinding divider
• a DebugAction is passed through
• a [Symbol] creates DebugEntry of that symbol, with the exceptions of :Change, :Iterate, :Iteration, and :Cost.

DebugFactory(a)

given an array of Symbols, Strings DebugActions and Ints

• The symbol :Stop creates an entry of to display the stoping criterion at the end (:Stop => DebugStoppingCriterion())
• The symbol :Cost creates a DebugCost
• The symbol :iteration creates a DebugIteration
• The symbol :Change creates a DebugChange
• any other symbol creates debug output of the corresponding field in Options
• any string creates a DebugDivider
• any DebugAction is directly included
• an Integer kintroduces that debug is only printed every kth iteration

RecordAction

A RecordAction is a small functor to record values. The usual call is given by (p,o,i) -> s that performs the record based on a Problem p, Options o and the current iterate i.

By convention i<=0 is interpreted as "For Initialization only", i.e. only initialize internal values, but not trigger any record, the same holds for i=typemin(Inf) which is used to indicate stop, i.e. that the record is called from within stopSolver! which returns true afterwards.

Fields (assumed by subtypes to exist)

• recordedValues an Array of the recorded values.

RecordChange <: RecordAction

debug for the amount of change of the iterate (stored in o.x of the Options) during the last iteration.

Additional Fields

• storage a StoreOptionsAction to store (at least) o.x to use this as the last value (to compute the change)

RecordCost <: RecordAction

record the current cost function value, see getCost.

RecordEntry{T} <: RecordAction

record a certain fields entry of type {T} during the iterates

Fields

• recordedValues – the recorded Iterates
• field – Symbol the entry can be accessed with within Options

RecordEntryChange{T} <: RecordAction

record a certain entries change during iterates

Additional Fields

• recordedValues – the recorded Iterates
• field – Symbol the field can be accessed with within Options
• distance – function (p,o,x1,x2) to compute the change/distance between two values of the entry
• storage – a StoreOptionsAction to store (at least) getproperty(o, d.field)

RecordEvery <: RecordAction

record only every $i$th iteration. Otherwise (optionally, but activated by default) just update internal tracking values.

This method does not perform any record itself but relies on it's childrens methods

RecordIterate <: RecordAction

record the iterate

Constructors

RecordIterate(x0)

initialize the iterate record array to the type of x0, e.g. your initial data.

RecordIterate(P)

initialize the iterate record array to the data type P, where P<:MPointholds.

RecordIteration <: RecordAction

record the current iteration

RecordOptions <: Options

append to any Options the decorator with record functionality, Internally a Dictionary is kept that stores a RecordAction for several occasions using a Symbol as reference. The default occasion is :All and for example solvers join this field with :Start, :Step and :Stop at the beginning, every iteration or the end of the algorithm, respectively

The original options can still be accessed using the getOptions function.

Fields

• options – the options that are extended by debug information
• recordDictionary – a Dict{Symbol,RecordAction} to keep track of all different recorded values

Constructors

RecordOptions(o,dR)

construct record decorated Options, where dR can be

• a RecordAction, then it is stored within the dictionary at :All
• an Array of RecordActions, then it is stored as a recordDictionary(@ref) within the dictionary at :All.
• a Dict{Symbol,RecordAction}.

RecordActionFactory(s)

create a RecordAction where

• a RecordAction is passed through
• a [Symbol] creates RecordEntry of that symbol, with the exceptions of :Change, :Iterate, :Iteration, and :Cost.

RecordFactory(a)

given an array of Symbols and RecordActions and Ints

• The symbol :Cost creates a RecordCost
• The symbol :iteration creates a RecordIteration
• The symbol :Change creates a RecordChange
• any other symbol creates a RecordEntry of the corresponding field in Options
• any RecordAction is directly included
• an Integer k introduces that record is only performed every kth iteration

getRecord(o[,s=:Step])

return the recorded values from within the RecordOptions o that where recorded with respect to the Symbol s as an Array. The default refers to any recordings during an Iteration represented by the Symbol :Step

getRecord(r)

return the recorded values stored within a RecordAction r.

ArmijoLineseach <: Linesearch

A functor representing Armijo line seach including the last runs state, i.e. a last step size.

Fields

• initialStepsize – (1.0) and initial step size
• retraction – (exp) the rectraction used in line search
• contractionFactor – (0.95) exponent for line search reduction
• sufficientDecrease – (0.1) gain within Armijo's rule
• lastStepSize – (initialstepsize) the last step size we start the search with

Constructor

ArmijoLineSearch()

with the Fields above in their order as optional arguments.

This method returns the functor to perform Armijo line search, where two inter faces are available:

• based on a tuple (p,o,i) of a GradientProblem p, Options o and a current iterate i.
• with (M,x,F,∇Fx[,η=-∇Fx]) -> s where Manifold M, a current MPoint x a function F, that maps from the manifold to the reals, its gradient (a TVector) ∇F$=\nabla F(x)$ at x and an optional search direction TVector η-∇F are the arguments.

DecreasingStepsize()

A functor that represents several decreasing step sizes

Fields

• length – (1) the initial step size $l$.
• factor – (1) a value $f$ to multiply the initial step size with every iteration
• subtrahend – (0) a value $a$ that is subtracted every iteration
• exponent – (1) a value $e$ the current iteration numbers $e$th exponential is taken of

In total the complete formulae reads for the $i$th iterate as

$ s_i = \frac{(l-i\cdot a)f^i}{i^e}$

and hence the default simplifies to just $ s_i = \frac{l}{i} $

Constructor

ConstantStepSize(l,f,a,e)

initialiszes all fields above, where none of them is mandatory.

CostProblem <: Problem

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

Fields

• M – a manifold $\mathcal M$
• costFunction – a function $F\colon\mathcal M\to\mathbb R$ to minimize

See also

NelderMead

GradientProblem <: Problem

specify a problem for gradient based algorithms.

Fields

• M – a manifold $\mathcal M$
• costFunction – a function $F\colon\mathcal M\to\mathbb R$ to minimize
• gradient – the gradient $\nabla F\colon\mathcal M \to \mathcal T\mathcal M$ of the cost function $F$

See also

steepestDescent GradientDescentOptions

getGradient(p,x)

evaluate the gradient of a HessianProblemp at the MPoint x.

SubGradientProblem <: Problem

A structure to store information about a subgradient based optimization problem

Fields

• M – a Manifold
• costFunction – the function $F$ to be minimized
• subGradient – a function returning a subgradient $\partial F$ of $F$

ProximalProblem <: Problem

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

Fields

• M - a Manifold $\mathcal M$
• costFunction - a function $F\colon\mathcal M\to\mathbb R$ to minimize
• proximalMaps - proximal maps $\operatorname{prox}_{\lambda\varphi}\colon\mathcal M\to\mathcal M$ as functions (λ,x) -> y, i.e. the prox parameter λ also belongs to the signature of the proximal map.
• numberOfProxes - (length(proximalMaps)) number of proxmal Maps, e.g. if one of the maps is a compined one such that the proximal Maps functions return more than one entry per function

See also

cyclicProximalPoint, getCost, getProximalMap

getProximalMap(p,λ,x,i)

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

HessianProblem <: Problem

specify a problem for hessian based algorithms.

Fields

• M : a manifold $\mathcal M$
• costFunction : a function $F\colon\mathcal M\to\mathbb R$ to minimize
• gradient : the gradient $\nabla F\colon\mathcal M \to \mathcal T\mathcal M$ of the cost function $F$
• hessian : the hessian $\operatorname{Hess}[F] (\cdot)_ {x} \colon \mathcal T_{x} \mathcal M \to \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

truncatedConjugateGradient, trustRegions

getHessian(p,x,ξ)

evaluate the Hessian of a HessianProblem p at the MPoint x applied to a TVector ξ.

getPreconditioner(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 MPoint xapplied to a TVector ξ.