Krasnoselskii Mann Constant Step Sizes
wc_krasnoselskii_mann_constant_step_sizes(n, gamma; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_krasnoselskii_mann_constant_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 (KM) method with constant step-size. 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 constant step-size KM method is described by
\[x_{t+1} = \left(1 - \gamma\right) x_{t} + \gamma Ax_{t}.\]
Theoretical guarantee
A theoretical upper bound is provided by [1, Theorem 4.9]
\[\tau(n) = \left\{ \begin{aligned} \frac{1}{n+1}\left(\frac{n}{n+1}\right)^n \frac{1}{4 \gamma (1 - \gamma)}\quad & \text{if } \frac{1}{2}\leqslant \gamma \leqslant \frac{1}{2}\left(1+\sqrt{\frac{n}{n+1}}\right) \\ (\gamma - 1)^{2n} \quad & \text{if } \frac{1}{2}\left(1+\sqrt{\frac{n}{n+1}}\right) < \gamma \leqslant 1. \end{aligned} \right.\]
References
Arguments
n: number of iterations.gamma: step-size parameter.solver: JuMP optimizer constructor used to solve the generated SDP.verbose: print example and solver progress information when true.
Returns
pepit_tau: worst-case valuetheoretical_tau: theoretical value
Julia usage
pepit_tau, theoretical_tau = wc_krasnoselskii_mann_constant_step_sizes(3, 3 / 4; verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.140625, 0.140625)