Cyclic Proximal Point

Cyclic Proximal Point

The Cyclic Proximal Point (CPP) algorithm is a Proximal Problem.

It aims to minimize

\[F(x) = \sum_{i=1}^c f_i(x)\]

assuming that the proximal maps $\operatorname{prox}_{\lambda f_i}(x)$ are given in closed form or can be computed efficiently (at least approximately).

The algorithm then cycles through these proximal maps, where the type of cycle might differ and the proximal parameter $\lambda_k$ changes after each cycle $k$.

For a convergence result on Hadamard manifolds see [Bačák, 2014].

Manopt.cyclicProximalPoint — Function.
cyclicProximalPoint(M, F, proximalMaps, x)

perform a cyclic proximal point algorithm.

Input

  • M – a manifold $\mathcal M$
  • F – a cost function $F\colon\mathcal M\to\mathbb R$ to minimize
  • proximalMaps – an Array of proximal maps (Functions) (λ,x) -> y for the summands of $F$
  • x – an initial value $x\in\mathcal M$

Optional

the default values are given in brackets

  • evaluationOrder – ( LinearEvalOrder ) – whether to use a randomly permuted sequence (FixedRandomEvalOrder), a per cycle permuted sequence (RandomEvalOrder) or the default linear one.
  • λ – ( iter -> 1/iter ) a function returning the (square summable but not summable) sequence of λi
  • stoppingCriterion – (stopWhenAny(stopAfterIteration(5000),stopWhenChangeLess(10.0^-8))) a StoppingCriterion.
  • returnOptions – (false) – if actiavated, the extended result, i.e. the complete Options are returned. This can be used to access recorded values. If set to false (default) just the optimal value xOpt if returned

and the ones that are passed to decorateOptions for decorators.

Output

  • xOpt – the resulting (approximately critical) point of gradientDescent

OR

  • options - the options returned by the solver (see returnOptions)
source
Manopt.CyclicProximalPointOptions — Type.
CyclicProximalPointOptions <: Options

stores options for the cyclicProximalPoint algorithm. These are the

Fields

  • x0 – an MPoint to start
  • stoppingCriterion – a function @(iter,x,xnew,λ_k) based on the current iter, x and xnew as well as the current value of λ.
  • λ – (@(iter) -> 1/iter) a function for the values of λ_k per iteration/cycle
  • evaluationOrder – (LinearEvalOrder()) how to cycle through the proximal maps. Other values are RandomEvalOrder() that takes a new random order each iteration, and FixedRandomEvalOrder() that fixes a random cycle for all iterations.

See also

cyclicProximalPoint

source

Debug Functions

Manopt.DebugProximalParameter — Type.
DebugProximalParameter <: DebugAction

print the current iterates proximal point algorithm parameter given by Optionss o.λ.

source

Record Functions

Manopt.RecordProximalParameter — Type.
RecordProximalParameter <: RecordAction

recoed the current iterates proximal point algorithm parameter given by in Optionss o.λ.

source

Literature