Operator splitting ADMM and primal dual methods — Examples

Write the columns of $A$ as $a_1=(1,1,1{)}^T$, $a_2=(1,1,2{)}^T$, $a_3=(1,2,2{)}^T$. Their squared norms are $3,6,9$, so every scalar block subproblem has a strictly positive quadratic coefficient and a unique attained minimizer. Also $detA=-1$, so $Ax=0$ has only $x=0$. The dual function is $d(y)=in{f}_x⟨y,Ax⟩$: it is $0$ when $A^{T}y=0$ and $-\mathrm{\infty }$ otherwise. Since $A$ is invertible, $A^{T}y=0$ only for $y=0$, so the dual optimum is unique.

For state $s^k=(x_2^k,x_3^k,u_1^k,u_2^k,u_3^k{)}^T$, exact differentiation of the three scalar subproblems gives $x_1^{k+1}=-\frac{a_1^T(u^k+a_2{x}_2^k+a_3{x}_3^k)}{3}$, $x_2^{k+1}=-\frac{a_2^T(u^k+a_1{x}_1^{k+1}+a_3{x}_3^k)}{6}$, and $x_3^{k+1}=-\frac{a_3^T(u^k+a_1{x}_1^{k+1}+a_2{x}_2^{k+1})}{9}$. Substitute these into $u^{k+1}=u^k+a_1{x}_1^{k+1}+a_2{x}_2^{k+1}+a_3{x}_3^{k+1}$; exact rational simplification gives $s^{k+1}=M{s}^k$ with $M=\frac{1}{162}\left(\begin{array}{ccccc}144& -9& 9& 9& -18\\ 8& 157& 5& -13& 8\\ -64& -122& 122& -58& -64\\ -56& 35& -35& 91& -56\\ 88& 26& -26& -62& 88\end{array}\right)\mathrm{.}$ The vector $v=(0,0,1,1,1{)}^T$ satisfies $Mv=0$. Exact rational matrix multiplication gives $p_1=\mathrm{tr}(M)=\frac{301}{81}$, $p_2=\mathrm{tr}(M^2)=\frac{20860}{6561}$, $p_3=\mathrm{tr}(M^3)=\frac{2588159}{1062882}$, and $p_4=\mathrm{tr}(M^4)=\frac{132553799}{86093442}$. Newton's identities $e_1=p_1$, $e_2=(p_1^2-p_2)\mathrm{/}2$, $e_3=(p_3-e_1{p}_2+e_2{p}_1)\mathrm{/}3$, and $e_4=(-p_4+e_1{p}_3-e_2{p}_2+e_3{p}_1)\mathrm{/}4$ give $e_1=301\mathrm{/}81$, $e_2=287\mathrm{/}54$, $e_3=280\mathrm{/}81$, $e_4=70\mathrm{/}81$; $Mv=0$ gives $e_5=\det M=0$. Therefore $\det (\lambda I-M)=\lambda q(\lambda )$, where $q(\lambda )={\lambda }^4-\frac{301}{81}{\lambda }^3+\frac{287}{54}{\lambda }^2-\frac{280}{81}\lambda +\frac{70}{81}$.

For $z=e^{it}$, direct expansion gives $\mathrm{Im}(e^{-2it}q(e^{it}))=\frac{\sin t(22\cos t-21)}{81}$. If this vanishes because $\sin t=0$, substitution gives $q(1)=1\mathrm{/}162$ and $q(-1)=775\mathrm{/}54$, both nonzero. Otherwise $\cos t=21\mathrm{/}22$, and substitution into the real part gives $\mathrm{Re}(e^{-2it}q(e^{it}))=19\mathrm{/}19602\mathrm{\ne }0$. Thus $q$ has no unit-circle zero.

