A Convergent $3$-Block Semi-Proximal ADMM for Convex Minimization Problems with One Strongly Convex Block

Introduction

We consider the following separable convex minimization problem whose objective function is the sum of three functions without coupled variables:

where ${\cal X}_{i}$ ($i=1,2,3$) and ${\cal Z}$ are real finite dimensional Euclidean spaces each equipped with an inner product $\langle\cdot,\cdot\rangle$ and its induced norm $\|\cdot\|$, $\theta_{i}:{\cal X}_{i}\rightarrow(-\infty,+\infty]$ ($i=1,2,3$) are closed proper convex functions, $A_{i}^{*}:{\cal X}_{i}\rightarrow{\cal Z}$ is the adjoint of the linear operator $A_{i}:{\cal Z}\to{\cal X}_{i}$, $i=1,2,3$, and $c\in{\cal Z}$. Since $\theta_{i}$, $i=1,2,3$, are closed proper convex functions, there exist self-adjoint and positive semi-definite operators $\Sigma_{i}$, $i=1,2,3$, such that

where $\partial\theta_{i}$ is the sub-differential mapping of $\theta_{i}$, $i=1,2,3$. The solution set of problem (1) is assumed to be nonempty throughout our discussions in this paper.

Let $\sigma>0$ be a given penalty parameter and $z\in{\cal Z}$ be the Lagrange multiplier associated with the linear equality constraint in problem (1). For any $(x_{1},x_{2},x_{3})\in{\cal X}_{1}\times{\cal X}_{2}\times{\cal X}_{3}$, write $x\equiv(x_{1},x_{2},x_{3})$, $\theta(x)\equiv\theta_{1}(x_{1})+\theta_{2}(x_{2})+\theta_{3}(x_{3})$ and $A^{*}x\equiv A_{1}^{*}x_{1}+A_{2}^{*}x_{2}+A_{3}^{*}x_{3}$. Then the augmented Lagrangian function for problem (1) is defined by

for any $(x_{1},x_{2},x_{3},z)\in{\cal X}_{1}\times{\cal X}_{2}\times{\cal X}_{3}\times{\cal Z}$. The direct extension of the classical alternating direction method of multipliers (ADMM) for solving problem (1) consists of the following iterations for $k=0,1,\ldots$

where $\tau>0$ is the step-length. Different from the $2$-block ADMM whose convergence has been established for a long time , the $3$-block ADMM may not converge in general, which was demonstrated by Chen, He, Ye and Yuan using counterexamples. Nevertheless, if all the functions $\theta_{i}$, $i=1,2,3$, are strongly convex, Han and Yuan proved the global convergence of the $3$-block ADMM scheme (4) with $\tau=1$ (Han and Yuan actually considered the general $m$-block case for any $m\geq 3$. Here and below we focus on the $3$-block case only) under the condition that

where $\lambda_{\max}(S)$ is the largest eigenvalue of a given self-adjoint linear operator $S$. Hong and Luo proposed to adopt a small step-length $\tau$ when updating the Lagrange multiplier $z^{k+1}$ in (4). Chen, Shen and You proposed the following sufficient condition

for the global convergence of the directly extended $3$-block ADMM with $\tau=1$ for solving problem (1). Closely related to the work of Chen, Shen and You , in , Lin, Ma and Zhang provided an analysis on the iteration complexity for the same method under the condition

In , under additional assumptions including some smoothness conditions, the same group of authors further proved the global linear convergence of the mentioned method.

The purpose of this work is to extend the $2$-block semi-proximal ADMM studied in to deal with problem (1) by only assuming $\theta_{2}$ to be strongly convex, i.e., $\Sigma_{2}\succ 0$. Note that the semi-proximal ADMM with $\tau>1$ often works better in practice than its counterpart with $\tau\leq 1$. So it is desirable to establish the convergence of the proposed semi-proximal ADMM that allows $\tau$ to stay in the larger region $(0,(1+\sqrt{5})/2)$.

One of our motivating examples is the following convex quadratic conic programming

where ${\cal K}$ is a nonempty closed convex cone in a finite dimensional real Euclidean space ${\cal X}$ endowed with an inner product $\langle\cdot,\,\cdot\rangle$ and its induced norm $\|\cdot\|$, ${\cal Q}:{\cal X}\to{\cal X}$ is a self-adjoint and positive semi-definite linear operator, ${\cal A}:{\cal X}\rightarrow\Re^{m}$ is a linear map, $C\in{\cal X}$ and $b\in\Re^{m}$ are given data. The dual of problem (7) takes the form of

