A Schur Complement Based Semi-Proximal ADMM for Convex Quadratic Conic Programming and Extensions

Introduction

In this paper, we aim to design an efficient yet simple first order convergent method for solving convex quadratic conic programming. An important special case is the following convex quadratic semidefinite programming (QSDP)

where ${\cal S}_{+}^{n}$ is the cone of $n\times n$ symmetric and positive semi-definite matrices in the space of $n\times n$ symmetric matrices ${\cal S}^{n}$ endowed with the standard trace inner product $\langle\cdot,\,\cdot\rangle$ and the Frobenius norm $\|\cdot\|$, ${\cal Q}$ is a self-adjoint positive semidefinite linear operator from ${\cal S}^{n}$ to ${\cal S}^{n}$, ${\cal A}_{E}:{\cal S}^{n}\rightarrow\Re^{m_{E}}$ and ${\cal A}_{I}:{\cal S}^{n}\rightarrow\Re^{m_{I}}$ are two linear maps, $C\in{\cal S}^{n}$, $b_{E}\in\Re^{m_{E}}$ and $b_{I}\in\Re^{m_{I}}$ are given data, ${\cal K}$ is a nonempty simple closed convex set, e.g., ${\cal K}=\{W\in{\cal S}^{n}:\;L\leq W\leq U\}$ with $L,U\in{\cal S}^{n}$ being given matrices. By introducing a slack variable $W\in{\cal S}^{n}$, we can equivalently recast (3) as

where $\delta_{\cal K}(\cdot)$ is the indicator function of ${\cal K}$, i.e., $\delta_{\cal K}(X)=0$ if $X\in{\cal K}$ and $\delta_{\cal K}(X)=\infty$ if $X\notin{\cal K}$. The dual of problem (6) is given by

where for any $Z\in{\cal S}^{n}$, $\delta_{{\cal K}}^{*}(-Z)$ is given by

It is evident that the dual problem (9) is in the form of the following convex optimization model:

where $p$ and $q$ are given nonnegative integers, $f:{\cal U}\rightarrow(-\infty,+\infty]$, $g:{\cal V}\rightarrow(-\infty,+\infty],$ $\theta_{i}:{\cal Y}_{i}\rightarrow(-\infty,+\infty],\,i=1,\ldots,p,$ and $\varphi_{j}:{\cal Z}_{j}\rightarrow(-\infty,+\infty],\,j=1,\ldots,q$ are closed proper convex functions, ${\cal F}:{\cal X}\rightarrow{\cal U},$ ${\cal G}:{\cal X}\rightarrow{\cal V}$, ${\cal A}_{i}:{\cal X}\rightarrow{\cal Y}_{i},\,i=1,\ldots,p$ and ${\cal B}_{j}:{\cal X}\rightarrow{\cal Z}_{j},\,j=1,\ldots,q$ are linear maps, ${\cal U},{\cal V},{\cal Y}_{1},\ldots,{\cal Y}_{p},{\cal Z}_{1},\ldots,{\cal Z}_{q}$ and ${\cal X}$ are all real finite dimensional Euclidean spaces each equipped with an inner product $\langle\cdot,\,\cdot\rangle$ and its induced norm $\|\cdot\|.$

In this paper, we make the following blanket assumption.

For $i=1,\ldots,p$ and $j=1,\ldots,q$, each $\theta_{i}(\cdot)$ and $\varphi_{j}(\cdot)$ are convex quadratic functions.

Note that, in general, problem (9) does not satisfy Assumption 1.1 unless $y_{I}$ is vacuous from the model or ${\cal K}\equiv{\cal S}^{n}$. However, one can always reformulate problem (9) equivalently as

where ${\cal D}:\Re^{m_{I}}\to\Re^{m_{I}}$ is any given nonsingular linear operator and $\delta_{\Re^{m_{I}}_{+}}(\cdot)$ is the indicator function over $\Re^{m_{I}}_{+}$. Now, one can see that problem (17) satisfies Assumption 1.1.

There are many other important cases that take the form of model (13) satisfying Assumption 1.1. One prominent example comes from the matrix completion with fixed basis coefficients . Indeed the nuclear semi-norm penalized least squares model in can be written as

where $\|X\|_{*}$ is the nuclear norm of $X$ defined as the sum of all its singular values, $\|\cdot\|_{\infty}$ is the elementwise $l_{\infty}$ norm defined by $\|X\|_{\infty}:=\max_{i=1,\ldots,m}\{\max_{j=1,\ldots,n}|X_{ij}|\}$, ${\cal A}_{F}:\Re^{m\times n}\to\Re^{n_{F}}$ and ${\cal A}_{E}:\Re^{m\times n}\to\Re^{n_{E}}$ are two linear maps, $\rho$ and $\alpha$ are two given positive parameters, $d\in\Re^{n_{F}}$, $C\in\Re^{m\times n}$ and $b_{E}\in\Re^{n_{E}}$ are given data, $\Omega\subseteq\{1,\ldots,m\}\times\{1,\ldots,n\}$ is the set of the indices relative to which the basis coefficients are not fixed, ${\cal R}_{\Omega}:\Re^{m\times n}\to\Re^{|\Omega|}$ is the linear map such that ${\cal R}_{\Omega}X:=(X_{ij})_{ij\in\Omega}.$ Note that when there are no fixed basis coefficients (i.e., $\Omega=\{1,\ldots,m\}\times\{1,\ldots,n\}$ and ${\cal A}_{E}$ are vacuous), the above problem reduces to the model considered by Negahban and Wainwright in and Klopp in . By introducing slack variables $\eta$, $R$ and $W$, we can reformulate problem (20) as

The dual of problem (23) takes the form of

where $\|S\|_{2}$ is the operator norm of $S$, which is defined to be its largest singular value.

Another compelling example is the so called robust PCA (principle component analysis) considered in :

where $W\in\Re^{m\times n}$ is the observed data matrix, $\|\cdot\|_{1}$ is the elementwise $l_{1}$ norm given by $\|E\|_{1}:=\sum_{i=1}^{m}\sum_{j=1}^{n}|E_{ij}|$, $\|\cdot\|_{F}$ is the Frobenius norm, $\lambda_{1}$ and $\lambda_{2}$ are two positive parameters. There are many different variants to the robust PCA model. For example, one may consider the following model where the observed data matrix $W$ is incomplete:

