PDHG one-step primal-dual gap telescope

For each positive-dimensional proximal space, the optimality condition [F2] and extended-real subgradient definition [F3] give the relevant inequality. If a proximal space is zero-dimensional, [F6] says its only point is $0$; its update and test point are both $0$, so the same inequality is equality in that coordinate. Therefore in every dimension the two inequalities are $g^{\ast }(y)-g^{\ast }(y^{k+1})\ge ⟨\frac{y^k-y^{k+1}}{\sigma }+K{\bar{x}}^k,y-y^{k+1}⟩,$ $f(x)-f(x^{k+1})\ge ⟨\frac{x^k-x^{k+1}}{\tau }-K^{\ast }{y}^{k+1},x-x^{k+1}⟩\mathrm{.}$ The identity $-⟨a-b,c-b⟩=(\mathrm{\parallel }c-a{\mathrm{\parallel }}^2-\mathrm{\parallel }c-b{\mathrm{\parallel }}^2-\mathrm{\parallel }b-a{\mathrm{\parallel }}^2)\mathrm{/}2$ applied to the primal and dual displacement terms gives the two distance differences $E_k-E_{k+1}-X_{k+1}$ and $E_k-E_{k+1}-Y_{k+1}$ in their respective coordinates. The bilinear terms from the primal inequality and the gap expand as $⟨y^{k+1},K(x-x^{k+1})⟩+⟨K{x}^{k+1},y⟩-⟨Kx,y^{k+1}⟩=⟨K{x}^{k+1},y-y^{k+1}⟩$. Adding the dual update term $⟨K{\bar{x}}^k,y^{k+1}-y⟩$ gives $⟨K({\bar{x}}^k-x^{k+1}),y^{k+1}-y⟩$ in the upper bound for $G_{k+1}$. Moving this term to the other side yields $E_k\ge G_{k+1}+E_{k+1}+X_{k+1}+Y_{k+1}+⟨K(x^{k+1}-{\bar{x}}^k),y^{k+1}-y⟩,$ where $G_{k+1}=\mathrm{\Phi }(x^{k+1},y)-\mathrm{\Phi }(x,y^{k+1})$, $E_j=\mathrm{\parallel }x-x^j{\mathrm{\parallel }}^2\mathrm{/}(2\tau )+\mathrm{\parallel }y-y^j{\mathrm{\parallel }}^2\mathrm{/}(2\sigma )$, $X_j=\mathrm{\parallel }{x}^j-x^{j-1}{\mathrm{\parallel }}^2\mathrm{/}(2\tau )$, and $Y_j=\mathrm{\parallel }{y}^j-y^{j-1}{\mathrm{\parallel }}^2\mathrm{/}(2\sigma )$.

Define $x^{-1}=x^0$, so $X_0=0$, and $B_k=⟨K(x^k-x^{k-1}),y^k-y⟩$. The extrapolation in [F1] gives $⟨K(x^{k+1}-{\bar{x}}^k),y^{k+1}-y⟩=B_{k+1}-B_k-⟨K(x^k-x^{k-1}),y^{k+1}-y^k⟩\mathrm{.}$ By [F4,F5] and $2ab\le a^2+b^2$, $\mathrm{\mid }⟨K(x^k-x^{k-1}),y^{k+1}-y^k⟩\mathrm{\mid }\le \kappa (X_k+Y_{k+1})\mathrm{.}$ Substitution into step 1.1 therefore gives $E_k\ge G_{k+1}+E_{k+1}+(1-\kappa )Y_{k+1}+X_{k+1}-\kappa X_k+B_{k+1}-B_k\mathrm{.}$

Sum step 2.1 for $k=0,\dots ,N-1$. The $B$ terms telescope, $B_0=0$, and the $X$ terms satisfy ${\sum }_{k=0}^{N-1}(X_{k+1}-\kappa X_k)=(1-\kappa ){\sum }_{k=1}^{N-1}{X}_k+X_N\ge 0$. Thus ${\sum }_{k=0}^{N-1}{G}_{k+1}+E_N+(1-\kappa ){\sum }_{k=1}^N{Y}_k+(1-\kappa ){\sum }_{k=1}^{N-1}{X}_k+X_N+B_N\le E_0\mathrm{.}$ For the terminal cross term, [F4,F5] and $2ab\le a^2+b^2$ give $-B_N\le \mathrm{\parallel }K{\mathrm{\parallel }}_2\mathrm{\parallel }{x}^N-x^{N-1}{\mathrm{\parallel }}_2\mathrm{\parallel }{y}^N-y{\mathrm{\parallel }}_2\le X_N+\tau \sigma \mathrm{\parallel }K{\mathrm{\parallel }}_2^2\frac{\mathrm{\parallel }{y}^N-y{\mathrm{\parallel }}_2^2}{2\sigma }\mathrm{.}$ Since $E_N$ contains $\mathrm{\parallel }{y}^N-y{\mathrm{\parallel }}^2\mathrm{/}(2\sigma )$ and $\tau \sigma \mathrm{\parallel }K{\mathrm{\parallel }}_2^2={\kappa }^2<1$, these terminal terms leave a nonnegative remainder; all increment terms are also nonnegative because $\kappa <1$. Drop them to obtain $\sum G_{k+1}\le E_0$, the claimed estimate. When $K=0$, $\kappa =0$ and the same inequalities hold without division by $\mathrm{\parallel }K{\mathrm{\parallel }}_2$.