Accelerated Proximal Point
wc_accelerated_proximal_point(alpha::Real, n::Int; solver=Clarabel.Optimizer, verbose::Int=1)Problem statement
Compute a PEPit worst-case guarantee for wc_accelerated_proximal_point.
Consider the monotone inclusion problem
\[\mathrm{Find}\, x:\, 0\in Ax,\]
where $A$ is maximally monotone. We denote $J_A = (I + A)^{-1}$ the resolvent of $A$.
Performance metric
This code computes a worst-case guarantee for the accelerated proximal point method proposed in [1]. That, it computes the smallest possible $\tau(n, \alpha)$ such that the guarantee
\[\|x_n - y_n\|^2 \leqslant \tau(n, \alpha) \|x_0 - x_\star\|^2,\]
is valid, where $x_\star$ is such that $0 \in Ax_\star$.
Algorithm
Accelerated proximal point is described as follows, for $t \in \{ 0, \dots, n-1\}$
\[ \begin{aligned} x_{t+1} & = & J_{\alpha A}(y_t), \\ y_{t+1} & = & x_{t+1} + \frac{t}{t+2}(x_{t+1} - x_{t}) - \frac{t}{t+2}(x_t - y_{t-1}), \end{aligned}\]
where $x_0=y_0=y_{-1}$
Theoretical guarantee
A tight theoretical worst-case guarantee can be found in [1, Theorem 4.1], for $n \geqslant 1$,
\[\|x_n - y_{n-1}\|^2 \leqslant \frac{1}{n^2} \|x_0 - x_\star\|^2.\]
References
Arguments
alpha: algorithm parameter used in the update rule.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
wc_accelerated_proximal_point(2.0, 10; verbose=1)
## Returns approximately: (τ_PEPit, τ_theory) = (0.01, 0.01)