where ${\cal K}^{*}:=\{v\in{\cal X}:\langle v,w\rangle\geq 0\;\forall\,w\in{\cal K}\}$ is the dual cone of ${\cal K}$. Since ${\cal Q}$ is self-adjoint and positive semi-definite, ${\cal Q}$ can be decomposed as ${\cal Q}={\cal L}^{*}{\cal L}$ for some linear map ${\cal L}$. By introducing a new variable $\Xi=-{\cal L}X^{\prime}$, we can re-write problem (8) equivalently as

where $\delta_{\Re^{m}_{+}}(\cdot)$ and $\delta_{{\cal K}^{*}}(\cdot)$ are the indicator functions of $\Re^{m}_{+}$ and ${\cal K}^{*}$, respectively. As one can see, problem (11) has only one strongly convex block, i.e., the block with respect to $\Xi$. Consequently, the results in the aforementioned papers for the convergence analysis of the directly extended 3-block ADMM applied to solving problem (11) are no longer valid. We shall show in the next section that our proposed 3-block semi-proximal ADMM can exactly solve this kind of problems. When ${\cal K}={\cal S}_{+}^{n}$, the cone of symmetric and positive semi-definite matrices in the space ${\cal S}^{n}$ of $n\times n$ symmetric matrices, problem (11) is a convex quadratic semidefinite programming problem that has been extensively studied both theoretically and numerically in the literature , to name only a few.

The remaining parts of this paper are organized as follows. In the next section, we first present our $3$-block semi-proximal ADMM and then provide the main convergence results. We give some concluding remarks in the final section.

The effective domain of a function $f$: ${\cal X}\rightarrow(-\infty,+\infty]$ is defined as $\hbox{dom}(f):=\{x\in{\cal X}\;|\;f(x)<+\infty\}$. The set of all relative interior points of a given nonempty convex set ${\cal C}$ is denoted by ri$(\cal C)$.

For convenience, for any given $x$, we use $\|x\|_{G}^{2}$ to denote $\langle x,Gx\rangle$ if $G$ is a self-adjoint linear operator in a given finite dimensional Euclidean space ${\cal X}$. If $\Sigma:{\cal X}\to{\cal X}$ is a self-adjoint and positive semi-definite linear operator, we use $\Sigma^{\frac{1}{2}}$ to denote the unique self-adjoint and positive semi-definite square root of $\Sigma$.

A 333-Block Semi-Proximal ADMM

Based on our previous introduction and motivation, we propose our $3$-block semi-proximal ADMM for solving problem (1) in the following:

Algorithm sPADMM: A 3-block semi-proximal ADMM for solving problem (1). Let $\sigma\in(0,+\infty)$ and $\tau\in(0,+\infty)$ be given parameters. Let $T_{i}$, $i=1,2,3$, be given self-adjoint and positive semi-definite linear operators defined on ${\cal X}_{i}$, $i=1,2,3$, respectively. Choose $(x_{1}^{0},x_{2}^{0},x_{3}^{0},z^{0})\in\hbox{dom}(\theta_{1})\times\hbox{dom}(\theta_{2})\times\hbox{dom}(\theta_{3})\times{\cal Z}$ and set $k=0$. Step 1. Compute \left\{\begin{array}[]{l}\displaystyle x_{1}^{k+1}:=\operatorname*{argmin}_{x_{1}\in{\cal X}_{1}}\bigl{\{}{\cal L}_{\sigma}(x_{1},x_{2}^{k},x_{3}^{k};z^{k})+\frac{1}{2}\|x_{1}-x_{1}^{k}\|_{T_{1}}^{2}\bigr{\}},\\ \displaystyle x_{2}^{k+1}:=\operatorname*{argmin}_{x_{2}\in{\cal X}_{2}}\bigl{\{}{\cal L}_{\sigma}(x_{1}^{k+1},x_{2},x_{3}^{k};z^{k})+\frac{1}{2}\|x_{2}-x_{2}^{k}\|_{T_{2}}^{2}\bigr{\}},\\ \displaystyle x_{3}^{k+1}:=\operatorname*{argmin}_{x_{3}\in{\cal X}_{3}}\bigl{\{}{\cal L}_{\sigma}(x_{1}^{k+1},x_{2}^{k+1},x_{3};z^{k})+\frac{1}{2}\|x_{3}-x_{3}^{k}\|_{T_{3}}^{2}\bigr{\}},\\ z^{k+1}:=z^{k}+\tau\sigma(A^{*}x^{k+1}-c).\end{array}\right. (14) Step 2. If a termination criterion is not met, set $k:=k+1$ and then goto Step 1.

In order to analyze the convergence properties of Algorithm sPADMM, we make the following assumptions.

The convex function $\theta_{2}$ satisfies (2) with $\Sigma_{2}\succ 0$.

The self-adjoint and positive semi-definite operators $T_{i}$, $i=1,2,3$, are chosen such that the sequence $\{(x_{1}^{k},x_{2}^{k},x_{3}^{k},z^{k})\}$ generated by Algorithm sPADMM is well defined.

There exists $x^{\prime}=(x_{1}^{\prime},x_{2}^{\prime},x_{3}^{\prime})\in\hbox{ri}(\hbox{dom}(\theta_{1})\times\hbox{dom}(\theta_{2})\times\hbox{dom}(\theta_{3}))\bigcap P$, where

Under Assumption 2.3, it follows from [19, Corollary 28.2.2] and [19, Corollary 28.3.1] that $\bar{x}=(\bar{x}_{1},\bar{x}_{2},\bar{x}_{3})\in{\cal X}_{1}\times{\cal X}_{2}\times{\cal X}_{3}$ is an optimal solution to problem (1) if and only if there exists a Lagrange multiplier $\bar{z}\in{\cal Z}$ such that

Moreover, any $\bar{z}\in{\cal Z}$ satisfying (15) is an optimal solution to the dual of problem (1).

Let $\bar{x}=(\bar{x}_{1},\bar{x}_{2},\bar{x}_{3})\in{\cal X}_{1}\times{\cal X}_{2}\times{\cal X}_{3}$ and $\bar{z}\in{\cal Z}$ satisfy (15). For the sake of convenience, define for $(x_{1},u,z):=(x_{1},(x_{2},x_{3}),z)\in{\cal X}_{1}\times({\cal X}_{2}\times{\cal X}_{3})\times{\cal Z}$, $\alpha\in(0,1]$ and $k=0,1,\ldots$, the following quantities

To prove the convergence of Algorithm sPADMM for solving problem (1), we first present some useful lemmas.

Assume that Assumptions 2.1, 2.2 and 2.3 hold. Let $\{(x_{1}^{k},x_{2}^{k},x_{3}^{k},z^{k})\}$ be generated by Algorithm sPADMM. Then, for any $\tau\in(0,+\infty)$ and integer $k\geq 0$, we have

where $\overline{\phi}_{k}$, $s_{k+1}$ and $r^{k+1}$ are defined as in (16).

Proof. The sequence $\{(x_{1}^{k},x_{2}^{k},x_{3}^{k},z^{k})\}$ is well defined under Assumption 2.2. Notice that the iteration scheme (14) of Algorithm sPADMM can be re-written as for $k=0,1,\ldots$ that

Combining (2) with (15) and (18), and using the definitions of $x_{ie}^{k+1}$ and $\Delta x_{i}^{k}$, for $i=1,2,3$, we have

For any vectors $a,b,d$ in the same Euclidean vector space and any self-adjoint linear operator $G$, we have the identity

Taking $a=x_{i}^{k+1}$, $b=\bar{x}_{i}$, $d=x_{i}^{k}$ and $G=T_{i}$ in the above identity, and using the definitions of $x_{ie}^{k+1}$ and $\Delta x_{i}^{k}$, we get

Substituting (20) and (21) into (19) and using the definition of $\Delta x_{j}^{k}$, for $i=1,2$, we have

By simple manipulations and using $A_{1}^{*}x_{1e}^{k+1}=A_{1}^{*}x_{1}^{k+1}-A_{1}^{*}\bar{x}_{1}=B^{*}\bar{u}+(A_{1}^{*}x_{1}^{k+1}-c)$, we get

For any vectors $a,b,d,e$ in the same Euclidean vector space, we have the identity

Using the Cauchy-Schwarz inequality, for the parameter $\alpha\in(0,1]$, we get

Substituting (2), (28) and (29) into (2), we obtain

From the elementary inequality $\|a\|^{2}+\|b\|^{2}\geq\|a-b\|^{2}/2$ and $x_{ie}^{k+1}-x_{ie}^{k}=\Delta x_{i}^{k}$, it follows that

By simple manipulations and using the definition of $z_{e}^{k}$, we get

By using (18), (21) and the definitions of $z_{e}^{k}$ and $r^{k+1}$, we have

Substituting (2) and (33) into (2), and using the definitions of $\overline{\phi}_{k}$, $s_{k+1}$ and $r^{k+1}$, we get the assertion (17). The proof is complete. $\Box$

Assume that Assumptions 2.1 and 2.2 hold. Let $\{(x_{1}^{k},x_{2}^{k},x_{3}^{k},z^{k})\}$ be generated by Algorithm sPADMM. Then, for any $\tau\in(0,+\infty)$ and integer $k\geq 1$, we have

where $\Delta u^{k}$, $\Delta x_{i}^{k}$ $(i=2,3)$ and $r^{k+1}$ are defined as in (16).

By using (18) and the definition of $\Delta x_{2}^{k}$, we have

By using the Cauchy-Schwarz inequality, we obtain

Adding up the above two inequalities, we get

Using $z^{k-1}-z^{k}=-\tau\sigma r^{k}$ and the definitions of $v^{k}$ and $r^{k}$, we have

Substituting the above equation into (35), we get

Similarly as for deriving (36), we can obtain that

Adding up the above inequality and (36), and using the definitions of $B^{*}$ and $u$, we get the assertion (2.2). The proof is complete. $\Box$

Assume that Assumptions 2.1 and 2.2 hold. Let $\{(x_{1}^{k},x_{2}^{k},x_{3}^{k},z^{k})\}$ be generated by Algorithm sPADMM. For any $\tau\in(0,+\infty)$ and integer $k\geq 1$, we have

where $s_{k+1}$, $t_{k+1}$, $\xi_{k+1}$ and $r^{k+1}$ are defined as in (16).

Proof. By simple manipulations and using the definition of $r^{k+1}$, we obtain

By the Cauchy-Schwarz inequality, for the parameter $\alpha\in(0,1]$, we have

Substituting the above inequality into (2), we get

By using the definitions of $s_{k+1}$ and $t_{k+1}$, and the fact that

Substituting the above equation into (2) and using the definition of $\xi_{k+1}$, we get

By using the Cauchy-Schwarz inequality, we get

Substituting (42) into (2), we obtain from simple manipulations that

The assertion (37) is proved immediately. $\Box$

Now, we are ready to prove the convergence of the sequence $\{(x_{1}^{k},x_{2}^{k},x_{3}^{k},z^{k})\}$ generated by Algorithm sPADMM.

Assume that Assumptions 2.1, 2.2 and 2.3 hold. Let $\{(x_{1}^{k},x_{2}^{k},x_{3}^{k},z^{k})\}$ be generated by Algorithm sPADMM. Then, for any $\tau\in(0,+\infty)$ and integer $k\geq 1$, we have

where $\overline{\phi}_{k}$, $\xi_{k+1}$, $t_{k+1}$ and $r^{k}$ are defined as in (16). Assume that $\tau\in(0,(1+\sqrt{5})/2)$. If for some $\alpha\in(0,1]$ it holds that

then the whole sequence $\{(x_{1}^{k},x_{2}^{k},x_{3}^{k})\}$ converges to an optimal solution to problem (1) and $\{z^{k}\}$ converges to an optimal solution to the dual of problem (1).

Proof. By substituting (37) into (17), we can easily get (2.1).

Assume that $\tau\in(0,(1+\sqrt{5})/2)$. Since (44) holds for some $\alpha\in(0,1]$, we have $\min(\tau,1+\tau-\tau^{2})>0$, $H\succ 0$ and $M\succ 0$. From (2.1), we see immediately that the sequence $\{\overline{\phi}_{k+1}\}$ is bounded, $\lim_{k\rightarrow\infty}t_{k+1}=0$ and $\lim_{k\rightarrow\infty}\|r^{k+1}\|=0$, i.e.,

as $k\rightarrow\infty$. Now from (45) and (47), we obtain

Recall that $\frac{1}{2}\Sigma_{1}+T_{1}+\sigma A_{1}A_{1}^{*}\succ 0$. Thus it follows from (48) that

By the definition of $\overline{\phi}_{k+1}$, we see that the three sequences $\{\|z_{e}^{k+1}\|\}$, $\{\|x_{1e}^{k+1}\|_{\Sigma_{1}+T_{1}}\}$, and $\{\|u_{e}^{k+1}\|_{M}\}$ are all bounded. Since $M\succ 0$, the sequences $\{\|x_{2}^{k+1}\|\}$ and $\{\|x_{3}^{k+1}\|\}$ are also bounded. Furthermore, by using

we also know that the sequence $\{\|A_{1}^{*}x_{1e}^{k+1}\|\}$ is bounded, and so is the sequence $\{\|x_{1e}^{k+1}\|_{(\Sigma_{1}+T_{1}+\sigma A_{1}A_{1}^{*})}\}$. This shows that the sequence $\{\|x_{1}^{k+1}\|\}$ is also bounded as the operator $\Sigma_{1}+T_{1}+\sigma A_{1}A_{1}^{*}\succeq\frac{1}{2}\Sigma_{1}+T_{1}+\sigma A_{1}A_{1}^{*}\succ 0.$ Thus, the sequence $\{(x_{1}^{k},x_{2}^{k},x_{3}^{k},z^{k})\}$ is bounded.

Since the sequence $\{(x_{1}^{k},x_{2}^{k},x_{3}^{k},z^{k})\}$ is bounded, there is a subsequence $\{(x_{1}^{k_{i}},x_{2}^{k_{i}},x_{3}^{k_{i}},z^{k_{i}})\}$ which converges to a cluster point, say $\{(x_{1}^{\infty},x_{2}^{\infty},x_{3}^{\infty},z^{\infty})\}$. Taking limits on both sides of (18) along the subsequence $\{(x_{1}^{k_{i}},x_{2}^{k_{i}},x_{3}^{k_{i}},z^{k_{i}})\}$, using (45), (46) and (49), we obtain that

i.e., $(x_{1}^{\infty},x_{2}^{\infty},x_{3}^{\infty},z^{\infty})$ satisfies (15). Thus $\{(x_{1}^{\infty},x_{2}^{\infty},x_{3}^{\infty})\}$ is an optimal solution to (1) and ${z^{\infty}}$ is an optimal solution to the dual of problem (1).

To complete the proof, we show next that $(x_{1}^{\infty},x_{2}^{\infty},x_{3}^{\infty},z^{\infty})$ is actually the unique limit of $\{(x_{1}^{k},x_{2}^{k},x_{3}^{k},z^{k})\}$. Replacing $(\bar{x}_{1},\bar{u},\bar{z}):=(\bar{x}_{1},(\bar{x}_{2},\bar{x}_{3}),\bar{z})$ by $(x_{1}^{\infty},u^{\infty},z^{\infty}):=(x_{1}^{\infty},(x_{2}^{\infty},x_{3}^{\infty}),z^{\infty})$ in (2.1), for any integer $k\geq k_{i}$, we have

Since $M\succ 0$, we also have that $\lim_{k\rightarrow\infty}u^{k}=u^{\infty}$, that is $\lim_{k\rightarrow\infty}x_{2}^{k}=x_{2}^{\infty}$ and $\lim_{k\rightarrow\infty}x_{3}^{k}=x_{3}^{\infty}$. Using the fact that $\lim_{k\rightarrow\infty}\|r^{k+1}\|=0$ and $\lim_{k\rightarrow\infty}\|u^{k+1}-u^{\infty}\|=0$, we get from (50) that $\lim_{k\rightarrow\infty}\|A_{1}^{*}(x_{1}^{k+1}-x_{1}^{\infty})\|=0$. Thus

Since $\Sigma_{1}+T_{1}+\sigma A_{1}A_{1}^{*}\succ 0$, we also obtain that $\lim_{k\rightarrow\infty}x_{1}^{k}=x_{1}^{\infty}$. Therefore, we have shown that the sequence $\{(x_{1}^{k},x_{2}^{k},x_{3}^{k})\}$ converges to an optimal solution to (1) and $\{z^{k}\}$ converges to an optimal solution to the dual of problem (1) for any $\tau\in(0,(1+\sqrt{5})/2)$. The proof is complete. $\Box$

Assume that $(1-\alpha)\Sigma_{2}+\sigma A_{2}A_{2}^{*}$ is invertible for some $\alpha\in(0,1]$. Set $\tau=1$ (the case that $1\neq\tau\in(0,(1+\sqrt{5})/2)$ can be discussed in a similar but slightly more complicated manner) and $T_{2}=0$ in (12) and (13). Then the assumptions $H\succ 0$ and $M\succ 0$ in (44) reduce to

in terms of the Schur-complement format. The conditions (52) and (53) can be satisfied easily by choosing a proper $T_{3}$ for given $\alpha\in(0,1]$ and $\sigma\in(0,+\infty)$. Evidently, with a fixed $\alpha$, $T_{3}$ can take a smaller value with a smaller $\sigma$ and $T_{3}$ can even take the zero operator for any $\sigma>0$ smaller than a certain threshold if $\Sigma_{3}+(1-\alpha)\sigma A_{3}A_{3}^{*}\succ 0$. To see this, let us consider the following example constructed in :

which is a convex minimization problem with three strongly convex functions. In , Chen, He, Ye and Yuan showed that the directly extended $3$-block ADMM scheme (4) with $\tau=\sigma=1$ applied to problem (62) is divergent. For problem (62), $\Sigma_{1}=\Sigma_{2}=\Sigma_{3}=\frac{1}{10}$, $A_{1}=(1,1,1)$, $A_{2}=(1,1,2)$ and $A_{3}=(1,2,2)$. From (52) and (53), by taking $\alpha=1$, we have that $T_{3}$ and $\sigma$ should satisfy the following conditions

which hold true, in particular, if $T_{3}=0$ and $\sigma<\frac{1+\sqrt{1765}}{2940}\approx 0.015$ or if $\sigma=1$ and $T_{3}>\frac{14687}{12}\approx 1223.92$.

If $A_{2}^{*}$ is vacuous, then for any integer $k\geq 0$, we have that $x_{2}^{k+1}=x_{2}^{0}=\bar{x}_{2}$, the $3$-block sPADMM is just a $2$-block sPADMM, and condition (44) reduces to

since $\Sigma_{1}\succeq 0$, $T_{1}\succeq 0$, $\Sigma_{3}\succeq 0$ and $T_{3}\succeq 0$. Condition (63) is exactly the same as the one used in Theorem B.1. in .

Conclusions

In this paper, we provided a convergence analysis about a $3$-block semi-proximal ADMM for solving separable convex minimization problems with the condition that the second block in the objective is strongly convex. The step-length $\tau$ in our proposed semi-proximal ADMM is allowed to stay in the desirable region $(0,(1+\sqrt{5})/2)$. From Remark 2.1, we know that with a fixed parameter $\alpha\in(0,1]$, the added semi-proximal terms can be chosen to be small if the penalty parameter $\sigma$ is small. If $A_{1}^{*}$ and $A_{3}^{*}$ are both injective and $\sigma>0$ is taken to be smaller than a certain threshold, then the convergent $3$-block semi-proximal ADMM includes the directly extended $3$-block ADMM with $\tau\in(0,(1+\sqrt{5})/2)$ by taking $T_{i}$, $i=1,2,3$, to be zero operators. With no much difficulty, one could extend our $3$-block semi-proximal ADMM to deal with the $m$-block ($m\geq 4$) separable convex minimization problems possessing $m-2$ strongly convex blocks and provide the iteration complexity analysis for the corresponding algorithm in the sense of . In this work, we choose not to do the extension because we are not aware of interesting applications of the $m$-block ($m\geq 4$) separable convex minimization problems with $m-2$ strongly convex blocks. While our sufficient condition bounding the range of values for $\sigma$ and $T_{3}$ is quite flexible, it may have one potential limitation: $T_{3}$ can be very large if $\sigma$ is not small as shown in Remark 2.1. Since a larger $T_{3}$ can potentially make the algorithm converge slower, we do not feel that the study on the iteration complexity is of significance at the moment unless of course the above potential limitation is completely circumvented.

References