i.e. one assumes that only a subset $\Omega\subseteq\{1,\ldots,m\}\times\{1,\ldots,n\}$ of the entries of $W$ can be observed. Here ${\cal P}_{\Omega}:\Re^{m\times n}\to\Re^{m\times n}$ is the orthogonal projection operator defined by

Again, problem (32) satisfies Assumption 1.1. In , Tao and Yuan tested one of the equivalent forms of problem (32). In the numerical section, we will see other interesting examples.

For notational convenience, let ${\cal Y}:={\cal Y}_{1}\times{\cal Y}_{2}\times,\ldots,{\cal Y}_{p},$ ${\cal Z}:={\cal Z}_{1}\times{\cal Z}_{2}\times,\ldots,{\cal Z}_{q}$. We write $y\equiv(y_{1},y_{2},\ldots,y_{p})\in{\cal Y}$ and $z\equiv(z_{1},z_{2},\ldots,z_{q})\in{\cal Z}$. Define the linear map ${\cal A}:{\cal X}\rightarrow{\cal Y}$ such that its adjoint is given by

Similarly, we define the linear map ${\cal B}:{\cal X}\rightarrow{\cal Z}$ such that its adjoint is given by

Additionally, let $\theta(y):=\sum_{i=1}^{p}\theta_{i}(y_{i}),$ $y\in{\cal Y}$ and $\varphi(z):=\sum_{j=1}^{q}\varphi_{j}(z_{j})$, $z\in{\cal Z}$. Now we can rewrite (13) in the following compact form:

Problem (13) can be view as a special case of the following block-separable convex optimization problem:

where for each $i\in\{1,\ldots,n\}$, ${\cal W}_{i}$ is a finite dimensional real Euclidean space equipped with an inner product $\langle\cdot,\,\cdot\rangle$ and its induced norm $\|\cdot\|$, $\phi_{i}:{\cal W}_{i}\to(-\infty,+\infty]$ is a closed proper convex function, ${\cal H}_{i}:{\cal X}\to{\cal W}_{i}$ is a linear map and $c\in{\cal X}$ is given. Note that when we rewrite problem (13) in terms of (39), the quadratic structure in (13) is hidden in the sense that each $\phi_{i}$ will be treated equally. However, this special quadratic structure will be thoroughly exploited in our search for an efficient yet simple ADMM-type method with guaranteed convergence.

Let $\sigma>0$ be a given parameter. The augmented Lagrangian function for (39) is defined by

for $w_{i}\in{\cal W}_{i}$, $i=1,\ldots,n$ and $x\in{\cal X}.$ Choose any initial points $w_{i}^{0}\in{\rm dom}(\phi_{i})$, $i=1,\ldots,q$ and $x^{0}\in{\cal X}$. The classical augmented Lagrangian method consists of the following iterations:

where $\tau\in(0,2)$ guarantees the convergence. Due to the non-separability of the quadratic penalty term in ${\cal L}_{\sigma}$, it is generally a challenging task to solve the joint minimization problem (40) exactly or approximately with high accuracy. To overcome this difficulty, one may consider the following $n$-block alternating direction methods of multipliers (ADMM):

The above $n$-block ADMM is an direct extension of the ADMM for solving the following $2$-block convex optimization problem

The convergence of $2$-block ADMM has already been extensively studied in and references therein. However, the convergence of the $n$-block ADMM has been ambiguous for a long time. Fortunately this ambiguity has been addressed very recently in where Chen, He, Ye, and Yuan showed that the direct extension of the ADMM to the case of a $3$-block convex optimization problem is not necessarily convergent. On the other hand, the $n$-block ADMM with $\tau\geq 1$ often works very well in practice and this fact poses a big challenge if one attempts to develop new ADMM-type algorithms which have convergence guarantee but with competitive numerical efficiency and iteration simplicity as the $n$-block ADMM.

Recently, there is exciting progress in this active research area. Sun, Toh and Yang proposed a convergent semi-proximal ADMM (PADMM3c) for convex programming problems of three separable blocks in the objective function with the third part being linear. One distinctive feature of algorithm PADMM3c is that it requires only an inexpensive extra step, compared to the 3-block ADMM, but yields a convergent and faster algorithm. Extensive numerical tests on the doubly non-negative SDP problems with equality and/or inequality constraints demonstrate that PADMM3c can have superior numerical efficiency over the directly extended ADMM. This opens up the possibility of designing an efficient and convergent ADMM type method for solving multi-block convex optimization problems. Inspired by the aforementioned work, in this paper we shall propose a Schur complement based semi-proximal ADMM (SCB-SPADMM) to efficiently solve the convex quadratic conic programming problems to medium accuracy. The development of our algorithm is based on the simple yet elegant idea of the Schur complement and the convenient convergence results of the semi-proximal ADMM given in the appendix of . Our primary motivation for designing the proposed SCB-SPADMM is to generate a good initial point quickly to warm-start locally fast convergent method such as the semismooth Newton-CG method used in for solving linear SDP though the method proposed here is definitely of its own interest.

The remaining parts of this paper are organized as follows. In the next section, we present a Schur complement based semi-proximal augmented Lagrangian method (SCB-SPALM) to solve a 2-block convex optimization problem where the second function $g$ is quadratic and then show the relation between our SCB-SPALM and the generic 2-block semi-proximal ADMM (SPADMM). In section 3, we propose our main algorithm SCB-SPADMM for solving the general convex model (13). Our main convergence results are presented in this section. Section 4 is devoted to the implementation and numerical experiments of using our SCB-SPADMM to solve convex quadratic conic programming problems and the various extensions. We conclude our paper in the final section.

Notation. Define the spectral (or operator) norm of a given linear operator ${\cal T}$ by $\|{\cal T}\|:=\sup_{\|w\|=1}\|{\cal T}w\|.$ For any $w\in{\cal U},$ we let

A Schur complement based semi-proximal augmented Lagrangian method

Before we introduce our approach for the multi-block case, we need to consider the convex optimization problem with the following 2-block separable structure

where $f:{\cal U}\rightarrow(-\infty,+\infty]$ and $g:{\cal V}\rightarrow(-\infty,+\infty]$ are closed proper convex functions, ${\cal F}:{\cal X}\rightarrow{\cal U}$ and ${\cal G}:{\cal X}\rightarrow{\cal V}$ are given linear maps. The dual of problem (46) is given by

