Proximal Point
wc_proximal_point(alpha, n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_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 resolvents of $A$.
Performance metric
This code computes a worst-case guarantee for the proximal point method, and looks for a low-dimensional worst-case example nearly achieving this worst-case guarantee using the trace heuristic.
That is, it computes the smallest possible $\tau(n, \alpha)$ such that the guarantee
\[\|x_n - x_{n-1}\|^2 \leqslant \tau(n, \alpha) \|x_0 - x_\star\|^2,\]
is valid, where $x_\star$ is such that $0 \in Ax_\star$. Then, it looks for a low-dimensional nearly achieving this performance.
Algorithm
The proximal point algorithm for monotone inclusions is described as follows, for $t \in \{ 0, \dots, n-1\}$,
\[x_{t+1} = J_{\alpha A}(x_t),\]
where $\alpha$ is a step-size.
Theoretical guarantee
A tight theoretical guarantee can be found in [1, section 4].
\[\|x_n - x_{n-1}\|^2 \leqslant \frac{\left(1 - \frac{1}{n}\right)^{n - 1}}{n} \|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 value.theoretical_tau: theoretical value.
Julia usage
pepit_tau, theoretical_tau = wc_proximal_point(2.2, 11; solver=Clarabel.Optimizer, verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.035039, 0.035049)