Halpern Iteration
wc_halpern_iteration(n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_halpern_iteration.
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 Halpern Iteration, and looks for a low-dimensional worst-case example nearly achieving this worst-case guarantee. That is, it computes the smallest possible $\tau(n)$ such that the guarantee
\[\|x_n - Ax_n\|^2 \leqslant \tau(n) \|x_0 - x_\star\|^2\]
is valid, where $x_n$ is the output of the Halpern iteration, and $x_\star$ the fixed point of $A$.
In short, for a given value of $n$, $\tau(n)$ is computed as the worst-case value of $\|x_n - Ax_n\|^2$ when $\|x_0 - x_\star\|^2 \leqslant 1$. Then, it looks for a low-dimensional nearly achieving this performance.
Algorithm
The Halpern iteration can be written as
\[x_{t+1} = \frac{1}{t + 2} x_0 + \left(1 - \frac{1}{t + 2}\right) Ax_t.\]
Theoretical guarantee
A tight worst-case guarantee for Halpern iteration can be found in [1, Theorem 2.1]:
\[\|x_n - Ax_n\|^2 \leqslant \left(\frac{2}{n+1}\right)^2 \|x_0 - x_\star\|^2.\]
References
The detailed approach and tight bound are available in [1].
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 valuetheoretical_tau: theoretical value
Julia usage
pepit_tau, theoretical_tau = wc_halpern_iteration(10; solver=Clarabel.Optimizer, verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.033048, 0.033058)