1. Introduction
In this paper, we consider the convex programming with separable functions:
(1)
where
(
i = 1,2, ā¦,
m) are closed proper convex functions (not necessarily smooth);
(
i = 1,2, ā¦,
m);
(
i = 1,2, ā¦,
m) are closed convex sets;
b ā
āl and
. Throughout the paper, we assume that the solution set of (
1) is nonempty.
For the special case of (
1) with
m = 2,
(2)
the problem has been studied extensively. Among lots of numerical methods, one of the most popular methods is the alternating direction method of multipliers (ADMM) which was presented originally in [
1,
2]. The iterative scheme of ADMM for (
2) is as follows:
(3)
where
Ī»k is Lagrange multiplier associated with the linear constraints and
Ī² > 0 is the penalty parameter. The convergence of ADMM for (
2) was also established under the condition that the involved functions are convex and the constrained sets are convex too.
While there are diversified applications whose objective function is separable into
m ā„ 3 individual convex functions without coupled variables, such as traffic problems, the problem of recovering the low-rank, sparse components of matrices from incomplete and noisy observation in [
3], the constrained total-variation image restoration and reconstruction problem in [
4,
5], and the minimal surface PDE problem in [
6], it is thus natural to extend ADMM from 2 blocks to
m blocks, resulting in the iterative scheme:
(4)
Unfortunately, the convergence of the natural extension is still open under convex assumption, and the recent convergence results [7] are under the assumption that all the functions involved in the objective functions are strongly convex. This lack of convergence has inspired some ADM-based methods, for example, prediction-correction type method [3, 8ā11], that is, the iterate is regarded as a prediction, and the next iterate is a correction for it. However, the numerical results show that the algorithm (4) always performs better than these variants. Recently, Han and Yuan [7] show that the global convergence of the extension of ADMM for m ā„ 3 is valid if the involved functions are further assumed to be strongly convex. This result does not answer the open problem regarding the convergence of the extension of ADMM under the convex assumption, but it makes a key progress towards this objective.
In this paper, we consider the separable convex optimization problem (
1) where each individual function
fi is the combination of a strongly convex function
gi and a linear transform
Bi. That is, (
1) takes the following form:
(5)
where
(
i = 1,2, ā¦,
m) are closed proper strongly convex function with the modulus
Ī¼i (not necessarily smooth);
(
i = 1,2, ā¦,
m);
(
i = 1,2, ā¦,
m) are closed convex sets;
b ā
āl and
;
(
i = 1,2, ā¦,
m), where
Bi may not have full column rank (if
Bi has full column rank, the composite function is strongly convex and reduces to the case considered in [
7]). Note that although (
5) is very special, it arises frequently from many applications. One example is under the route-based traffic assignment problem [
12], where
gi is the link traffic cost,
Bi is the link-path incidence matrix, and
x is the path follow vector.
In the following, we abuse a little the notation and still write
gi with
fi; that is, the problem under consideration is
(6)
where
(
i = 1,2, ā¦,
m) are closed proper strongly convex function with the modulus
Ī¼i (not necessarily smooth).
The rest of the paper is organized as follows. In the next section, we list some necessary preliminary results that will be used in the rest of the paper. We then describe the algorithm formally and analyze its global convergence under reasonable conditions in Section 3. We complete the paper with some conclusions in Section 4.
2. Preliminaries
In this section, we summarize some basic concepts and their properties that will be useful for further discussion.
Let ā„Ā·ā„p denote the standard definition of the lp-norm, and particularly, let ā„Ā·ā„ = ā„Ā·ā„2 denote the Euclidean norm. For a symmetric and positive definite matrix G, we denote ā„Ā·ā„G the G-norm, that is, . If G is the product of a positive parameter Ī² and the identity matrix I, that is, G = Ī²I, we use the simpler notation: ā„Ā·ā„G = ā„Ā·ā„Ī².
Let
f :
ān ā
ā āŖ {+
ā}. If the domain of
f denoted by domā
f = {
x ā
ānā£
f(
x)<+
ā} is not empty, then
f is said to be proper. If for any
x ā
ān and
y ā
ān, we have
(7)
then
f is said to be convex. Furthermore,
f is said to be strongly convex with the modulus
Ī¼ > 0 if and only if
(8)
A set-valued operator
T defined on
ān is said to be monotone if and only if
(9)
and
T is said to be strongly monotone with modulus
Ī¼ > 0 if and only if
(10)
Let Ī
0(
ān) denote the set of closed proper convex functions from
ān to
ā āŖ {+
ā}. For any
f ā Ī
0(
ān), the subdifferential of
f which is the set-valued operator, defined by
(11)
is monotone. Moreover, if
f is strongly convex function with the modulus
Ī¼,
āf is strongly monotone with the modulus
Ī¼.
Let
F be a mapping from a set
Ī© ā
ān ā
ān. Then
F is said to be co-coercive on
Ī© with modulus
Ī³ > 0, if
(12)
Throughout the paper, we make the following assumptions.
Assumption 1. (i) niā„Bixiā„ ā„ ā„Aiā„ā„xiā„, , i ā {1,2, ā¦, m}; (ii) the solution set of (1) is nonempty.
Remark 2. Assumption 1 is a little restrictive. However, some problems can satisfy it. A remarkable one is the following route-based traffic assignment problem.
Consider a transportation network G(š©, E), where š© is the set of nodes. We denote the set of links by š, and the number of the element of š by Nš, respectively. Let RS denote the set of origin-destination (O-D) pairs. For an O-D pair rs ā RS, let qrs be its traffic demand; let Prs be the set of routes connecting rs, and p ā Prs; š©rs denotes the number of the routes connecting rs; let be the route flow on p. The feasible route flow vector h = (p ā Prsā£rs ā RS) is thus given by
(13)
Define
E as the link-route incidence matrix such that
(14)
Then, link flow
fa can be written as
(15)
By denoting the link cost function as
Ca(
f) and for the additive case, the route cost function as
Cp(
h), they can be related by
(16)
The user equilibrium traffic assignment problem can be formulated as a VI: find
f* ā
F such that
(17)
or equivalently, find
h* ā
H such that
(18)
where
C = {
Ca} is the vector of the link cost function.
In general, it is easy to show that e is a row of E and E is not a full column rank (if E is, then the above variational inequality is strongly monotone).
For simplicity, in the following, we only consider the case for m = 3. Notice that for m ā„ 3, it can be proved similarly following the processing of m = 3.
3. The Method
In this section, we consider the following convex minimization problem with linear constraint, where the objective function is in the form of the sum of three individual functions without coupled variable:
(19)
where
(
i = 1,2, 3) are closed proper strongly convex function with the modulus
Ī¼i (not necessarily smooth);
(
i = 1,2, 3),
(
i = 1,2, 3);
(
i = 1,2, 3) are closed convex sets;
b ā
āl and
.
The iterative scheme of ADMM for problem (
19) is as follows:
(20)
where
Ī»k is the Lagrangian multiplier associated with the linear constraints and
Ī² > 0 is the penalty parameter.
4. Convergence
In this section, we prove the convergence of the extended ADMM for problem (
19). As the assumptions aforementioned, by invoking the first-order necessary and sufficient condition for convex programming, we easily see that the problem (
19) under the condition is characterized by the following variational inequality (VI): find
u* ā
š° and
such that
(21)
where
(22)
We denote the VI (
21)-(
22) by MVI(
š°,
Q).
Similarly, in [
7], we propose an easily implementable stopping criterion for executing (
20):
(23)
and its rationale can be seen in the following lemma.
Lemma 3 (see [7].)If and (i = 1,2, 3), then is a solution of MVI(š°, Q).
Lemma 3 implies that the iterate is a solution of MVI(š°, Q) when the inequality (23) holds with Ļµ = 0. Some techniques of establishing the error bounds in [13] can help us analyze how precisely the iterate satisfies the optimality conditions when the proposed stopping criterion is satisfied with a tolerance Ļµ > 0.
Lemma 4. Let be the solution of the problem (19), and let Ī»* be a corresponding Lagrange multiplier associated with the linear constraint. Then, the sequence generated by (20) satisfies
(24)
Proof. By invoking the first-order optimality condition for the related subproblem in (20), for any xi ā š³i, i = 1,2, 3, we get
(25)
Setting
(
i = 1,2, 3) in (
25), we have
(26)
On the other hand, setting
in (
21), it follows that
(27)
Adding (
26) and (
27), we obtain
(28)
With the rearrangement of the above inequalities, we derive that
(29)
Adding the above inequalities (
29), we have
(30)
The proof is complete.
Hereafter, we define a matrix which will make the notation of proof more succinct. More specifically, let
(31)
Obviously,
M is a positive semidefinite matrix, only for analysis convenience; we denote
(32)
Lemma 5. Let be a solution of MVI(š°, Q), and let the sequence be generated by (20). Then, one has
(33)
Proof. From (20) and Lemma 4, we have
(34)
Since
(35)
and
, we can get
(36)
Using Cauchy-Schwarz inequality, we have
(37)
Substituting (
36) and (
37) into (
34), we get
(38)
Since fi is strongly convex, from the strong monotonicity of the subdifferential mapping āfi (with the modulus Ī¼i), then we have
(39)
where
,
, for any
i ā {1,2, 3}.
By using the notion of , from (38) we have
(40)
The proof is complete.
Theorem 6. Under Assumption 1, for any
(41)
the sequence
generated by (
20) converges to a solution of MVI(
š°,
Q).
Proof. From Lemma 5, we have
(42)
where
(43)
From Assumption
1, it follows that
(44)
Consequently,
(45)
From (
45), we have
(46)
which means that the generated sequence {
uk} is bounded.
Furthermore, it follows that
(47)
which means that
(48)
Therefore, we have
(49)
Since ā„
Aiā„ is nonzero and bounded, from (
48) we have
(50)
Since {
uk} is bounded, {
Ī»k} has at least one cluster point, say
. Let
be the corresponding subsequence that converges to
. Taking a limit along this subsequence in (
25) and (
49), we obtain
,
(51)
which follows that
is an optimal Lagrange multiplier. Since
Ī»* is arbitrary, we can set
in (
46) and conclude that the whole generated sequence converges to a solution of MVI(
š°,
Q).
5. Conclusions
In this paper, we extend the convergence analysis of the ADMM for the separable convex optimization problem with strongly convex functions to the case in which the individual functions are composites of strongly convex functions with a linear transform. Under further assumptions, we established the global convergence of the algorithm.
It should be admitted that although some problems arising from applications such as traffic assignment fall into our analysis, the problems considered here are too special. Thus, it is far away to solve the open problem of convergence of the ADMM with more than three blocks.
Acknowledgments
Xingju Cai was supported by the National Natural Science Foundation of China (NSFC) Grants nos. 11071122 and 11171159 and by the Doctoral Fund of Ministry of Education of China no. 20103207110002.