Let $\sigma>0$ be given. The augmented Lagrangian function associated with (46) is given as follows:

The semi-proximal ADMM proposed in , when applied to (46), has the following template. Since the proximal terms added here are allowed to be positive semidefinite, the corresponding method is referred to as semi-proximal ADMM instead of proximal ADMM as in .

Algorithm SPADMM: A generic 2-block semi-proximal ADMM for solving (46). Let $\sigma>0$ and $\tau\in(0,\infty)$ be given parameters. Let ${\cal T}_{f}$ and ${\cal T}_{g}$ be given self-adjoint positive semidefinite, not necessarily positive definite, linear operators defined on ${\cal U}$ and ${\cal V}$, respectively. Choose $(u^{0},v^{0},x^{0})\in\mbox{dom}(f)\times\mbox{dom}(g)\times{\cal X}.$ For $k=0,1,2,...$, perform the $k$th iteration as follows: Step 1. Compute $\displaystyle u^{k+1}=\mbox{argmin}_{u}\;{\cal L}_{\sigma}(u,v^{k};x^{k})+\frac{\sigma}{2}\|u-u^{k}\|_{{\cal T}_{f}}^{2}.$ (49) Step 2. Compute $\displaystyle v^{k+1}=\mbox{argmin}_{v}\;{\cal L}_{\sigma}(u^{k+1},v;x^{k})+\frac{\sigma}{2}\|v-v^{k}\|_{{\cal T}_{g}}^{2}.$ (50) Step 3. Compute $\displaystyle x^{k+1}=x^{k}+\tau\sigma({\cal F}^{*}u^{k+1}+{\cal G}^{*}v^{k+1}-c).$ (51)

In the above 2-block semi-proximal ADMM for solving (46), the presence of ${\cal T}_{f}$ and ${\cal T}_{g}$ can help to guarantee the existence of solutions for the subproblems (49) and (50). In addition, they play important roles in ensuring the boundedness of the two generated sequences $\{y^{k+1}\}$ and $\{z^{k+1}\}$. Hence, these two proximal terms are preferred. The choices of ${\cal T}_{f}$ and ${\cal T}_{g}$ are very much problem dependent. The general principle is that both ${\cal T}_{f}$ and ${\cal T}_{g}$ should be as small as possible while $y^{k+1}$ and $z^{k+1}$ are still relatively easy to compute.

For the convergence of the 2-block semi-proximal ADMM, we need the following assumption.

There exists $(\hat{u},\hat{v})\in{\rm ri}({\rm dom}\,f\times{\rm dom}\,g)$ such that ${\cal F}^{*}\hat{u}+{\cal G}^{*}\hat{v}=c$.

Let $\Sigma_{f}$ and $\Sigma_{g}$ be the self-adjoint and positive semidefinite operators defined by (52) and (53), respectively. Suppose that the solution set of problem (46) is nonempty and that Assumption 2.1 holds. Assume that ${\cal T}_{f}$ and ${\cal T}_{g}$ are chosen such that the sequence $\{(u^{k},v^{k},x^{k})\}$ generated by Algorithm SPADMM is well defined. Then, under the condition either (a) $\tau\in(0,(1+\sqrt{5}\,)/2)$ or (b) $\tau\geq(1+\sqrt{5}\,)/2$ but $\sum_{k=0}^{\infty}(\|{\cal G}^{*}(v^{k+1}-v^{k})\|^{2}+\tau^{-1}\|{\cal F}^{*}u^{k+1}+{\cal G}^{*}v^{k+1}-c\|^{2})<\infty$, the following results hold:

If $(u^{\infty},v^{\infty},x^{\infty})$ is an accumulation point of $\{(u^{k},v^{k},x^{k})\}$, then $(u^{\infty},v^{\infty})$ solves problem (46) and $x^{\infty}$ solves (47), respectively.

If both $\sigma^{-1}\Sigma_{f}+{\cal T}_{f}+{\cal F}{\cal F}^{*}$ and $\sigma^{-1}\Sigma_{g}+{\cal T}_{g}+{\cal G}{\cal G}^{*}$ are positive definite, then the sequence $\{(u^{k},v^{k},x^{k})\}$, which is automatically well defined, converges to a unique limit, say, $(u^{\infty},v^{\infty},x^{\infty})$ with $(u^{\infty},v^{\infty})$ solving problem (46) and $x^{\infty}$ solving (47), respectively.

When the $u$-part disappears, the corresponding results in parts (i)–(ii) hold under the condition either $\tau\in(0,2)$ or $\tau\geq 2$ but $\sum_{k=0}^{\infty}\|{\cal G}^{*}v^{k+1}-c\|^{2}<\infty$.

The conclusions of Theorem 2.1 follow essentially from the results given in [3, Theorem B.1]. See for more detailed discussions.

Next, we shall pay particular attention to the case when $g$ is a quadratic function:

where $\Sigma_{g}$ a self-adjoint positive semidefinite linear operator defined on ${\cal V}$ and $b\in{\cal V}$ is a given vector. Problem (46) now takes the form of

In order to solve subproblem (50) in Algorithm SPADMM, we need to solve a linear system with the linear operator given by $\sigma^{-1}\Sigma_{g}+{\cal G}{\cal G}^{*}$. Hence, an appropriate proximal term should be chosen such that (50) can be solved efficiently. Here, we choose ${\cal T}_{g}$ as follows. Let ${\cal E}_{g}:{\cal V}\to{\cal V}$ be a self-adjoint positive definite linear operator such that it is a majorization of $\sigma^{-1}\Sigma_{g}+{\cal G}{\cal G}^{*}$, i.e.,

We choose ${\cal E}_{g}$ such that its inverse can be computed at a moderate cost. Define

Note that for numerical efficiency, we need the self-adjoint positive semidefinite linear operator ${\cal T}_{g}$ to be as small as possible. In order to fully exploit the structure of the quadratic function $g$, we add, instead of a naive proximal term, a proximal term based on the Schur complement as follows. For a given ${\cal T}_{f}\succeq 0$, we define the self-adjoint positive semidefinite linear operator

For later developments, here we state a proposition which uses the Schur complement condition for establishing the positive definiteness of a linear operator.

