We investigate the techniques and ideas used in Shefi and Teboulle (SIAM J Optim 24(1), 269–297, 2014) in the convergence analysis of two proximal ADMM algorithms for solving convex optimization problems involving compositions with linear operators. Besides this, we formulate a variant of the ADMM algorithm that is able to handle convex optimization problems involving an additional smooth function in its objective, and which is evaluated through its gradient. Moreover, in each iteration, we allow the use of variable metrics, while the investigations are carried out in the setting of infinite-dimensional Hilbert spaces. This algorithmic scheme is investigated from the point of view of its convergence properties.
Hinweise
Research supported by FWF (Austrian Science Fund), project I 2419-N32, and by Wallenberg AI, Autonomous Systems and Software Program (WASP).
Research partially supported by FWF (Austrian Science Fund), project I 2419-N32.
Research supported by FWF (Austrian Science Fund), projects M 1682-N25 and P 29809-N32.
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
One of the most popular numerical algorithms for solving optimization problems of the form
$$ \inf_{x\in\mathbb{R}^{n}}\{f(x)+g(Ax)\}, $$
(1)
where \(f:\mathbb {R}^{n}\rightarrow \overline {\mathbb {R}}:=\mathbb {R}\cup \{\pm \infty \}\) and \(g:\mathbb {R}^{m}\rightarrow \overline {\mathbb {R}}\) are proper, convex, lower semicontinuous functions and \(A:\mathbb {R}^{n}\rightarrow \mathbb {R}^{m}\) is a linear operator, is the alternating direction method of multipliers (ADMM). Here, the spaces \(\mathbb {R}^{n}\) and \(\mathbb {R}^{m}\) are equipped with their usual inner products and induced norms, which we both denote by 〈⋅,⋅〉 and ∥⋅∥, respectively, as there is no risk of confusion.
By introducing an auxiliary variable z, one can rewrite (1) as
It is known that (x∗, z∗, y∗) is a saddle point of l if and only if z∗ = Ax∗, (x∗, z∗) is an optimal solution of (2), y∗ is an optimal solution of the Fenchel-Rockafellar dual problem (see [3‐5, 20, 30]) to (1)
and the optimal objective values of (1) and (4) coincide. Notice that f∗ and g∗ are the conjugates of f and g, defined by \(f^{*}(u)=\sup _{x\in \mathbb {R}^{n}}\{\langle u,x\rangle -f(x)\}\) for all \(u \in \mathbb {R}^{n}\) and \(g^{*}(y)=\sup _{z\in \mathbb {R}^{m}}\{\langle y,z\rangle -g(z)\}\) for all \(y\in \mathbb {R}^{m}\), respectively.
If (1) has an optimal solution and A(ri (domf)) ∩ri domg≠∅, then the set of saddle points of l is nonempty. Here, we denote by ri(S) the relative interior of a convex set S, which is the interior of S relative to its affine hull.
For a fixed real number c > 0, we further consider the augmented Lagrangian associated with problem (2), which is defined as
If A has full column rank, then the set of minimizers in (5) is a singleton, as is the set of minimizers in (6) without any further assumption, and the sequence (xk, zk, yk)k≥ 0 generated by Algorithm 1 converges to a saddle point of the Lagrangian l (see, for instance, [19]). The alternating direction method of multipliers was first introduced in [25] and [23]. Gabay has shown in [24] (see also [19]) that ADMM is nothing else than the Douglas-Rachford algorithm applied to the monotone inclusion problem
For a function \(k : \mathbb {R}^{n} \rightarrow \overline {\mathbb {R}}\), the set-valued operator defined by \(\partial k(x) := \{u \in \mathbb {R}^{n} : k(t) - k(x) \geq \langle u,t-x\rangle \ \forall t \in \mathcal {R}^{n}\}\), for \(k(x) \in \mathbb {R}\), and ∂k(x) := ∅, otherwise, denotes its (convex) subdifferential.
One of the limitations of the ADMM algorithm comes from the presence of the term Ax in the update rule of xk+ 1 (we refer to [14] for an approach to circumvent the limitations of ADMM). While in (6) a proximal step for the function g is taken, in (5), the function f and the operator A are not evaluated independently, which makes the ADMM algorithm less attractive for implementations than the primal-dual splitting algorithms (see, for instance, [8‐10, 12, 13, 16, 29]). Despite of this fact, the ADMM algorithm has been widely used for solving convex optimization problems arising in real-life applications (see, for instance, [11, 17, 21]). For a version of the ADMM algorithm with inertial and memory effects, we refer the reader to [7].
In order to overcome the above-mentioned drawback of the classical ADMM method and to increase its flexibility, the following so-called proximal alternating direction proximal method of multipliers has been considered in [28] (see also [22, 26]):
×
Here, \(M_{1}\in \mathbb {R}^{n\times n}\) and \(M_{2}\in \mathbb {R}^{m\times m}\) are symmetric positive semidefinite matrices and \(\|u\|_{M_{i}}^{2}=\langle u,M_{i}u\rangle \) denotes the squared semi-norm induced by Mi, for i ∈{1,2}.
Indeed, for M1 = M2 = 0, Algorithm 1 becomes the classical ADMM method, while for M1 = μ1Id and M2 = μ2Id with μ1, μ2 > 0 and Id denoting the corresponding matrix, it becomes the algorithm proposed and investigated in [18]. Furthermore, if M1 = τ− 1Id − cATA with τ > 0 such that cτ∥A∥2 < 1 and M2 = 0, then one can show that Algorithm 2 is equivalent to one of the primal-dual algorithms formulated in [16].
The sequence (zk)k≥ 0 generated in Algorithm 2 is uniquely determined due to the fact that the objective function in (9) is lower semicontinuous and strongly convex. On the other hand, the set of minimizers in (8) is in general not a singleton and it can be even empty. However, if one imposes that M1 + A∗A is positive definite, then (xk)k≥ 0 will be uniquely determined, too.
Shefi and Teboulle provide in [28] in connection to Algorithm 2 an ergodic convergence rate result for a primal-dual gap function formulated in terms of the Lagrangian l, from which they deduce a global convergence rate result for the sequence of function values (f(xk) + g(Axk))k≥ 0 to the optimal objective value of (1), when g is Lipschitz continuous. Furthermore, they formulate a global convergence rate result for the sequence (∥Axk − zk∥)k≥ 0 to 0. Finally, Shefi and Teboulle prove the convergence of the sequence (xk, zk, yk)k≥ 0 to a saddle point of the Lagrangian l, provided that either M1 = 0 and A has full column rank or M1 is positive definite.
Algorithm 2 from [28] represents the starting point of our investigations. More precisely, in this paper:
We point out some flaws in the proof of a statement in [28], which is fundamental for the derivation of the global convergence rate of (∥Axk − zk∥)k≥ 0 to 0 and of the convergence of the sequence (xk, zk, yk)k≥ 0.
We show how the statement in cause can be proved by using different techniques.
We formulate a variant of Algorithm 2 for solving convex optimization problems in infinite-dimensional Hilbert spaces involving an additional smooth function in their objective that we evaluate through its gradient and which allows in each iteration the use of variable metrics.
We prove an ergodic convergence rate result for this algorithm involving a primal-dual gap function formulated in terms of the associated Lagrangian l and a convergence result for the sequence of iterates to a saddle point of l.
2 Fixing some results from [28] related to the convergence analysis for Algorithm 2
In this section, we point out several flaws that have been made in [28] when deriving a fundamental result for both the rate of convergence of the sequence (∥Axk − zk∥)k≥ 0 to 0 and the convergence of the sequence (xk, zk, yk)k≥ 0 to a saddle point of the Lagrangian l. We also show how these arguments can be fixed by relying on some of the building blocks of the analysis we will carry out in Section 3.
To proceed, we first recall some results from [28]. We start with a statement that follows from the variational characterization of the minimizers of (8)–(9).
Lemma 1
(see [28, Lemma 4.2]) Let (xk, zk, yk)k≥ 0 be a sequence generated by Algorithm 2. Then, for all k ≥ 0 and for all \((x,z,y)\in \mathbb {R}^{n}\times \mathbb {R}^{m}\times \mathbb {R}^{m}\) it holds
Furthermore, by invoking the monotonicity of the convex subdifferential of g, in [28], the following estimation is derived.
Lemma 2
(see [28, Proposition 5.3(b)]) Let (xk, zk, yk)k≥ 0 be a sequence generated by Algorithm 2. Then, for all k ≥ 1 and for all \((x,z)\in \mathbb {R}^{n}\times \mathbb {R}^{m}\), it holds
and the estimation in Lemma 2, one easily obtains the following result.
Lemma 3
Let (x∗, z∗, y∗) be a saddle point of the Lagrangian l associated with (1), M1, M2 be symmetric positive semidefinite matrices and c > 0. Let (xk, zk, yk)k≥ 0 be a sequence generated by Algorithm 1. Then, for all k ≥ 1, the following inequality holds
however, its proof, which follows the argument that goes through Lemma 1, Lemma 2, and Lemma 3, is not correct, since it leads to (14) instead of (15).
Since the sequence (vk)k≥ 0 is monotonically decreasing, statement (15), in combination with straightforward telescoping arguments, leads to the fact that (vk)k≥ 0 converges to zero with a rate of convergence of \(\mathcal {O} (1/k)\). This implies that (∥Axk − zk∥)k≥ 0 converges to zero with a rate of convergence of \(\mathcal {O} (1/\sqrt {k})\) (see [28, Theorem 5.4]). In addition, statement (15) is used in [28, Theorem 5.6] to prove the convergence of the sequence (xk, zk, yk)k≥ 0 to a saddle point of the Lagrangian l. However, the techniques used in [28], involving function values and the saddle point inequality, do not lead to (15), but to the weaker inequality (14).
In the following, we will show that one can in fact derive (15), however, to this end one needs to use different techniques. These are described in detail in the next section; here, we will just show how do they lead to (15). We would like to notice that, differently from [28], in our analysis we will only use properties related to the fact that the convex subdifferential of a proper, convex, and lower semicontinuous function is a maximally monotone set-valued operator.
We start our analysis with relation (40), which in case h = 0, L = 0, \({M_{1}^{k}}=M_{1} \succcurlyeq 0\), and \({M_{2}^{k}}=M_{2} \succcurlyeq 0\) for all k ≥ 0 (see the setting of Section 3) reads
From here, by using that vk+ 1 ≤ vk for all k ≥ 0 and straightforward telescoping arguments, it follows immediately that (∥Axk − zk∥)k≥ 0 converges to zero with a rate of \(\mathcal {O} (1/\sqrt {k})\).
We will see in the following section that the inequality (40) will play an essential role also in the convergence analysis of the sequence of iterates. When applied to the particular context of the optimization problem (1) and Algorithm 2, Theorem 12 provides a rigorous formulation and a correct and clear proof of the convergence result stated in [28, Theorem 5.6].
3 A variant of the ADMM algorithm in the presence of a smooth function and by involving variable metrics
In this section, we propose an extension of the ADMM algorithm considered in [28] that we also investigate from the perspective of its convergence properties. This extension is twofold: on the one hand, we consider an additional convex differentiable function in the objective of the optimization problem (1), which is evaluated in the algorithm through its gradient, and on the other hand, instead of fixed matrices M1 and M2, we use different matrices in each iteration. Furthermore, we change the setting to infinite-dimensional Hilbert spaces. We start by describing the problem under investigation:
Problem 4
Let \({\mathscr{H}}\) and \(\mathcal { G}\) be real Hilbert spaces, \(f:{\mathscr{H}}\rightarrow \overline {\mathbb {R}}\), \(g: \mathcal G\rightarrow \overline {\mathbb {R}}\) be proper, convex, and lower semicontinuous functions, \(h:{\mathscr{H}}\rightarrow \mathbb {R}\) a convex and Fréchet differentiable function with L-Lipschitz continuous gradient (where L ≥ 0) and \(A:{\mathscr{H}}\rightarrow \mathcal { G}\) a linear continuous operator. The Lagrangian associated with the convex optimization problem
We say that \((x^{*},z^{*},y^{*})\in {\mathscr{H}}\times \mathcal { G}\times \mathcal { G}\) is a saddle point of the Lagrangian l, if the following inequalities hold
Notice that (x∗, z∗, y∗) is a saddle point if and only if z∗ = Ax∗, x∗ is an optimal solution of (18), y∗ is an optimal solution of the Fenchel-Rockafellar dual problem to (18)
and the optimal objective values of (18) and (20) coincide, where \(A^{*}:\mathcal { G}\rightarrow {\mathscr{H}}\) is the adjoint operator defined by 〈A∗v,x〉 = 〈v,Ax〉 for all \((v,x)\in \mathcal { G}\times {\mathscr{H}}\). The infimal convolution \(f^{*}{\Box } h^{*}:{\mathscr{H}}\rightarrow \overline {\mathbb {R}}\) is defined by \((f^{*}{\Box } h^{*})(x)=\inf _{u\in {\mathscr{H}}}\{f^{*}(u)+h^{*}(x-u)\}\) for all \(x\in {\mathscr{H}}\).
For the reader’s convenience, we discuss some situations which lead to the existence of saddle points. This is for instance the case when (18) has an optimal solution and the Attouch-Brézis qualification condition
holds. Here, for a convex set \(S\subseteq \mathcal { G}\), we denote by
$$\text{sri} S:=\{x\in S:\cup_{\lambda>0}\lambda(S-x) \ \text{is a closed linear subspace of} \ \mathcal{ G}\}$$
its strong relative interior. Notice that the classical interior is contained in the strong relative interior: \(\text {int} \ S\subseteq \text {sri} S\); however, in general, this inclusion may be strict. If \(\mathcal { G}\) is finite-dimensional, then for a nonempty and convex set \(S \subseteq \mathcal { G}\), one has sriS = riS. Considering again the infinite-dimensional setting, we remark that condition (21) is fulfilled if there exists \(x^{\prime }\in \text {dom} f\) such that \(Ax^{\prime }\in \text {dom} g\) and g is continuous at \(Ax^{\prime }\).
The optimality conditions for the primal-dual pair of optimization problems (18)-(20) read
$$ -A^{*}y-\nabla h(x)\in\partial f(x) \text{ and } y\in\partial g(Ax). $$
(22)
This means that if (18) has an optimal solution \(x^{*}\in {\mathscr{H}}\) and the qualification condition (21) is fulfilled, then there exists \(y^{*}\in \mathcal { G}\), an optimal solution of (20), such that (22) holds and (x∗, Ax∗, y∗) is a saddle point of the Lagrangian l. Conversely, if the pair \((x^{*},y^{*})\in {\mathscr{H}}\times \mathcal { G}\) satisfies relation (22), then x∗ is an optimal solution to (18), y∗ is an optimal solution to (20) and (x∗, Ax∗, y∗) is a saddle point of the Lagrangian l. For further considerations on convex duality, we invite the reader to consult [3‐5, 20, 30].
Furthermore, we discuss some conditions ensuring that (18) has an optimal solution. Suppose that (18) is feasible, which means that its optimal objective value is not \(+\infty \). The existence of optimal solutions to (18) is guaranteed if, for instance, f + h is coercive (that is \(\lim _{\|x\|\rightarrow \infty }(f+h)(x)=+\infty \)) and g is bounded from below. Indeed, under these circumstances, the objective function of (18) is coercive and the statement follows via [3, Corollary 11.15]. On the other hand, if f + h is strongly convex, then the objective function of (18) is strongly convex, too, thus (18) has a unique optimal solution (see [3, Corollary 11.16]).
Some more notations are in order before we state the algorithm for solving Problem 4. We denote by \(\mathcal { S_{+}}({\mathscr{H}})\) the family of operators \(U:{\mathscr{H}}\rightarrow {\mathscr{H}}\) which are linear, continuous, self-adjoint, and positive semidefinite. For \(U\in \mathcal { S_{+}}({\mathscr{H}})\), we consider the semi-norm defined by
If h = 0 and \({M_{1}^{k}}=M_{1}\), \({M_{2}^{k}}=M_{2}\) are constant in each iteration, then Algorithm 3 becomes Algorithm 2, which has been investigated in [28].
(ii)
In order to ensure that the sequence (xk)k≥ 0 is uniquely determined one can assume that for all k ≥ 0, there exists \({\alpha _{1}^{k}}>0\) such that \({M_{1}^{k}} + cA^{*}A \in \mathcal { P}_{{\alpha _{1}^{k}}}({\mathscr{H}})\).
This is in particular the case when
$$ \exists \alpha>0 \text{ such that } A^{*}A\in \mathcal{ P}_{\alpha}(\mathcal{ H}). $$
(26)
Relying on [3, Fact 2.19], on can see that (26) holds if and only if A is injective and ranA∗ is closed. Hence, in finite-dimensional spaces, namely, if \({\mathscr{H}}=\mathbb {R}^{n}\) and \(\mathcal { G}=\mathbb {R}^{m}\), with m ≥ n ≥ 1, (26) is nothing else than saying that A has full column rank.
(iii)
One of the pioneering works addressing proximal ADMM algorithms in Hilbert spaces, in the particular case when h = 0 and \({M_{1}^{k}}\) and \({M_{2}^{k}}\) are equal for all k ≥ 0 to the corresponding identity operators, is the paper by Attouch and Soueycatt [2]. We also refer the reader to [22, 26] for versions of the proximal ADMM algorithm stated in finite-dimensional spaces and with proximal terms induced by constant linear operators.
Remark 6
We show that the particular choices \({M_{1}^{k}}=\frac {1}{\tau _{k}}\text {Id}-cA^{*}A\), for τk > 0, and \({M_{2}^{k}}=0\) for all k ≥ 0 lead to a primal-dual algorithm introduced in [16]. Here, \(\text {Id} : {\mathscr{H}} \rightarrow {\mathscr{H}}\) denotes the identity operator on \({\mathscr{H}}\). Let k ≥ 0 be fixed. The optimality condition for (23) reads (for xk+ 2):
The iterative scheme obtained in (31) and (28) generates, for a given starting point \((x^{1},y^{0})\in {\mathscr{H}} \times \mathcal { G}\) and c > 0, the sequence (xk, yk)k≥ 1 for all k ≥ 0 as follows
For τk = τ > 0 for all k ≥ 1, one recovers a primal-dual algorithm from [16] that has been investigated under the assumption \(\frac {1}{\tau }-c\|A\|^{2}>\frac {L}{2}\) (see Algorithm 3.2 and Theorem 3.1 in [16]). We invite the reader to consult [8, 9, 13, 29] for more insights into primal-dual algorithms and their highlights. Primal-dual algorithms with dynamic step sizes have been investigated in [13] and [9], where it has been shown that clever strategies in the choice of the step sizes can improve the convergence behavior.
3.1 Ergodic convergence rates for the primal-dual gap
In this section, we will provide a convergence rate result for a primal-dual gap function formulated in terms of the associated Lagrangian l. We start by proving a technical statement (see also [28]).
Lemma 7
In the context of Problem 4, let (xk, zk, yk)k≥ 0 be a sequence generated by Algorithm 3. Then, for all k ≥ 0 and all \((x,z,y)\in {\mathscr{H}}\times \mathcal { G}\times \mathcal { G}\), the following inequality holds
The second statement follows easily from the arithmetic-geometric mean inequality in Hilbert spaces (see [28, Proposition 5.3(a)]). □
A direct consequence of the two inequalities in Lemma 7 is the following result.
Lemma 8
In the context of Problem 4, assume that \({M_{1}^{k}}-L\text {Id}\in \mathcal { S_{+}}({\mathscr{H}}), {M_{1}^{k}}\succcurlyeq M_{1}^{k+1}\), \({M_{2}^{k}}\in \mathcal { S_{+}}(\mathcal { G}), {M_{2}^{k}}\succcurlyeq M_{2}^{k+1}\) for all k ≥ 0, and let (xk, zk, yk)k≥ 0 be the sequence generated by Algorithm 3. Then, for all k ≥ 0 and all \((x,z,y)\in {\mathscr{H}}\times \mathcal { G}\times \mathcal { G}\) the following inequality holds
We can now state the main result of this subsection.
Theorem 9
In the context of Problem 4, assume that \({M_{1}^{k}}-L\text {Id}\in \mathcal { S_{+}}({\mathscr{H}}), {M_{1}^{k}}\succcurlyeq M_{1}^{k+1}\), \({M_{2}^{k}}\in \mathcal { S_{+}}(\mathcal { G}), {M_{2}^{k}}\succcurlyeq M_{2}^{k+1}\) for all k ≥ 0, and let (xk, zk, yk)k≥ 0 be the sequence generated by Algorithm 3. For all k ≥ 1 define the ergodic sequences
We fix k ≥ 1 and \((x,z,y)\in {\mathscr{H}}\times \mathcal { G}\times \mathcal { G}\). Summing up the inequalities in Lemma 8 for i = 0,...,k − 1 and using classical arguments for telescoping sums, we obtain
where f(x∗) + h(x∗) + g(Ax∗) is the optimal objective value of the problem (18). Hence, if we suppose that the set of optimal solutions of the dual problem (20) is contained in a bounded set, there exists R > 0 such that for all k ≥ 1
at 0. This set is weakly compact, thus bounded, if 0 ∈int(domψ) = int(A(domf) −domg) (see [3, 5, 30]).
3.2 Convergence of the sequence of generated iterates
In this subsection, we will address the convergence of the sequence of iterates generated by Algorithm 3 (see also [6, Theorem 7]). One of the important tools for the proof of the convergence result will be [15, Theorem 3.3], which we recall below.
Lemma 11
(see [15, Theorem 3.3]) Let S be a nonempty subset of \({\mathscr{H}}\) and (xk)k≥ 0 a sequence in \({\mathscr{H}}\). Let α > 0 and \(W^{k}\in \mathcal { P}_{\alpha }({\mathscr{H}})\) be such that \(W^{k}\succcurlyeq W^{k+1}\) for all k ≥ 0. Assume that:
(i)
For all z ∈ S and for all k ≥ 0: \(\|x^{k+1}-z\|_{W^{k+1}}\leq \|x^{k}-z\|_{W^{k}}\).
(ii)
Every weak sequential cluster point of (xk)k≥ 0 belongs to S.
Then, (xk)k≥ 0 converges weakly to an element in S.
The proof of the convergence result relies on techniques specific to monotone operator theory and does not make use of the values of the objective function or of the Lagrangian l. This makes it different from the proofs in [28] and from the majority of other conventional convergence proofs for ADMM methods. To the few exceptions belong [2] and [19].
Theorem 12
In the context of Problem 4, assume that the set of saddle points of the Lagrangian l is nonempty and that \({M_{1}^{k}}-\frac {L}{2}\text {Id}\in \mathcal { S_{+}}({\mathscr{H}}), {M_{1}^{k}}\succcurlyeq M_{1}^{k+1}\), \({M_{2}^{k}}\in \mathcal { S_{+}}(\mathcal { G}), {M_{2}^{k}}\succcurlyeq M_{2}^{k+1}\) for all k ≥ 0, and let (xk, zk, yk)k≥ 0 be the sequence generated by Algorithm 7. If one of the following assumptions
(I) There exists α1 > 0 such that \({M_{1}^{k}}-\frac {L}{2}\text {Id}\in \mathcal { P}_{\alpha _{1}}({\mathscr{H}})\) for all k ≥ 0.
(II) There exists α,α2 > 0 such that \({M_{1}^{k}}-\frac {L}{2}\text {Id}+A^{*}A\in \mathcal { P}_{\alpha }({\mathscr{H}})\) and \({M_{2}^{k}}\in \mathcal { P}_{\alpha _{2}}(\mathcal { G})\) for all k ≥ 0.
(III) There exists α > 0 such that \({M_{1}^{k}}-\frac {L}{2}\text {Id}+A^{*}A\in \mathcal { P}_{\alpha }({\mathscr{H}})\) and \(2M_{2}^{k+1}\succcurlyeq {M_{2}^{k}}\succcurlyeq M_{2}^{k+1}\) for all k ≥ 0.
is fulfilled, then (xk, zk, yk)k≥ 0 converges weakly to a saddle point of the Lagrangian l. This means that (xk)k≥ 0 converges weakly to an optimal solution of problem (18), and (yk)k≥ 0 converges weakly to an optimal solution of its dual problem (20).
Proof
Let \(S\subseteq {\mathscr{H}}\times \mathcal { G}\times \mathcal { G}\) denote the set of the saddle points of the Lagrangian l and (x∗, z∗, y∗) be a fixed element in S. Then, z∗ = Ax∗ and the optimality conditions hold
We consider first the case L > 0. By the Baillon-Haddad Theorem (see [3, Corollary 18.16]), the gradient of h is L− 1-cocoercive; hence, the following inequality holds
By neglecting the negative terms from the right-hand side of both (39) and (40), it follows that the first assumption in Lemma 11 holds, when applied in the product space \({\mathscr{H}}\times \mathcal { G}\times \mathcal { G}\), for the sequence (xk, zk, yk)k≥ 0, for \(W^{k}:= ({M_{1}^{k}},{M_{2}^{k}}+c\text {Id},c^{-1}\text {Id})\) for k ≥ 0, and for \(S\subseteq {\mathscr{H}}\times \mathcal { G}\times \mathcal { G}\) the set of saddle points of the Lagrangian l.
The relations (42)–(45) will play an essential role in the verification of the second assumption in Lemma 11. Let \((\overline x,\overline z,\overline y)\in {\mathscr{H}}\times \mathcal { G}\times \mathcal { G}\) be such that there exists (kn)n≥ 0, \(k_{n}\rightarrow +\infty \) (as \(n\rightarrow +\infty \)), and \((x^{k_{n}},z^{k_{n}}, y^{k_{n}})\) converges weakly to \((\overline x,\overline z,\overline y)\) (as \(n\rightarrow +\infty \)).
From (42), we obtain that \((Ax^{k_{n}+1})_{n\in \mathbb {N}}\) converges weakly to \(A\overline x\) (as \(n\rightarrow +\infty \)), which combined with (43) yields \(\overline z=A\overline x\). We use now the following notations for all n ≥ 0
hence, \((\overline x,\overline z,\overline y)=(\overline x,A\overline x,\overline y)\) is a saddle point of the Lagrangian l; thus, the second assumption of the Lemma 11 is verified, too. In conclusion, (xk, zk, yk)k≥ 0 converges weakly to a saddle point of the Lagrangian l.
The case when Assumption (II) is valid.
We show that the relations (42)–(45) are fulfilled also in this case. Indeed, Assumption (II) allows to derive from (41) that (43) and (44) hold. From (25), (43), and (44), we obtain (45). Finally, the inequalities
hence, (yk)k≥ 0 and (zk)k≥ 0 are bounded. Combining this with (25) and the condition imposed on \({M_{1}^{k}}-\frac {L}{2}\text {Id}+A^{*}A\), we derive that (xk)k≥ 0 is bounded, too. Hence, there exists a weakly convergent subsequence of (xk, zk, yk)k≥ 0. By using the same arguments as in the proof of (I), it follows that every weak sequential cluster point of (xk, zk, yk)k≥ 0 is a saddle point of the Lagrangian l.
Now, we show that the set of weak sequential cluster points of (xk, zk, yk)k≥ 0 is a singleton. Let (x1, z1, y1),(x2, z2, y2) be two such weak sequential cluster points. Then, there exist (kp)p≥ 0,(kq)q≥ 0, \(k_{p}\rightarrow +\infty \) (as \(p\rightarrow +\infty \)), \(k_{q}\rightarrow +\infty \) (as \(q\rightarrow +\infty \)), a subsequence \((x^{k_{p}},z^{k_{p}}, y^{k_{p}})_{p \geq 0}\) which converges weakly to (x1, z1, y1) (as \(p\rightarrow +\infty \)), and a subsequence \((x^{k_{q}},z^{k_{q}}, y^{k_{q}})_{q \geq 0}\) which converges weakly to (x2, z2, y2) (as \(q\rightarrow +\infty \)). As seen, (x1, z1, y1) and (x2, z2, y2) are saddle points of the Lagrangian l and zi = Axi for i ∈{1,2}. From (52), which is true for every saddle point of the Lagrangian l, we derive
Applying [27, Théorème 104.1], there exists \(M_{1}\in \mathcal { S_{+}}({\mathscr{H}})\) such that \(({M_{1}^{k}})_{k \geq 0}\) converges to M1 in the strong operator topology, i.e., \(\|{M_{1}^{k}} x - M_{1} x\| \to 0\) for all \(x \in {\mathscr{H}}\) (as \(k \to +\infty \)). Similarly, the monotonicity condition imposed on \(({M_{2}^{k}})_{k \geq 0}\) implies that \(\sup _{k\geq 0}\|{M_{2}^{k}}+c\text {Id}\|<+\infty \). Thus, according to [15, Lemma 2.3], there exists \(\alpha ^{\prime }>0\) and \(M_{2}\in \mathcal { P}_{\alpha ^{\prime }}(\mathcal { G})\) such that \(({M_{2}^{k}}+c\text {Id})_{k \geq 0}\) converges to M2 in the strong operator topology (as \(k\rightarrow +\infty \)).
Taking the limit in (53) along the subsequences (kp)p≥ 0 and (kq)q≥ 0 and using the last three relations above, we obtain
we obtain that x1 = x2. In conclusion, (xk, zk, yk)k≥ 0 converges weakly to a saddle point of the Lagrangian l.
The case when Assumption (III) is valid Under Assumption (III), we can further refine the inequalities in (39) and (40). Let k ≥ 1 be fixed. By considering the relation (37) for consecutive iterates and by taking into account the monotonicity of ∂g, we derive
Taking into account that, according to Assumption (III), \(3{M_{2}^{k}}-M_{2}^{k-1}\succcurlyeq {M_{2}^{k}}\), we can conclude that for all k ≥ 1 it holds
Using telescoping sum arguments, we obtain that \(\|x^{k+1}-x^{k}\|_{{M_{1}^{k}}-\frac {L}{2}\text {Id}} \rightarrow 0\), \(y^{k} - y^{k+1} \rightarrow 0\) and \(z^{k} - z^{k+1} \rightarrow 0\) as \(k \rightarrow +\infty \). Using (25), it follows that \(A(x^{k}-x^{k+1}) \rightarrow 0\) as \(k \rightarrow +\infty \), which, combined with the fact that \({M_{1}^{k}}-\frac {L}{2}\text {Id} + A^{*}A \in \mathcal { P}_{\alpha }(\mathcal { {H}})\), for all k ≥ 0, yields \(x^{k}-x^{k+1} \rightarrow 0\) as \(k \rightarrow +\infty \). Consequently, \(z^{k} - Ax^{k+1} \rightarrow 0\) as \(k \rightarrow +\infty \). Hence, the relations (42)–(45) are fulfilled. On the other hand, from both (56) and (57), we derive
it follows that \(\lim _{k\rightarrow +\infty } \|z^{k}-z^{k-1}\|_{M_{2}^{k-1}}^{2} = 0\), which further implies that (52) holds. From here, the conclusion follows by arguing as in the proof provided in the setting of Assumption (II). □
Remark 13
Choosing as in Remark 6, \({M_{1}^{k}}= \frac {1}{\tau _{k}}\text {Id} - cA^{*}A\), with τk > 0 and such that \(\tau :=\sup _{k \geq 0} \tau _{k} \in \mathbb {R}\), and \({M_{2}^{k}} = 0\) for all k ≥ 0, we have
which means that under the assumption \(\frac {1}{\tau }-c\|A\|^2>\frac {L}{2}\) (which recovers the one in Algorithm 3.2 and Theorem 3.1 in [16]), the operators \(M_1^k-\frac {L}{2}\text {Id}\) belong for all k ≥ 0 to the class \(\mathcal { P}_{\alpha _1}({\mathscr{H}})\), with \(\alpha _1:= \frac {1}{\tau }-c\|A\|^2-\frac {L}{2}>0\).
Remark 14
By taking h = 0 and L = 0, and in each iteration constant operators \(M_1^k = M_1 \succcurlyeq 0\) and \(M_2^k = M_2 \succcurlyeq 0\) for all k ≥ 0, Theorem 12 in the context of Assumption (I) covers the first situation investigated in [28, Theorem 5.6], where in finite-dimensional spaces the matrix M1 was assumed to be positive definite and the matrix M2 to be positive semidefinite.
The arguments used in [28, Theorem 5.6] for proving convergence in the case when M1 = 0 and A has full column rank contain flaws and rely on incorrect statements. Theorem 12 provides in the context of Assumption (III) (for h = 0, L = 0, \(M_1^k=0\) and \(M_2^k = M_2 \succcurlyeq 0\) for all k ≥ 0) the correct proof of this result.
Finally, we notice that the convergence theorem for the iterates of the classical ADMM algorithm (which corresponds to the situation when h = 0, L = 0, M1 = M2 = 0 and A has full column rank, see for example [19]) is covered by Theorem 12 in the context of Assumption (III).
Acknowledgments
Open access funding provided by Austrian Science Fund (FWF). The authors are thankful to two anonymous reviewers and the handling editor for comments and remarks which have improved the quality of the paper.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
