Dykstra
wc_dykstra(n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_dykstra.
Consider the convex feasibility problem:
\[\mathrm{Find}\, x\in Q_1\cap Q_2\]
where $Q_1$ and $Q_2$ are two closed convex sets.
Performance metric
This code computes a worst-case guarantee for the Dykstra projection method, 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
\[\|\mathrm{Proj}_{Q_1}(x_n)-\mathrm{Proj}_{Q_2}(x_n)\|^2 \leqslant \tau(n) \|x_0 - x_\star\|^2\]
is valid, where $x_n$ is the output of the Dykstra projection method, and $x_\star\in Q_1\cap Q_2$ is a solution to the convex feasibility problem.
In short, for a given value of $n$, $\tau(n)$ is computed as the worst-case value of $\|\mathrm{Proj}_{Q_1}(x_n)-\mathrm{Proj}_{Q_2}(x_n)\|^2$ when $\|x_0 - x_\star\|^2 \leqslant 1$. Then, it looks for a low-dimensional nearly achieving this performance.
Algorithm
The Dykstra projection method can be written as
\[ \begin{aligned} y_{t} & = & \mathrm{Proj}_{Q_1}(x_t+p_t), \\ p_{t+1} & = & x_t + p_t - y_t,\\ x_{t+1} & = & \mathrm{Proj}_{Q_2}(y_t+q_t),\\ q_{t+1} & = & y_t + q_t - x_{t+1}. \end{aligned}\]
References
This method is due to [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: no theoretical value.
Julia usage
pepit_tau, theoretical_tau = wc_dykstra(10; solver=Clarabel.Optimizer, verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.025746, nothing)