Two-block ADMM residual, objective and dual sequence convergence

The left saddle inequality forces $K{x}_{\ast }+L{z}_{\ast }=c$: otherwise taking $y=y_{\ast }+t(K{x}_{\ast }+L{z}_{\ast }-c)$ and letting $t\to +\mathrm{\infty }$ contradicts its finite upper bound. The right saddle inequality then says every feasible pair has objective at least $p_{\ast }$, so $(x_{\ast },z_{\ast })$ is primal optimal. For every $y$, the dual value $d(y)$ is at most $\mathcal{L}((x_{\ast },z_{\ast }),y)=p_{\ast }$. At $y_{\ast }$, the right saddle inequality gives $d(y_{\ast })\ge p_{\ast }$; hence $d(y_{\ast })=p_{\ast }$ and $y_{\ast }$ is dual optimal.

The subgradient inequalities underlying [F3] imply, for every fixed $x,z$ and every sweep, $f(x)+g(z)+⟨y^{k+1},Kx+Lz-c⟩\ge p_{k+1}+⟨y^{k+1},r^{k+1}⟩+\rho ⟨L\mathrm{\Delta }{z}^{k+1},Kx-K{x}^{k+1}⟩\mathrm{.}$ Indeed, apply the $f$- and $g$-subgradient inclusions [F8] at the new iterates, use their defining inequalities, add them, and substitute $K{x}^{k+1}+L{z}^{k+1}-c=r^{k+1}$.

Fixing $z=z_{\ast }$ and then $x=x_{\ast }$ in the right saddle inequality gives $-K^{\ast }{y}_{\ast }\in \mathrm{\partial }f(x_{\ast })$ and $-L^{\ast }{y}_{\ast }\in \mathrm{\partial }g(z_{\ast })$. By [F6], $f(x_{\ast })+f^{\ast }(-K^{\ast }{y}_{\ast })=-⟨y_{\ast },K{x}_{\ast }⟩,g(z_{\ast })+g^{\ast }(-L^{\ast }{y}_{\ast })=-⟨y_{\ast },L{z}_{\ast }⟩\mathrm{.}$ Each component infimum is below a finite value because $f,g$ are proper, so neither equals $+\mathrm{\infty }$. If both are finite, choosing independent points within any $ϵ>0$ of them proves that the joint infimum is their sum; if either is $-\mathrm{\infty }$, fixing a finite competitor in the other block and sending the first block value down shows the joint infimum is $-\mathrm{\infty }$. Thus separating the $x$ and $z$ infima and using [F4] gives the extended-real identity $d(y)=-f^{\ast }(-K^{\ast }y)-g^{\ast }(-L^{\ast }y)-⟨y,c⟩\mathrm{.}$ The terms are well-defined because [F5] excludes $-\mathrm{\infty }$ conjugate values. Substituting the two equalities and feasibility into the formula gives $d(y_{\ast })=p_{\ast }$. The dual solution set $Y_{\ast }:=\{y:d(y)=p_{\ast }\}$ is nonempty. Weak duality gives $d(y)\le p_{\ast }$, so $y\in Y_{\ast }$ iff $\mathcal{L}((x,z),y)\ge p_{\ast }$ for every $x,z$. Each finite-valued pair $(x,z)$ imposes a closed affine half-space in $y$; an infinite-valued pair imposes no restriction. Thus $Y_{\ast }$ is closed and convex as an intersection of closed convex sets.

Sum the descent inequality [F3] from $k=1$ to $N$. Since $V^{N+1}\ge 0$, ${\sum }_{k=1}^N(\mathrm{\parallel }{r}^{k+1}{\mathrm{\parallel }}_2^2+\mathrm{\parallel }L\mathrm{\Delta }{z}^{k+1}{\mathrm{\parallel }}_2^2)\le V^1\mathrm{/}\rho \mathrm{.}$ Each nonnegative term of a convergent bounded partial sum tends to zero, so $r^k\to 0$ and $L\mathrm{\Delta }{z}^k\to 0$. The energy bound also makes $y^k$ and $L(z^k-z_{\ast })$ bounded.

The objective estimates [F3] now force convergence. In the upper estimate, $⟨y^{k+1},r^{k+1}⟩\to 0$ by boundedness and residual convergence; both terms paired with $L\mathrm{\Delta }{z}^{k+1}$ tend to zero because $r^{k+1}\to 0$ and $L(z^{k+1}-z_{\ast })$ is bounded. The lower estimate $p_{\ast }-p_{k+1}\le ⟨y_{\ast },r^{k+1}⟩$ also tends to zero. Hence $p_{k+1}\to p_{\ast }$.

Along any convergent subsequence $y^{k_j+1}\to \bar{y}$, the quantities $K{x}^{k_j+1}=c-L{z}^{k_j+1}+r^{k_j+1}$ are bounded by step 2.2. Taking limits in step 1.2, using steps 2.2 and 3.1, gives $f(x)+g(z)+⟨\bar{y},Kx+Lz-c⟩\ge p_{\ast }\text{for all }x,z\mathrm{.}$ Since the primal optimizer is feasible, $d(\bar{y})\ge p_{\ast }$, while weak duality from step 1.1 gives $d(\bar{y})\le p_{\ast }$. Thus every dual cluster point belongs to $Y_{\ast }$. The inequality at the fixed primal optimizer also makes it a saddle point with $\bar{y}$.

If $p=0$, then ${\mathbb{R}}^p=\{0\}$ by [F10], so $y^k=0$ for every $k$; step 2.1 shows this unique dual vector is optimal, and dual convergence follows. Assume henceforth $p\ge 1$. Boundedness from step 2.2 and [F7] give at least one dual cluster point. Let $y_1,y_2\in Y_{\ast }$ be any two cluster points. Each pairs with the same primal optimizer to form a saddle point, so [F3] makes both energy sequences $V^k(y_i)={\rho }^{-1}\mathrm{\parallel }{y}^k-y_i{\mathrm{\parallel }}_2^2+\rho \mathrm{\parallel }L(z^k-z_{\ast }){\mathrm{\parallel }}_2^2(i=1,2)$ nonincreasing from $k=1$ and bounded below; each therefore converges. Expanding the two squared norms gives $V^k(y_1)-V^k(y_2)=\frac{2}{\rho }⟨y^k,y_2-y_1⟩+\frac{\mathrm{\parallel }{y}_1{\mathrm{\parallel }}_2^2-\mathrm{\parallel }{y}_2{\mathrm{\parallel }}_2^2}{\rho },$ so $⟨y^k,y_2-y_1⟩$ converges. Along subsequences tending to $y_1$ and $y_2$ the limits are equal, so $⟨y_1-y_2,y_2-y_1⟩=-\mathrm{\parallel }{y}_1-y_2{\mathrm{\parallel }}_2^2=0$ and $y_1=y_2$.

In the remaining case $p\ge 1$, there is exactly one cluster point. If the bounded sequence $y^k$ did not converge to it, some subsequence would stay a fixed positive distance away; [F7] would give a convergent subsubsequence with a different cluster point, a contradiction. Therefore the whole unscaled dual sequence converges to a point of $Y_{\ast }$. No convergence of primal iterates was used.