Optimal Contractive Halpern Iteration
wc_optimal_contractive_halpern_iteration(n, gamma; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_optimal_contractive_halpern_iteration.
Consider the fixed point problem
\[\mathrm{Find}\, x:\, x = Ax,\]
where $A$ is a $1/\gamma$-contractive operator, i.e. a $L$-Lipschitz operator with $L=1/\gamma$.
Performance metric
This code computes a worst-case guarantee for the Optimal Contractive Halpern Iteration. That is, it computes the smallest possible $\tau(n, \gamma)$ such that the guarantee
\[\|x_n - Ax_n\|^2 \leqslant \tau(n, \gamma) \|x_0 - x_\star\|^2\]
is valid, where $x_n$ is the output of the Optimal Contractive Halpern iteration, and $x_\star$ is the fixed point of $A$. In short, for a given value of $n, \gamma$, $\tau(n, \gamma)$ is computed as the worst-case value of $\|x_n - Ax_n\|^2$ when $\|x_0 - x_\star\|^2 \leqslant 1$.
Algorithm
The Optimal Contractive Halpern iteration can be written as
\[x_{t+1} = \left(1 - \frac{1}{\varphi_{t+1}} \right) Ax_t + \frac{1}{\varphi_{t+1}} x_0.\]
where $\varphi_k = \sum_{i=0}^k \gamma^{2i}$ and $x_0$ is a starting point.
Theoretical guarantee
A tight worst-case guarantee for the Optimal Contractive Halpern iteration can be found in [1, Corollary 3.3, Theorem 4.1]:
\[\|x_n - Ax_n\|^2 \leqslant \left(1 + \frac{1}{\gamma}\right)^2 \left( \frac{1}{\sum_{k=0}^n \gamma^k} \right)^2 \|x_0 - x_\star\|^2.\]
References
The detailed approach and tight bound are available in [1].
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_optimal_contractive_halpern_iteration(10, 1.1; solver=Clarabel.Optimizer, verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.010613, 0.010613)