Alternate Projections
wc_alternate_projections(n; solver=Clarabel.Optimizer, verbose=true)Problem statement
Compute a PEPit worst-case guarantee for wc_alternate_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 alternate 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 alternate 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 alternate projection method can be written as
\[ \begin{aligned} y_{t+1} & = & \mathrm{Proj}_{Q_1}(x_t), \\ x_{t+1} & = & \mathrm{Proj}_{Q_2}(y_{t+1}). \end{aligned}\]
References
The first results on this method are due to [1]. Its translation in PEPs is due to [2].
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_alternate_projections(10; solver=Clarabel.Optimizer, verbose=true)
## Returns approximately: (pepit_tau, theoretical_tau) = (0.01885, nothing)