Since ${\cal E}_{g}={\cal G}{\cal G}^{*}+\sigma^{-1}\Sigma_{g}+{\cal T}_{g}\succ 0,$ by the Schur complement condition for ensuring the positive definiteness of linear operators, we have ${\cal W}\succ 0$ if and only if

By (60), we know that the conclusion of this proposition holds.

Now, we can propose our Schur complement based semi-proximal augmented Lagrangian method (SCB-SPALM) to solve (57) with a specially chosen proximal term involving $\widehat{{\cal T}}_{f}$ and ${\cal T}_{g}$.

Algorithm SCB-SPALM: A Schur complement based semi-proximal augmented Lagrangian method for solving (57). Let $\sigma>0$ and $\tau\in(0,\infty)$ be given parameters. Choose $(u^{0},v^{0},x^{0})\in\mbox{dom}(f)\times{\cal V}\times{\cal X}.$ For $k=0,1,2,...$, perform the $k$th iteration as follows: Step 1. Compute $\displaystyle(u^{k+1},v^{k+1})=\mbox{argmin}_{u,v}\;{\cal L}_{\sigma}(u,v;x^{k})+\frac{\sigma}{2}\|u-u^{k}\|_{\widehat{{\cal T}}_{f}}^{2}+\frac{\sigma}{2}\|v-v^{k}\|^{2}_{{\cal T}_{g}}.$ (63) Step 2. Compute $\displaystyle x^{k+1}=x^{k}+\tau\sigma({\cal F}^{*}u^{k+1}+{\cal G}^{*}v^{k+1}-c).$ (64)

Note that problem (63) in Step 1 is well defined if the the linear operator ${\cal W}$ defined in Proposition 2.1 is positive definite, or equivalently, if ${\cal F}{\cal F}^{*}+\sigma^{-1}\Sigma_{f}+{\cal T}_{f}\succ 0$. Also, note that in the context of the convex optimization problem (57), Assumption 2.1 is reduced to the following:

There exists $(\hat{u},\hat{v})\in{\rm ri}({\rm dom}\,f)\times{\cal V}$ such that ${\cal F}^{*}\hat{u}+{\cal G}^{*}\hat{v}=c$.

Now, we are ready to establish our convergence results for Algorithm SCB-SPALM for solving (57).

Let $\Sigma_{f}$, $\Sigma_{g}$ and ${\cal T}_{g}$ be three self-adjoint and positive semidefinite operators defined by (52), (54) and (59), respectively. Suppose that the solution set of problem (57) is nonempty and that Assumption 2.2 holds. Assume that ${\cal T}_{f}$ is chosen such that the sequence $\{(u^{k},v^{k},x^{k})\}$ generated by Algorithm SCB-SPALM is well defined. Then, under the condition either (a) $\tau\in(0,2)$ or (b) $\tau\geq 2$ but $\sum_{k=0}^{\infty}\|{\cal F}^{*}u^{k+1}+{\cal G}^{*}v^{k+1}-c\|^{2}<\infty$, the following results hold:

If $(u^{\infty},v^{\infty},x^{\infty})$ is an accumulation point of $\{(u^{k},v^{k},x^{k})\}$, then $(u^{\infty},v^{\infty})$ solves problem (57) and $x^{\infty}$ solves (58), respectively.

If $\sigma^{-1}\Sigma_{f}+{\cal T}_{f}+{\cal F}{\cal F}^{*}$ is positive definite, then the sequence $\{(u^{k},v^{k},x^{k})\}$, which is automatically well defined, converges to a unique limit, say, $(u^{\infty},v^{\infty},x^{\infty})$ with $(u^{\infty},v^{\infty})$ solving problem (57) and $x^{\infty}$ solving (58), respectively.

Proof. By combining Theorem 2.1 and Proposition 2.1, one can prove the results of this theorem directly.

The relationship between Algorithm SCB-SPALM and Algorithm SPADMM for solving (57) will be revealed in the next proposition.

Let $\delta_{g}:{\cal U}\times{\cal V}\times{\cal X}\rightarrow{\cal U}$ be an auxiliary linear function associated with (57) defined by

Let $\bar{u}\in{\cal U}$, $\bar{v}\in{\cal V}$, $\bar{x}\in{\cal X}$ and $c\in{\cal X}$ be given. Denote

Let $(u^{+},v^{+})\in{\cal U}\times{\cal V}$ be defined by

Let $\bar{\alpha}:=\sigma^{-1}b+{\cal T}_{g}\bar{v}+{\cal G}(c-\sigma^{-1}\bar{x})$. Define $v^{\prime}\in{\cal V}$ by

The optimal solution $(u^{+},v^{+})$ to problem (66) is generated exactly by the following procedure

Furthermore, $(u^{+},v^{+})$ can also be obtained by the following equivalent procedure

Proof. First we show that the equivalence between (66) and (70). Define

By simple algebraic manipulations, we have that

with $\bar{\alpha}$ as defined in the proposition. For any given $u\in{\cal U}$, let

Then by using the fact that $\min_{v}\frac{1}{2}\langle v,\,{\cal E}_{g}v\rangle+\langle q,\,v\rangle=-\frac{1}{2}\langle q,\,{\cal E}_{g}^{-1}q\rangle$ for any $q\in{\cal V}$, we have that

where $\kappa_{0}=\frac{\sigma}{2}(\|\sigma^{-1}\bar{x}-c\|^{2}+\|\bar{v}\|_{{\cal T}_{g}}^{2}-\|\bar{\alpha}\|_{{\cal E}_{g}^{-1}}^{2})$. Let

From (74), we have that for any given $u\in{\cal U}$,

where $\kappa_{2}=\kappa_{1}-g(\bar{v})-\frac{\sigma}{2}\|{\cal G}^{*}\bar{v}-c\|^{2}-\langle\bar{x},\,{\cal G}^{*}\bar{v}-c\rangle$. Note that with some manipulations, we can show that the constant term

where $\widetilde{{\cal L}}_{\sigma}(u,v(u);\bar{x})$ satisfies (75). From here, the equivalence between (66) and (70) follows.

Next, we prove the equivalence between (70) and (73). Note that, the first minimization problem in (73) can be equivalently recast as

which, together with the definition of $v^{\prime}$ given in (67), is equivalent to

The condition (76) can be reformulated as

The equivalence between (70) and (73) then follows. This completes the proof of this proposition.