Suppose every zero of $q$ lies inside the unit disk. By [F2], its normalized Schur reduction is the stable monic cubic $q_1(z)=z^3-\frac{4781}{1661}{z}^2+\frac{861}{302}z-\frac{1610}{1661}$. Since $\mathrm{\mid }{q}_1(0)\mathrm{\mid }=1610\mathrm{/}1661<1$, another application gives the stable monic quadratic $q_2(z)=z^2-\frac{317086}{166821}z+\frac{336511}{333642}$. By [F3], $q_2$ factors as $(z-{\zeta }_1)(z-{\zeta }_2)$ over $\mathbb{C}$, with both roots inside the unit disk by the reductions. Its constant term is ${\zeta }_1{\zeta }_2$, so $\mathrm{\mid }{q}_2(0)\mathrm{\mid }=\mathrm{\mid }{\zeta }_1\mathrm{\mid }\mathrm{\mid }{\zeta }_2\mathrm{\mid }<1$, contradicting $q_2(0)=336511\mathrm{/}333642>1$. Therefore not all zeros of $q$ lie inside. The coefficients of $q_1,q_2$ follow by substituting into $(p-p(0)p^{\mathrm{\#}})\mathrm{/}(z(1-p(0{)}^2))$ and collecting powers.

By [F3], $q$ has four roots counted with multiplicity. Steps 2.1 and 3.1 show that none is on the unit circle and not all are inside, so some root $\lambda$ satisfies $\mathrm{\mid }\lambda \mathrm{\mid }>1$. Since $\det (\lambda I-M)=\lambda q(\lambda )=0$ by step 1.2, [F4] gives a nonzero complex vector $v$ with $Mv=\lambda v$. Suppose each of the five standard basis vectors $e_j\in {\mathbb{Q}}^5$ had a bounded orbit under $M$. Then every column of $M^k$ would be uniformly bounded in $k$, and since there are only five columns, every entry would be bounded by one common constant $C$. Choose $i$ with $v_i\mathrm{\ne }0$. The finite-sum triangle inequality would give $\mathrm{\mid }(M^{k}v{)}_i\mathrm{\mid }\le C{\sum }_j\mathrm{\mid }{v}_j\mathrm{\mid }$ for every $k$, but $M^{k}v={\lambda }^{k}v$ makes $\mathrm{\mid }(M^{k}v{)}_i\mathrm{\mid }=\mathrm{\mid }\lambda {\mathrm{\mid }}^k\mathrm{\mid }{v}_i\mathrm{\mid }\to \mathrm{\infty }$, a contradiction. Hence at least one standard basis vector has an unbounded orbit. Taking $s^0=e_j$ for that index and $x_1^0=0$ gives a rational initial state with unbounded iterates; each subproblem remains uniquely attained as shown in step 1.1.

On the feasible set $z=x$, the objective is $f(x)+g(x)=\frac{1}{2}(x-1{)}^2+\frac{1}{2}(x+1{)}^2=x^2+1,$ which is uniquely minimized at $x=z=0$ with value $1$. For $y_{\ast }=1$, $\mathcal{L}((x,z),1)=f(x)+g(z)+x-z=1+\frac{1}{2}{x}^2+\frac{1}{2}{z}^2\ge 1,$ with equality at $(0,0)$; feasibility makes $\mathcal{L}((0,0),y)=1$ for every $y$. These are exactly the saddle inequalities [F2].

Differentiating the first strictly convex quadratic in [F1] gives $2x^{k+1}=1+z^k-u^k$. At $k=0$ this yields $x^1=1\mathrm{/}2$. Differentiating the second gives $2z^{k+1}=x^{k+1}+u^k-1$, hence $z^1=-1\mathrm{/}4$ and then $u^1=u^0+x^1-z^1=3\mathrm{/}4$.

The equality matrix is $A=(1,-1)$, whose single row is linearly independent, so the dual definition [F3] applies. Its dual function is $d(y)={\inf }_x\{\frac{1}{2}(x-1{)}^2+yx\}+{\inf }_z\{\frac{1}{2}(z+1{)}^2-yz\}=(y-\frac{1}{2}{y}^2)+(y-\frac{1}{2}{y}^2)=1-(y-1{)}^2\mathrm{.}$ Thus its maximum is $1$ at $y=1$, consistent with weak duality [F4] and the saddle value.

The same two equations give $x^2=(1-1\mathrm{/}4-3\mathrm{/}4)\mathrm{/}2=0$, $z^2=(0+3\mathrm{/}4-1)\mathrm{/}2=-1\mathrm{/}8$, and $u^2=3\mathrm{/}4+0-(-1\mathrm{/}8)=7\mathrm{/}8$. Each subproblem is a strictly convex quadratic, so both minimizers in each of these sweeps are attained and unique. The recurrence values are exact rationals.

Since $Kb=e_1=b$, every power $K^{j}b=b$. For $m=0$, the spanning list is empty and its span is $\{0\}$, with no nonzero vector on which to evaluate a Rayleigh quotient. For every $m\ge 1$, the spanning set in [F1] consists of repetitions of the single nonzero vector $e_1$, and the Rayleigh quotient on this one-dimensional subspace is $e_1^{T}K{e}_1\mathrm{/}(e_1^T{e}_1)=1$. Exact Lanczos terminates after one vector with Ritz value $1$.

For $x=(x_1,x_2)$, $\mathrm{\parallel }Kx{\mathrm{\parallel }}_2^2=x_1^2+4x_2^2\le 4(x_1^2+x_2^2)$, with equality at $e_2$, so [F4] gives $\mathrm{\parallel }K{\mathrm{\parallel }}_2=2$. The top eigenspace is $\mathrm{span}\{e_2\}$ and $Pb=0$; [F2] identifies exactly this degenerate branch and supplies no top-eigenvalue convergence bound. Therefore the Ritz value $1$ is not the norm upper bound $2$ required by [F3].

The record has valid row pointers $0=r_0\le r_1=2=s$ and valid columns $0,1$. By [F2,F3], its exact matrix-vector product is $-x_0+x_1$; its transpose sends $y$ to $(-y,y)$. By [F4], its stored-entry count is $s=2$, slot count is $6$, and the exact operation count is two multiplications, two additions, and one output initialization.

The conjugate of $g(v)=\mathrm{\mid }v\mathrm{\mid }$ is the indicator of $[-1,1]$: if $\mathrm{\mid }y\mathrm{\mid }\le 1$, then $yv-\mathrm{\mid }v\mathrm{\mid }\le 0$ for every $v$ and equality occurs at $v=0$; if $y>1$, taking $v\to +\mathrm{\infty }$ makes the supremum infinite, and if $y<-1$, taking $v\to -\mathrm{\infty }$ does so. Therefore ${\mathrm{prox}}_{\sigma g^{\ast }}$ is Euclidean projection onto $[-1,1]$. Also, direct completion of squares gives ${\mathrm{prox}}_{\tau f}(w)=\frac{w+\tau (1,0)}{1+\tau }\mathrm{.}$

Initially $K{\bar{x}}^0=0$, so $y^1={\mathrm{proj}}_{[-1,1]}(0)=0$, then $x^1=(0+(1\mathrm{/}2)(1,0))\mathrm{/}(3\mathrm{/}2)=(1\mathrm{/}3,0)$. Thus ${\bar{x}}^1=(2\mathrm{/}3,0)$ and $y^2={\mathrm{proj}}_{[-1,1]}((1\mathrm{/}2)K{\bar{x}}^1)={\mathrm{proj}}_{[-1,1]}(-1\mathrm{/}3)=-1\mathrm{/}3$.

Since $K^T{y}^2=(1\mathrm{/}3,-1\mathrm{/}3)$, $x^2=\frac{x^1-(1\mathrm{/}2)K^T{y}^2+(1\mathrm{/}2)(1,0)}{3\mathrm{/}2}=\frac{(1\mathrm{/}6,1\mathrm{/}6)+(1\mathrm{/}2,0)}{3\mathrm{/}2}=(4\mathrm{/}9,1\mathrm{/}9)\mathrm{.}$ Finally, for any $(a,b)$, $\mathrm{\parallel }K(a,b){\mathrm{\parallel }}_2^2=(-a+b{)}^2\le 2(a^2+b^2)$ with equality at $(a,b)=(1,-1)\mathrm{/}\sqrt{2}$. Hence $\mathrm{\parallel }K{\mathrm{\parallel }}_2^2=2$ by [F5] and $\tau \sigma \mathrm{\parallel }K{\mathrm{\parallel }}_2^2=(1\mathrm{/}4)2=1\mathrm{/}2<1$, so the step-size hypothesis of [F6] is satisfied.