Two-block ADMM energy descent and objective gap estimates

For every $x\in \mathrm{dom}f$, the right saddle inequality at $(x,z_{\ast })$ and feasibility give $f(x)\ge f(x_{\ast })+⟨-K^{\ast }{y}_{\ast },x-x_{\ast }⟩$; the same argument with $(x_{\ast },z)$ gives $-L^{\ast }{y}_{\ast }\in \mathrm{\partial }g(z_{\ast })$. Thus [F4] gives both saddle subgradient inclusions. For $k\ge 1$, the preceding exact sweep also gives $-L^{\ast }{y}^k\in \mathrm{\partial }g(z^k)$ from [F2]. The inequalities at $z^{k+1}$ and $z^k$ read $g(z^{k+1})-g(z^k)\le -⟨y^{k+1},L\mathrm{\Delta }{z}^{k+1}⟩$ and $g(z^{k+1})-g(z^k)\ge -⟨y^k,L\mathrm{\Delta }{z}^{k+1}⟩$. Combining them gives $⟨y^{k+1}-y^k,L\mathrm{\Delta }{z}^{k+1}⟩\le 0$. This is the sign needed below and is why the estimate starts at $k=1$.

Adding the two defining subgradient inequalities shows subgradient monotonicity. At the $f$-block this gives $0\le ⟨a^{k+1}+K^{\ast }{y}_{\ast },x^{k+1}-x_{\ast }⟩=-⟨y^{k+1}-y_{\ast },K(x^{k+1}-x_{\ast })⟩+\rho ⟨L\mathrm{\Delta }{z}^{k+1},K(x^{k+1}-x_{\ast })⟩\mathrm{.}$ At the $g$-block it gives $0\le ⟨b^{k+1}+L^{\ast }{y}_{\ast },z^{k+1}-z_{\ast }⟩=-⟨y^{k+1}-y_{\ast },L(z^{k+1}-z_{\ast })⟩$. Add the two inequalities and use $K{x}_{\ast }+L{z}_{\ast }=c$ to obtain $⟨y^{k+1}-y_{\ast },r^{k+1}⟩\le \rho ⟨L\mathrm{\Delta }{z}^{k+1},K(x^{k+1}-x_{\ast })⟩\mathrm{.}$ Substitute $K(x^{k+1}-x_{\ast })=r^{k+1}-L(z^{k+1}-z_{\ast })$.

The identity $y^{k+1}-y^k=\rho r^{k+1}$ gives $\frac{\mathrm{\parallel }{y}^{k+1}-y_{\ast }{\mathrm{\parallel }}^2-\mathrm{\parallel }{y}^k-y_{\ast }{\mathrm{\parallel }}^2}{\rho }=2⟨y^{k+1}-y_{\ast },r^{k+1}⟩-\rho \mathrm{\parallel }{r}^{k+1}{\mathrm{\parallel }}^2\mathrm{.}$ The analogous expansion for $L(z^k-z_{\ast })$ is $\rho (\mathrm{\parallel }L(z^{k+1}-z_{\ast }){\mathrm{\parallel }}^2-\mathrm{\parallel }L(z^k-z_{\ast }){\mathrm{\parallel }}^2)=2\rho ⟨L\mathrm{\Delta }{z}^{k+1},L(z^{k+1}-z_{\ast })⟩-\rho \mathrm{\parallel }L\mathrm{\Delta }{z}^{k+1}{\mathrm{\parallel }}^2\mathrm{.}$ Add these identities, use step 2.1, and then use step 1.1 to bound $2⟨y^{k+1}-y^k,L\mathrm{\Delta }{z}^{k+1}⟩\le 0$. The asserted energy descent follows.

The two subgradient inequalities [F2,F4] at $(x^{k+1},z^{k+1})$ against $(x_{\ast },z_{\ast })$ give $p_{k+1}-p_{\ast }\le ⟨a^{k+1},x^{k+1}-x_{\ast }⟩+⟨b^{k+1},z^{k+1}-z_{\ast }⟩=-⟨y^{k+1},r^{k+1}⟩+\rho ⟨L\mathrm{\Delta }{z}^{k+1},K(x^{k+1}-x_{\ast })⟩\mathrm{.}$ Replace $K(x^{k+1}-x_{\ast })$ by $r^{k+1}-L(z^{k+1}-z_{\ast })$ to obtain the upper estimate. The right saddle inequality [F3] at $(x^{k+1},z^{k+1})$ is $p_{k+1}+⟨y_{\ast },r^{k+1}⟩\ge p_{\ast }$, which rearranges to the lower estimate.