Let $\delta_{g}^{k}:=\delta_{g}(u^{k},v^{k},x^{k})$ for $k=0,1,2,...$. We have that $u^{k+1}$ and $v^{k+1}$ obtained by Algorithm SCB-SPALM for solving (57) can be generated exactly according to the following procedure:

Proof. The conclusion follows directly from (70) in Proposition 2.2.

(i) Note that comparing to (49) in Algorithm SPADMM, the first subproblem of (81) has an extra linear term $\langle\delta_{g}^{k},\,\cdot\rangle$. It is this linear term that allows us to design a convergent SPADMM for solving multi-block convex optimization problems. (ii) The linear term $\langle\delta_{g}^{k},\,\cdot\rangle$ will vanish if $\Sigma_{g}=0$, ${\cal E}_{g}={\cal G}{\cal G}^{*}\succ 0$ and a proper starting point $(u^{0},v^{0},x^{0})$ is chosen. Specifically, if we choose $x^{0}\in{\cal X}$ such that ${\cal G}x^{0}=b$ and $(u^{0},v^{0})\in{\rm dom}(f)\times{\cal V}$ such that $v^{0}={\cal E}_{g}^{-1}{\cal G}(c-{\cal F}^{*}u^{0})$, then it holds that ${\cal G}x^{k}=b$ and $v^{k}={\cal E}_{g}^{-1}{\cal G}(c-{\cal F}^{*}u^{k})$, which imply that $\delta_{g}^{k}=0$. (iii) Observe that when ${\cal T}_{f}$ and ${\cal T}_{g}$ are chosen to be in (81), apart from the range of $\tau$, our Algorithm SCB-SPALM differs from the classical 2-block ADMM for solving problem (57) only in the linear term $\langle\delta_{g}^{k},\,\cdot\rangle$. This shows that the classical 2-block ADMM for solving problem (57) has an unremovable deviation from the augmented Lagrangian method. This may explain why even when ADMM type methods suffer from slow local convergence, the latter can still enjoy fast local convergence.

In the following, we compare our Schur complement based proximal term $\frac{\sigma}{2}\|u-u^{k}\|_{\widehat{{\cal T}}_{f}}^{2}+\frac{\sigma}{2}\|v-v^{k}\|^{2}_{{\cal T}_{g}}$ used to derive the scheme (81) for solving (57) with the following proximal term which allows one to update $u$ and $v$ simultaneously:

where ${\cal D}_{1}:{\cal U}\rightarrow{\cal U}$ and ${\cal D}_{2}:{\cal V}\rightarrow{\cal V}$ are two self-adjoint positive semidefinite linear operators satisfying

A common naive choice will be ${\cal D}_{1}=\lambda_{\max}{\cal I}_{1}$ and ${\cal D}_{2}=\lambda_{\max}{\cal I}_{2}$ where $\lambda_{\max}=\|{\cal F}{\cal G}^{*}\|_{2},$ ${\cal I}_{1}:{\cal U}\rightarrow{\cal U}$ and ${\cal I}_{2}:{\cal V}\rightarrow{\cal V}$ are identity maps. Simple calculations show that the resulting semi-proximal augmented Lagrangian method generates $(u^{k+1},v^{k+1},x^{k+1})$ as follows:

To ensure that the subproblems in (88) are well defined, we may require the following sufficient conditions to hold:

Comparing the proximal terms used in (63) and (84), we can easily see that the difference is:

To simplify the comparison, we assume that

By rescaling the equality constraint in (57) if necessary, we may also assume that $\|{\cal F}\|=1$. Now, we have that

which is larger than the former upper bound $\|u-u^{k}\|^{2}$ if $\|{\cal G}\|\geq 1/2$. Thus we can conclude safely that the proximal term $\|u-u^{k}\|^{2}_{{\cal F}{\cal G}^{*}{\cal E}_{g}^{-1}{\cal G}{\cal F}^{*}}$ can be potentially much smaller than $\|(u,v)-(u^{k},v^{k})\|^{2}_{{\cal M}}$ unless $\|{\cal G}\|$ is very small.

The above mentioned upper bounds difference is of course due to the fact that the SCB semi-proximal augmented Lagrangian method takes advantage of the fact that $g$ is assumed to be a convex quadratic function. However, the key difference lies in the fact that (88) is a splitting version of the semi-proximal augmented Lagrangian method with a Jacobi type decomposition, whereas Algorithm SCB-SPALM is a splitting version of semi-proximal augmented Lagrangian method with a Gauss-Seidel type decomposition. It is this fact that provides us with the key idea to design Schur complement based proximal terms for multi-block convex optimization problems in the next section.

A Schur complement based semi-proximal ADMM

with all $\theta_{i}$ and $\varphi_{j}$ being assumed to be convex quadratic functions:

where ${\cal P}_{i}$ and ${\cal Q}_{j}$ are given self-adjoint positive semidefinite linear operators. The dual of (91) is given by

For $i=1,\ldots,p$, let ${\cal E}_{\theta_{i}}$ be a self-adjoint positive definite linear operator on ${\cal Y}_{i}$ such that it is a majorization of $\sigma^{-1}{\cal P}_{i}+{\cal A}_{i}{\cal A}_{i}^{*}$, i.e.,

We choose ${\cal E}_{\theta_{i}}$ in a way that its inverse can be computed at a moderate cost. Define

Note that for numerical efficiency, we need the self-adjoint positive semidefinite linear operator ${\cal T}_{\theta_{i}}$ to be as small as possible for each $i$. Similarly, for $j=1,\ldots,q$, let ${\cal E}_{\varphi_{j}}$ be a self-adjoint positive definite linear operator on ${\cal Z}_{j}$ that majorizes $\sigma^{-1}{\cal Q}_{j}+{\cal B}_{j}{\cal B}_{j}^{*}$ in a way that ${\cal E}_{\varphi_{j}}^{-1}$ can be computed relatively easily. Denote

Again, we need the self-adjoint positive semidefinite linear operator ${\cal T}_{\varphi_{j}}$ to be as small as possible for each $j$.

with the convention that $y_{0}=y_{p+1}=y_{\leq 0}=y_{\geq p+1}=\emptyset.$ For $i=1,\ldots,p,$ define the linear operator ${\cal A}_{\leq i}:{\cal X}\rightarrow{\cal Y}$ by

