Write $w_k=(x_k,z_k)$ and $w_{k+1}=(x_{k+1},z_{k+1})$. Expanding
$$
M w_{k+1}+F(w_{k+1})=Mw_k
$$
gives
$$
\begin{aligned}
\alpha x_{k+1}+A^Tz_{k+1}
+\nabla f(x_{k+1})-A^Tz_{k+1}
&=\alpha x_k+A^Tz_k,\\
Ax_{k+1}+\beta z_{k+1}
+Ax_{k+1}-b
&=Ax_k+\beta z_k.
\end{aligned}
$$
The off-diagonal terms in the first equation cancel. By the optimality condition for the <proximal operator>,
$$
\boxed{
x_{k+1}
=\operatorname{prox}_{\alpha^{-1}f}
\left(x_k+\alpha^{-1}A^Tz_k\right).}
$$
The second equation then becomes the explicit linear update
$$
\boxed{
z_{k+1}
=z_k+\beta^{-1}\bigl(Ax_k-2Ax_{k+1}+b\bigr).}
$$
Thus each step of this <preconditioned proximal point algorithm> uses only one evaluation of the <proximal operator> of $\alpha^{-1}f$, together with applications of the <linear map> $A$ and its <matrix transpose>[transpose] $A^T$.

Solution

Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 339 / 2 / e / Solution

 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/iii/paper-339/2/e/solution