Averaged Projections
wc_averaged_projections(n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_averaged_projections.
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 averaged 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 averaged 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 averaged projection method can be written as
\[ \begin{aligned} x_{t+1} & = & \frac{1}{2} \left(\mathrm{Proj}_{Q_1}(x_t) + \mathrm{Proj}_{Q_2}(x_t)\right). \end{aligned}\]
References
No specific bibliographic reference is associated with this example.
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_averaged_projections(10; solver=Clarabel.Optimizer, verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.068432, nothing)