In a similar manner, we can define $z_{\leq j},z_{\geq j}$ for $j=0,\ldots,q+1$ and define the linear operator ${\cal B}_{\leq j}$ for $j=1,\ldots,q.$ Note that by definition, we have $y=y_{\leq p}$, $z=z_{\leq q}$, ${\cal A}={\cal A}_{\leq p}$ and ${\cal B}={\cal B}_{\leq q}$.

Define the affine function $\Gamma:{\cal U}\times{\cal Y}\times{\cal V}\times{\cal Z}\rightarrow{\cal X}$ by

Let $\sigma>0$ be given. The augmented Lagrangian function associated with (91) is given as follows:

where $\theta(y)=\sum_{i=1}^{p}\theta_{i}(y_{i})$ and $\varphi(z)=\sum_{j=1}^{q}\varphi_{j}(z_{j})$.

Now we are ready to present our SCB-SPADMM (Schur complement based semi-proximal alternating direction method of multipliers) algorithm for solving (91).

Algorithm SCB-SPADMM: A Schur complement based SPADMM for solving (91). Let $\sigma>0$ and $\tau\in(0,\infty)$ be given parameters. Let ${\cal T}_{f}$ and ${\cal T}_{g}$ be given self-adjoint positive semidefinite operators defined on ${\cal U}$ and ${\cal V}$ respectively. Choose $(u^{0},y^{0},v^{0},z^{0},x^{0})\in\mbox{dom}(f)\times{\cal Y}\times\mbox{dom}(g)\times{\cal Z}\times{\cal X}.$ For $k=0,1,2,...$, generate $(u^{k+1},y^{k+1},v^{k+1},z^{k+1})$ and $x^{k+1}$ according to the following iteration. Step 1. Compute for $i=p,\ldots,1,$ $\displaystyle\overline{y}_{i}^{k}\;=\;\mbox{argmin}_{y_{i}}\;{\cal L}_{\sigma}(u^{k},(y_{\leq i-1}^{k},y_{i},\overline{y}_{\geq i+1}^{k}),v^{k},z^{k};x^{k})+\frac{\sigma}{2}\|y_{i}-y_{i}^{k}\|_{{\cal T}_{\theta_{i}}}^{2},$ (102) where ${\cal T}_{\theta_{i}}$ is defined as in (97). Then compute $\displaystyle u^{k+1}=\mbox{argmin}_{u}\;{\cal L}_{\sigma}(u,\overline{y}^{k},v^{k},z^{k};x^{k})+\frac{\sigma}{2}\|u-u^{k}\|_{{\cal T}_{f}}^{2}.$ (103) Step 2. Compute for $i=1,\ldots,p,$ $\displaystyle y_{i}^{k+1}\;=\;\mbox{argmin}_{y_{i}}\;{\cal L}_{\sigma}(u^{k+1},(y_{\leq i-1}^{k+1},y_{i},\overline{y}_{\geq i+1}^{k}),v^{k},z^{k};x^{k})+\frac{\sigma}{2}\|y_{i}-y_{i}^{k}\|_{{\cal T}_{\theta_{i}}}^{2}.$ (104) Step 3. Compute for $j=q,\ldots,1$, $\displaystyle\overline{z}_{j}^{k}\;=\;\mbox{argmin}_{z_{j}}\;{\cal L}_{\sigma}(u^{k+1},y^{k+1},v^{k},(z_{\leq j-1}^{k},z_{j},\overline{z}_{\geq j+1}^{k});x^{k})+\frac{\sigma}{2}\|z_{j}-z_{j}^{k}\|_{{\cal T}_{\varphi_{j}}}^{2},$ (105) where ${\cal T}_{\varphi_{j}}$ is defined as in (98). Then compute $\displaystyle v^{k+1}=\mbox{argmin}_{v}\;{\cal L}_{\sigma}(u^{k+1},y^{k+1},v,\overline{z}^{k};x^{k})+\frac{\sigma}{2}\|v-v^{k}\|_{{\cal T}_{g}}^{2}.$ (106) Step 4. Compute for $j=1,\ldots,q$, $\displaystyle z_{j}^{k+1}\;=\;\mbox{argmin}_{z_{j}}\;{\cal L}_{\sigma}(u^{k+1},y^{k+1},v^{k+1},(z_{\leq j-1}^{k+1},z_{j},\overline{z}_{\geq j+1}^{k});x^{k})+\frac{\sigma}{2}\|z_{j}-z_{j}^{k}\|_{{\cal T}_{\varphi_{j}}}^{2}.$ (107) Step 5. Compute $\displaystyle x^{k+1}=x^{k}+\tau\sigma({\cal F}^{*}u^{k+1}+{\cal A}^{*}y^{k+1}+{\cal G}^{*}v^{k+1}+{\cal B}^{*}z^{k+1}-c).$ (108)

In order to prove the convergence of Algorithm SCB-SPADMM for solving (91), we need first to study the relationship between SCB-SPADMM and the generic 2-block semi-proximal ADMM for solving a two-block convex optimization problem discussed in the previous section.

where ${\cal Y}_{\leq l}={\cal Y}_{1}\times{\cal Y}_{2}\times\ldots\times{\cal Y}_{l}$. Similarly, for $l=1,\ldots,q$, define ${\cal Z}_{\leq l}={\cal Z}_{1}\times{\cal Z}_{2}\times\ldots\times{\cal Z}_{l}$, and

Denote ${\cal A}_{0}^{*}\equiv{\cal F}_{1}^{*}\equiv{\cal F}^{*}$ and ${\cal B}_{0}^{*}\equiv{\cal G}_{1}^{*}\equiv{\cal G}^{*}$. Let

Define the following self-adjoint linear operators: $\widehat{{\cal T}}_{f_{1}}:={\cal T}_{f}+{\cal F}_{1}{\cal A}_{1}^{*}{\cal E}_{\theta_{1}}^{-1}{\cal A}_{1}{\cal F}_{1}^{*}$,

and $\widehat{{\cal T}}_{g_{1}}:={\cal T}_{g}+{\cal G}_{1}{\cal B}_{1}^{*}{\cal E}_{\varphi_{1}}^{-1}{\cal B}_{1}{\cal G}_{1}^{*}$,

Let $(\bar{v},\bar{z},\bar{x},c)\in{\cal V}\times{\cal Z}\times{\cal X}\times{\cal X}$ be given. Denote

