Douglas Rachford Splitting
wc_douglas_rachford_splitting(L, alpha, theta, n; verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_douglas_rachford_splitting.
Consider the composite convex minimization problem
\[F_\star \triangleq \min_x \{F(x) \equiv f_1(x)+f_2(x) \}\]
where $f_1(x)$ is is convex, closed and proper , and $f_2$ is $L$-smooth. Both proximal operators are assumed to be available.
Performance metric
This code computes a worst-case guarantee for the Douglas Rachford Splitting (DRS) method. That is, it computes the smallest possible $\tau(n, L, \alpha, \theta)$ such that the guarantee
\[F(y_n) - F(x_\star) \leqslant \tau(n, L, \alpha, \theta) \|x_0 - x_\star\|^2.\]
is valid, where it is known that $x_k$ and $y_k$ converge to $x_\star$, but not $w_k$ (see definitions in the section # Algorithm ). Hence we require the initial condition on $x_0$ (arbitrary choice, partially justified by the fact we choose $f_2$ to be the smooth function).
Note that $y_n$ is feasible as it has a finite value for $f_1$ (output of the proximal operator on $f_1$) and as $f_2$ is smooth.
Algorithm
Our notations for the DRS method are as follows, for $t \in \{0, \dots, n-1\}$,
\[ \begin{aligned} x_t & = & \mathrm{prox}_{\alpha f_2}(w_t), \\ y_t & = & \mathrm{prox}_{\alpha f_1}(2x_t - w_t), \\ w_{t+1} & = & w_t + \theta (y_t - x_t). \end{aligned}\]
This description can be found in [1, Section 7.3].
Theoretical guarantee
We compare the output with that of PESTO [2] for when $0\leqslant n \leqslant 10$ in the case where $\alpha=\theta=L=1$.
References
Arguments
L: smoothness or Lipschitz parameter, as used by the modeled class.alpha: algorithm parameter used in the update rule.theta: relaxation or averaging parameter used in the update rule.n: number of iterations.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_douglas_rachford_splitting(1.0, 1.0, 1.0, 9; verbose=true)
## Returns approximately: (PEPit_tau, theoretical_tau) = (0.027792, 0.0278)