Edit on GitHub

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}_{λ 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 $λ_k$ changes after each cycle $k$.

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

Manopt.cyclic_proximal_point — Function
cyclic_proximal_point(M, F, proxes, x)

perform a cyclic proximal point algorithm.

Input

  • M – a manifold $\mathcal M$
  • F – a cost function $F:\mathcal M→ℝ$ to minimize
  • proxes – an Array of proximal maps (Functions) (λ,x) -> y for the summands of $F$
  • x – an initial value $x ∈ \mathcal M$

Optional

the default values are given in brackets

  • evaluation – (AllocatingEvaluation) specify whether the proximal maps work by allocation (default) form prox(M, λ, x) or MutatingEvaluation in place, i.e. is of the form prox!(M, y, λ, x).
  • evaluation_order – (:Linear) – whether to use a randomly permuted sequence (:FixedRandom), a per cycle permuted sequence (:Random) or the default linear one.
  • λ – ( iter -> 1/iter ) a function returning the (square summable but not summable) sequence of λi
  • stopping_criterion – (StopWhenAny(StopAfterIteration(5000),StopWhenChangeLess(10.0^-8))) a StoppingCriterion.

and the ones that are passed to decorate_options for decorators.

Output

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

source
Manopt.cyclic_proximal_point! — Function
cyclic_proximal_point!(M, F, proxes, x)

perform a cyclic proximal point algorithm in place of x.

Input

  • M – a manifold $\mathcal M$
  • F – a cost function $F:\mathcal M→ℝ$ to minimize
  • proxes – an Array of proximal maps (Functions) (λ,x) -> y for the summands of $F$
  • x – an initial value $x ∈ \mathcal M$

for all options, see cyclic_proximal_point.

source

Options

Manopt.CyclicProximalPointOptions — Type
CyclicProximalPointOptions <: Options

stores options for the cyclic_proximal_point algorithm. These are the

Fields

  • x – the current iterate
  • stopping_criterion – a StoppingCriterion
  • λ – (@(iter) -> 1/iter) a function for the values of λ_k per iteration/cycle
  • oder_type – (:LinearOrder) – whether to use a randomly permuted sequence (:FixedRandomOrder), a per cycle permuted sequence (RandomOrder) or the default linear one.

Constructor

CyclicProximalPointOptions(M, p)

Generate the options with the following keyword arguments

  • stopping_criterion (StopAfterIteration(2000)) – a StoppingCriterion.
  • λ ( (iter) -> 1.0 / iter) a function to compute the $λ_k, k ∈ \mathbb N$,
  • evaluation_order(:LinearOrder) a Symbol indicating the order the proxes are applied.

See also

cyclic_proximal_point

source

Debug Functions

Record Functions

Literature