We will show later in Proposition 3.1 that $\bar{\delta}_{\theta}$ is the auxiliary linear term associated with problem (91). Recall that

For $i=p,\ldots,1,$ let $y_{i}^{\prime}\in{\cal Y}_{i}$ be defined by

with the convention $y^{\prime}_{p+1}=\emptyset$. Define $(u^{+},y^{+})\in{\cal U}\times{\cal Y}$ by

The following proposition about two other equivalent procedures for computing $(u^{+},y^{+})$ is the key ingredient for our algorithmic developments. The idea of proving this proposition is very simple: use Proposition 2.2 repeatedly though the proof itself is rather lengthy due to the multi-layered nature of the problems involved. For (121), we first express $y_{p}$ as a function of $(u,y_{\leq p-1})$ to obtain a problem involving only $(u,y_{\leq p-1})$, and from the resulting problem, express $y_{p-1}$ as a function of $(u,y_{\leq p-2})$ to get another problem involving only $(u,y_{\leq p-2})$. We continue this way until we get a problem involving only $(u,y_{1})$.

The optimal solution $(u^{+},y^{+})$ defined by (121) can be obtained exactly by

where the auxiliary linear term $\bar{\delta}_{\theta}$ is defined by (119). Furthermore, $(u^{+},y^{+})$ can also be generated by the following equivalent procedure

Proof. We will separate our proof into two parts and for each part we prove our conclusions by induction.

Part one. In this part we show that $(u^{+},y^{+})$ defined by (121) can be obtained exactly by (124). For the case $p=1$, this follows directly from Proposition 2.2.

Assume that the equivalence between (121) and (124) holds for all $p\leq l$. We need to show that for $p=l+1$, this equivalence also holds. For this purpose, we consider the following optimization problem with respect to $(u,y_{\leq l})$ and $y_{l+1}$:

The augmented Lagrangian function associated with problem (130) is given by

We denote the vector $\delta_{\theta_{l+1}}$ as the auxiliary linear term associated with problem (130) by

Note that by the definition of ${\cal F}_{l+1}$ and $p=l+1$, we have

with ${\beta}_{p,j}$, $j=1,\ldots,l+1$, defined as in (117).

By noting that ${{\cal L}}^{l+1}_{\sigma}((u,y_{\leq l}),y_{l+1};\bar{v},\bar{z},\bar{x})={{\cal L}}_{\sigma}(u,y_{\leq l},y_{l+1},\bar{v},\bar{z};\bar{x})$, we can rewrite problem (121) for $p=l+1$ equivalently as

Then, from Proposition 2.2, we know that problem (135) is equivalent to

By observing that ${{\cal L}}^{l+1}_{\sigma}((u^{+},y_{\leq l}^{+}),y_{l+1};\bar{v},\bar{z},\bar{x})={\cal L}_{\sigma}(u^{+},y_{\leq l}^{+},y_{l+1},\bar{v},\bar{z};\bar{x})$, we know that problem (139) can equivalently be rewritten as

In order to apply our induction assumption to problem (138), we need to construct a corresponding optimization problem. Define for $i=1,\ldots,l$,

We shall now consider the following optimization problem with respect to $(u,y_{\leq l})$:

The augmented Lagrangian function associated with problem (143) is defined by

By using the definitions of $\widetilde{\theta}_{i}$ and $\widetilde{f}_{i}$, $i=1,\ldots,l$, we have

Therefore, problem (138) can equivalently be rewritten as

The auxiliary linear term ${\delta}_{\widetilde{\theta}}$ associated with problem (147) is given by

We will show that for $i=l,l-1,\ldots,1$,

First, by using (144), we have for $j=1,\ldots,l$ that

That is, (149) holds for $i=l$ and $j=1,\ldots,l$. Now assume that we have proven $\widetilde{\beta}_{i,j}={\beta}_{i,j}$ for all $i\geq k+1$ with $k+1\leq l$ and $j=1,\ldots,i$. We shall next prove that (149) holds for $i=k$ and $j=1,\ldots,k$. Again, by using (144), we have for $j=1,\ldots,k$ that

which, shows that (149) holds for $i=k$ and $j=1,\ldots,k$. Thus, (149) is proven.

For $i=l,l-1,\ldots,1,$ define $\widetilde{y}^{\prime}_{i}\in{\cal Y}_{i}$ by

where we use the convention $\widetilde{y}^{\prime}_{l+1}=\emptyset.$ We will prove that

which, together with the definitions of $\beta_{p,i}$ in (117), implies

Now, by using (144), (153) and the definitions of $\widetilde{y}^{\prime}_{l}$ and $y^{\prime}_{l}$, we have

That is, (151) holds for $i=l$. Now assume that we have proven $\widetilde{y}^{\prime}_{i}=y^{\prime}_{i}$ for all $i\geq k+1$ with $k+1\leq l$. We shall next prove that (151) holds for $i=k$. Again, by using the definitions of $\widetilde{y}^{\prime}_{k}$ and $y^{\prime}_{k}$ and noting

which, shows that (151) holds for $i=k.$ Thus, (151) holds.

By applying our induction assumption to problem (147), we obtain equivalently that

where we use the facts that ${\cal T}_{\widetilde{f}_{1}}={\cal T}_{f}$ and ${\cal T}_{\widetilde{\theta}_{i}}={\cal T}_{\theta_{i}}$ for $i=1,\ldots,l$. By combining (149) and the definitions of $\bar{\delta}_{\theta}$ and ${\delta}_{\widetilde{\theta}}$ defined in (119) and (148), respectively, we derive that

Using (151), (153) and the definition of $\widetilde{{\cal L}}_{\sigma}$, we have for $i=1,\ldots,l$ that

where $c_{i}$ is a constant term given by

Thus, by using (156), (157) and (158) we know that (154) and (155) can be rewritten as

which, together with (140), shows that the equivalence between (121) and (124) holds for $p=l+1$. The proof of this part is completed.

Part two. In this part, we prove the equivalence between (124) and (127). Again, for the case $p=1$, it follows directly from Proposition 2.2.

Assume that the equivalence between (124) and (127) holds for all $p\leq l$. We shall prove that this equivalence also holds for $p=l+1$. Write ${f}_{0}(\cdot)\equiv f(\cdot)+\sum_{i=1}^{l}\langle{\beta}_{i,1},\,\cdot\rangle.$ Since ${f}_{0}$ differs from $f$ only with an extra linear term, we define ${\cal T}_{{f_{0}}}\equiv{\cal T}_{f}.$ In order to use Proposition 2.2, we consider the following optimization problem with respect to $u$ and $y_{l+1}$:

