Krasnoselskii Mann Increasing Step Sizes

Source file

wc_krasnoselskii_mann_increasing_step_sizes(n; solver=Clarabel.Optimizer, verbose=true)

Problem statement

Compute a PEPit worst-case guarantee for wc_krasnoselskii_mann_increasing_step_sizes.

Consider the fixed point problem

\[\mathrm{Find}\, x:\, x = Ax,\]

where $A$ is a non-expansive operator, that is a $L$-Lipschitz operator with $L=1$.

Performance metric

This code computes a worst-case guarantee for the Krasnolselskii-Mann method. That is, it computes the smallest possible $\tau(n)$ such that the guarantee

\[\frac{1}{4}\|x_n - Ax_n\|^2 \leqslant \tau(n) \|x_0 - x_\star\|^2\]

is valid, where $x_n$ is the output of the KM method, and $x_\star$ is some fixed point of $A$ (i.e., $x_\star=Ax_\star$).

Algorithm

The KM method is described by

\[x_{t+1} = \frac{1}{t + 2} x_{t} + \left(1 - \frac{1}{t + 2}\right) Ax_{t}.\]

References

This scheme was first studied using PEPs in [1].

[1] F. Lieder (2018). Projection Based Methods for Conic Linear Programming — Optimal First Order Complexities and Norm Constrained Quasi Newton Methods. PhD thesis, HHU Düsseldorf.

Arguments

• n: number of iterations.
• solver: JuMP optimizer constructor used to solve the generated SDP.
• verbose: print example and solver progress information when true.

Returns

• pepit_tau: worst-case value
• theoretical_tau: no theoretical value

Julia usage

pepit_tau, theoretical_tau = wc_krasnoselskii_mann_increasing_step_sizes(3; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.119634, nothing)