The augmented Lagrangian function associated with problem (162) is given as follows:

we can rewrite the first subproblem in (124) as

By using the definition of $y^{\prime}_{l+1}$ given in (120), we have

the point $y^{\prime}_{l+1}$ can be rewritten equivalently as

Then, by applying Proposition 2.2 to problem (162) with respect to $u$ and $y_{l+1}$, we know that problem (163) is equivalent to

In order to apply our induction assumption to problem (166), we need to consider the following optimization problem with respect to $(u,y_{\leq l})$:

The augmented Lagrangian function associated with problem (169) is given by

For problem (169), we define the following associated terms

The auxiliary linear term $\widehat{\delta}$ associated with problem (169) is given by

We will show that, for $i=l,l-1,\ldots,1$,

Similar to what we have done in part one, we shall first prove that $\widehat{\beta}_{l,j}={\beta}_{l,j}$ for $j=1,2,\ldots,l$. In fact, for $j=1,\ldots,l$, we have

where the third equation follows from (164) and simple calculations. This shows that (171) holds for $i=l$ and $j=1,\ldots,l$. Now we assume that $\widehat{\beta}_{i,j}={\beta}_{i,j}$ for all $i\geq k+1$ with $k+1\leq l$ and $j=1,\ldots,i$. Next, we shall prove that (171) holds for $i=k$ and $j=1,\ldots,k$. By direct calculations, we know for $j=1,\ldots,k$ that

which, shows that (171) holds for $i=k$ and $j=1,\ldots,k$. Therefore, we have shown that (171) holds.

For $i=l,l-1,\ldots,1,$ define $\widehat{y}^{\prime}_{i}\in{\cal Y}_{i}$ as

where we use the convention $\widehat{y}^{\prime}_{l+1}=\emptyset.$ We will prove that

which is exactly the same as $y^{\prime}_{l}$ defined in (120). This shows that (173) holds for $i=l.$ Now we assume that $\widehat{y}^{\prime}_{i}=y^{\prime}_{i}$ for all $i\geq k+1$ with $k+1\leq l$. Next, we shall prove that (173) holds for $i=k.$ Again, by using the definition of $\widehat{y}^{\prime}_{k}$ in (172) and the definition of $y^{\prime}_{k}$ in (120), we see that

By direct calculations, we obtain from (170) and (171) that

By using (174) and ${\cal T}_{{f}_{0}}\equiv{\cal T}_{f}$, we can reformulate problem (166) equivalently as

Then, from our induction assumption we know that problem (175) can be equivalently recast as

which, together with (165), shows that the equivalence between (124) and (127) holds for $p=l+1$. This completes the proof to the second part of this proposition.

For any $k\geq 0$, the point $(x^{k+1},y^{k+1},v^{k+1},z^{k+1})$ obtained by Algorithm SCB-SPADMM for solving problem (91) can be generated exactly according to the following iteration:

Proof. The $(u^{k+1},y^{k+1})$ part directly follows from Proposition 3.1. The conclusion for the $(v^{k+1},z^{k+1})$ part can be obtained in similar arguments to the part about $(u^{k+1},y^{k+1})$. Hence, the required result follows.

Write $\Sigma_{f_{1}}\equiv\Sigma_{f}$ and $\Sigma_{g_{1}}\equiv\Sigma_{g}$. Define

In order to prove the convergence of our algorithm SCB-SPADMM for solving problem (91), we need the following proposition.

Proof. We only need to prove (185) as (188) can be obtained in the similar manner. For $i=3,\ldots,p+1$, we have

Since ${\cal E}_{\theta_{i-1}}={\cal A}_{i-1}{\cal A}_{i-1}^{*}+\sigma^{-1}{\cal P}_{i-1}+{\cal T}_{\theta_{i-1}}\succ 0$ for all $i\geq 3$, by the Schur complement condition for ensuring the positive definiteness of linear operators, we have

Therefore, by taking $i=3$, we obtain that

Since ${\cal E}_{\theta_{1}}={\cal A}_{1}{\cal A}_{1}^{*}+\sigma^{-1}{\cal P}_{1}+{\cal T}_{\theta_{1}}\succ 0,$ again by the Schur complement condition for ensuring the positive definiteness of linear operators, we have

The proof of this proposition is completed.

Note that in the context of the multi-block convex optimization problem (91), Assumption 2.1 takes the following form:

There exists $(\hat{u},\hat{y},\hat{v},\hat{z})\in{\rm ri}({\rm dom}\,f)\times{\cal Y}\times{\rm ri}({\rm dom}\,g)\times{\cal Z}$ such that ${\cal F}^{*}\hat{u}+{\cal A}^{*}\hat{y}+{\cal G}^{*}\hat{v}+{\cal B}^{*}\hat{z}=c$.

After all these preparations, we can finally state our main convergence theorem.

Let $\Sigma_{f}$ and $\Sigma_{g}$ be the two self-adjoint and positive semidefinite operators defined by (52) and (53), respectively. Suppose that the solution set of problem (91) is nonempty and that Assumption 3.1 holds. Assume that ${\cal T}_{f}$ and ${\cal T}_{g}$ are chosen such that the sequence $\{(u^{k},y^{k},v^{k},z^{k},x^{k})\}$ generated by Algorithm SCB-SPADMM is well defined. Recall that ${\cal T}_{\theta_{i}}$ is defined in (97) for $1\leq i\leq p$ and ${\cal T}_{\varphi_{j}}$ is defined in (98) for $1\leq j\leq q$. Then, under the condition either (a) $\tau\in(0,(1+\sqrt{5}\,)/2)$ or (b) $\tau\geq(1+\sqrt{5}\,)/2$ but $\sum_{k=0}^{\infty}(\|{\cal G}^{*}(v^{k+1}-v^{k})+{\cal B}^{*}(z^{k+1}-z^{k})\|^{2}+\tau^{-1}\|{\cal F}^{*}u^{k+1}+{\cal A}^{*}y^{k+1}+{\cal G}^{*}v^{k+1}+{\cal B}^{*}z^{k+1}-c\|^{2})<\infty$, the following results hold: