# Sensitivity Analysis of the Proximal-Based Parallel Decomposition Methods

Authors: Feng Ma; Mingfang Ni; Lei Zhu; Zhanke Yu
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

The proximal-based parallel decomposition methods were recently proposed to solve structured convex optimization problems. These algorithms are eligible for parallel computation and can be used efficiently for solving large-scale separable problems. In this paper, compared with the previous theoretical results, we show that the range of the involved parameters can be enlarged while the convergence can be still established. Preliminary numerical tests on stable principal component pursuit problem testify to the advantages of the enlargement.


---

## Body

## 1. Introduction

Consider the constrained convex optimization problems with separable objective functions in the following form:(1)
min
⁡
x
∈
𝒳
,
y
∈
𝒴
f
(
x
)
+
g
(
y
)
ll
,
s
.
t
.
A
x
+
B
y
=
b
,
where A
∈
ℜ
m
×
n, B
∈
ℜ
m
×
p, b
∈
ℜ
m, 𝒳
⊂
ℜ
n, and 𝒴
⊂
ℜ
p, are two nonempty, closed, and convex sets and f
:
ℜ
n
→
ℜ, g
:
ℜ
p
→
ℜ are convex functions. Problem of this type arises from a number of fields such as signal processing, compressed sensing, machine learning, and semidefinite programming (see, e.g., [1–7] and references cited therein).To solve (1), the classical alternating direction method generates the new iterate via the following scheme:
(2)
x
k
+
1
=
arg
min
⁡
x
∈
𝒳
f
(
x
)
+
g
(
y
k
)
+
β
2
∥
A
x
+
B
y
k
-
b
-
1
β
λ
k
∥
2
,
y
k
+
1
=
arg
min
⁡
y
∈
𝒴
f
(
x
k
+
1
)
+
g
(
y
)
+
β
2
∥
A
x
k
+
1
+
B
y
-
b
-
1
β
λ
k
∥
2
,
λ
k
+
1
=
λ
k
-
β
(
A
x
k
+
1
+
B
y
k
+
1
-
b
)
,
where λ
∈
ℜ
m is the Lagrange multiplier associated with the linear constraint and β
>
0 is a penalty parameter for the violation of the linear constraint.At each iteration, ADM essentially splits the subproblem of the augmented Lagrangian method into two subproblems in Gauss-Seidel fashion. The subproblems can be solved in consecutive order, which makes ADM possible to exploit the individual structure off and g. The decomposed subproblems in (2) are often easy when A and B in (1) are both identity matrices and the resolvent operators of f and g have closed-form solutions or can be efficiently solved up to a high precision. Here, the resolvent operator of a function (say, θ
ℜ
n
→
ℜ) is defined by
(3)
(
I
+
1
β
∂
θ
)
-
1
(
υ
)
=
arg
min
⁡
z
∈
𝒵
θ
(
z
)
+
β
2
∥
z
-
υ
∥
2
,
where υ
∈
𝒵 and β
>
0. However, in some cases, both A and B are not identity matrices; the two subproblems in ADM (2) are difficult to solve because the evaluation of the following minimization style
(4)
(
M
T
M
+
1
β
∂
θ
)
-
1
(
M
υ
)
=
arg
min
⁡
z
∈
𝒵
θ
(
z
)
+
β
2
∥
M
z
-
υ
∥
2
could be costly, where M is a given nonidentity matrix, for example, A or B.For the purpose of parallel and easy computing, the first parallel decomposition method [8] (abbreviated as FPDM) generates the new iterative as follows:
(5)
x
k
+
1
=
arg
min
⁡
x
∈
𝒳
f
(
x
)
+
β
(
x
-
x
k
)
T
(
A
T
(
A
x
k
+
B
y
k
-
b
-
1
β
λ
k
)
)
+
r
2
∥
x
-
x
k
∥
2
,
y
k
+
1
=
arg
min
⁡
y
∈
𝒴
g
(
y
)
+
β
(
y
-
y
k
)
T
(
B
T
(
A
x
k
+
B
y
k
-
b
-
1
β
λ
k
)
)
+
s
2
∥
y
-
y
k
∥
2
,
λ
k
+
1
=
λ
k
-
β
(
A
x
k
+
1
+
B
y
k
+
1
-
b
)
,
where the parameters r, s are required to satisfy r
>
2
β
∥
A
T
A
∥ and s
>
2
β
∥
B
T
B
∥. Here, ∥
C
∥ denotes the largest eigenvalue of matrix C. It is easy to verify that the proximal-based decomposition method proposed in [9] is a special case of the FPDM.When (4) is easy to evaluate for f and g, the second parallel decomposition method [8] (abbreviated as SPDM) can be used, which generates the new iterative as follows:
(6)
x
k
+
1
=
arg
min
⁡
x
∈
𝒳
f
(
x
)
+
β
2
∥
A
x
+
B
y
k
-
b
-
1
β
λ
k
∥
+
r
2
∥
x
-
x
k
∥
2
,
y
k
+
1
=
arg
min
⁡
y
∈
𝒴
g
(
y
)
+
β
2
∥
A
x
k
+
B
y
-
b
-
1
β
λ
k
∥
+
s
2
∥
y
-
y
k
∥
2
,
λ
k
+
1
=
λ
k
-
β
(
A
x
k
+
1
+
B
y
k
+
1
-
b
)
,
where the parameters r, s are required to satisfy r
>
β
∥
A
T
A
∥ and s
>
β
∥
B
T
B
∥.Note that the subproblems in FPDM and SPDM can be processed in a parallelized fashion because the first subproblem involvingx is independent on the second subproblem involving y. Thus, FPDM and SPDM are suitable for solving large-scale distributed machine learning and big-data-related optimization problems.ADM was first described in [10] and is closely related to many other algorithms, such as augmented Lagrangian methods, proximal point algorithm [11], and split Bregman methods [12]. Recently, the convergence of ADM has been analyzed under certain assumptions (see, e.g., [13–16]) and the direct extension of ADM for multiblock convex minimization problems has already been proved not necessarily convergent [17].In this paper, we study the proximal-based parallel decomposition methods from the perspective of variational inequalities. We show that the requirement ranges of the parametersr,  s, and β can be significantly enlarged. Our contributions are as follows.(i)
For the FPDM, we show that the requirements of the step sizesr, s, and β can be uniformly relaxed by
(7)
β
∥
A
T
A
∥
r
+
β
∥
B
T
B
∥
s
∈
(
0,1
)
.
(ii)
For the SPDM, we show that the requirements of the step sizesr, s, and β can be uniformly relaxed by
(8)
β
∥
A
T
A
∥
r
+
β
∥
A
T
A
∥
+
β
∥
B
T
B
∥
s
+
β
∥
B
T
B
∥
∈
(
0,1
)
.
(iii)
We provide a new application example in machine learning, that is, stable principal component pursuit problem. Preliminary numerical experiments testify to the advantages of the enlargement.The rest of this paper is organized as follows. In Section2 we derive a variational reformulation of (1) and summarize some preliminaries of variational inequalities. In Section 3, we describe our main theoretical results and analyze their convergence. We report some numerical results in Section 4 and make some conclusions in Section 5.


## 2. Preliminaries

### 2.1. Variational Inequality Characterization

In this section, we derive a variational reformulation of (1) which will be used in subsequent analysis.Since the functionsf and g are all assumed to be convex, by invoking the first-order optimality condition for (1), we can easily verify that solving (1) amounts to finding a vector μ
*
∈
Ω of the variational inequality (VI):
(9)
(
μ
′
-
μ
*
)
T
F
(
μ
*
)
≥
0
,
∀
μ
′
∈
Ω
,
with
(10)
μ
∶
=
(
x
y
λ
)
,
F
(
μ
)
∶
=
(
∂
f
(
x
)
-
A
T
λ
∂
g
(
y
)
-
B
T
λ
A
x
+
B
y
-
b
)
,
where
(11)
Ω
=
𝒳
×
𝒴
×
ℜ
m
.The problem (9) is referred to as a structured variational inequality (SVI) and has been studied extensively both in the theoretical frameworks and applications. Recently, He et al. [18, 19] proposed a unified framework of proximal-like contraction methods for monotone VI. They also construct the O
(
1
/
t
) convergence rate of the projection and contraction methods for VI with Lipschitz continuous monotone operators [20]. Xu et al. [21] proposed two classes of correction methods for the SVI in which the mapping F does not have an explicit form. Yuan and Li [22] developed a logarithmic-quadratic proximal (LQP) based decomposition method by applying the LQP terms to regularize the ADM subproblems. Tao and Yuan [23] established the O
(
1
/
t
) convergence rate of ADM with LQP regularization. Bnouhachem et al. [24] studied a new inexact LQP alternating direction method by solving a series of related systems of nonlinear equations.


### 2.2. Some Properties of Variational Inequalities

In this section, we summarize some basic knowledge and related definitions of variational inequalities.LetG be a symmetric positive definite matrix; the G-norm of the vector μ is denoted by ∥
μ
∥
G
∶
=
〈
μ
,
G
μ
〉. In particular, when G
=
I, ∥
μ
∥
∶
=
〈
μ
,
μ
〉 is the Euclidean norm of μ. Let P
Ω
,
G
(
·
) be the projection operator onto Ω under the G-norm; that is,
(12)
P
Ω
,
G
(
ν
)
=
arg
min
⁡
⁡
{
∥
μ
-
ν
∥
G
∣
μ
∈
Ω
}
.
From the above definition, we have the following well-known properties:
(13)
(
μ
′
-
P
Ω
,
G
(
μ
′
)
)
T
G
(
μ
-
P
Ω
,
G
(
μ
′
)
)
≤
0
(
μ
′
-
P
Ω
,
G
(
u
′
)
)
T
G
∀
μ
′
∈
ℜ
l
,
∀
μ
∈
Ω
,
∥
P
Ω
,
G
(
μ
)
-
P
Ω
,
G
(
μ
′
)
∥
G
≤
∥
μ
-
μ
′
∥
G
,
∀
μ
,
μ
′
∈
ℜ
l
,
∥
μ
-
P
Ω
,
G
(
μ
′
)
∥
G
2
≤
∥
μ
-
μ
′
∥
G
2
-
∥
μ
′
-
P
Ω
,
G
(
μ
′
)
∥
G
2
,
∥
μ
-
P
Ω
,
G
(
μ
′
)
∥
G
2
≤
∥
μ
-
μ
′
∥
∀
μ
′
∈
ℜ
l
,
∀
μ
∈
Ω
.The mappingF is said to be monotone with respect to Ω if
(14)
(
μ
-
ν
)
T
(
F
(
μ
)
-
F
(
ν
)
)
≥
0
,
∀
μ
,
ν
∈
Ω
.The following lemma [25, page 267] states an important result which characterizes a VI by a projection equation.Lemma 1.
LetΩ be a closed convex set in ℜ
l and let G be any positive definite matrix; then μ
* is a solution of VI(Ω
,
F) if and only if it satisfies
(15)
μ
*
=
P
Ω
,
G
(
μ
*
-
α
G
-
1
F
(
μ
*
)
)
,
∀
α
>
0
.


## 2.1. Variational Inequality Characterization

In this section, we derive a variational reformulation of (1) which will be used in subsequent analysis.Since the functionsf and g are all assumed to be convex, by invoking the first-order optimality condition for (1), we can easily verify that solving (1) amounts to finding a vector μ
*
∈
Ω of the variational inequality (VI):
(9)
(
μ
′
-
μ
*
)
T
F
(
μ
*
)
≥
0
,
∀
μ
′
∈
Ω
,
with
(10)
μ
∶
=
(
x
y
λ
)
,
F
(
μ
)
∶
=
(
∂
f
(
x
)
-
A
T
λ
∂
g
(
y
)
-
B
T
λ
A
x
+
B
y
-
b
)
,
where
(11)
Ω
=
𝒳
×
𝒴
×
ℜ
m
.The problem (9) is referred to as a structured variational inequality (SVI) and has been studied extensively both in the theoretical frameworks and applications. Recently, He et al. [18, 19] proposed a unified framework of proximal-like contraction methods for monotone VI. They also construct the O
(
1
/
t
) convergence rate of the projection and contraction methods for VI with Lipschitz continuous monotone operators [20]. Xu et al. [21] proposed two classes of correction methods for the SVI in which the mapping F does not have an explicit form. Yuan and Li [22] developed a logarithmic-quadratic proximal (LQP) based decomposition method by applying the LQP terms to regularize the ADM subproblems. Tao and Yuan [23] established the O
(
1
/
t
) convergence rate of ADM with LQP regularization. Bnouhachem et al. [24] studied a new inexact LQP alternating direction method by solving a series of related systems of nonlinear equations.


## 2.2. Some Properties of Variational Inequalities

In this section, we summarize some basic knowledge and related definitions of variational inequalities.LetG be a symmetric positive definite matrix; the G-norm of the vector μ is denoted by ∥
μ
∥
G
∶
=
〈
μ
,
G
μ
〉. In particular, when G
=
I, ∥
μ
∥
∶
=
〈
μ
,
μ
〉 is the Euclidean norm of μ. Let P
Ω
,
G
(
·
) be the projection operator onto Ω under the G-norm; that is,
(12)
P
Ω
,
G
(
ν
)
=
arg
min
⁡
⁡
{
∥
μ
-
ν
∥
G
∣
μ
∈
Ω
}
.
From the above definition, we have the following well-known properties:
(13)
(
μ
′
-
P
Ω
,
G
(
μ
′
)
)
T
G
(
μ
-
P
Ω
,
G
(
μ
′
)
)
≤
0
(
μ
′
-
P
Ω
,
G
(
u
′
)
)
T
G
∀
μ
′
∈
ℜ
l
,
∀
μ
∈
Ω
,
∥
P
Ω
,
G
(
μ
)
-
P
Ω
,
G
(
μ
′
)
∥
G
≤
∥
μ
-
μ
′
∥
G
,
∀
μ
,
μ
′
∈
ℜ
l
,
∥
μ
-
P
Ω
,
G
(
μ
′
)
∥
G
2
≤
∥
μ
-
μ
′
∥
G
2
-
∥
μ
′
-
P
Ω
,
G
(
μ
′
)
∥
G
2
,
∥
μ
-
P
Ω
,
G
(
μ
′
)
∥
G
2
≤
∥
μ
-
μ
′
∥
∀
μ
′
∈
ℜ
l
,
∀
μ
∈
Ω
.The mappingF is said to be monotone with respect to Ω if
(14)
(
μ
-
ν
)
T
(
F
(
μ
)
-
F
(
ν
)
)
≥
0
,
∀
μ
,
ν
∈
Ω
.The following lemma [25, page 267] states an important result which characterizes a VI by a projection equation.Lemma 1.
LetΩ be a closed convex set in ℜ
l and let G be any positive definite matrix; then μ
* is a solution of VI(Ω
,
F) if and only if it satisfies
(15)
μ
*
=
P
Ω
,
G
(
μ
*
-
α
G
-
1
F
(
μ
*
)
)
,
∀
α
>
0
.


## 3. Theoretical Results of the Relaxation

In this section, we show that the range of the parametersr, s, and β can be enlarged in FPDM and SPDM, which is broader than the previous theoretical results. We also establish the global convergence of FPDM and SPDM under the new conditions for the parameters.


### 3.1. The Parameters Relaxation of the FPDM

From (5), the subproblems of FPDM can be, respectively, characterized by the following VI form: find μ
k
+
1
=
(
x
k
+
1
,
y
k
+
1
,
λ
k
+
1
)
T
∈
Ω such that
(16)
(
μ
′
-
μ
k
+
1
)
T
{
F
(
μ
k
+
1
)
+
η
I
(
μ
k
+
1
,
μ
k
)
-
G
(
μ
k
-
μ
k
+
1
)
}
≥
0
,
η
I
(
μ
k
+
1
,
μ
k
)
η
I
(
μ
k
+
1
,
μ
k
)
η
I
(
μ
k
+
1
,
μ
k
)
η
I
(
μ
k
+
1
,
μ
k
)
∀
μ
′
∈
Ω
,
with
(17)
η
I
(
μ
k
+
1
,
μ
k
)
=
β
(
A
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
B
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
0
)
,
G
I
=
(
r
I
n
s
I
p
β
-
1
I
m
)
,
where η
I
(
μ
k
+
1
,
μ
k
)
∈
ℜ
(
n
+
p
+
m
) and G
I
∈
ℜ
(
n
+
p
+
m
)
×
(
n
+
p
+
m
) is a positive definite matrix.Lemma 2.
For a givenμ
k
=
(
x
k
,
y
k
,
λ
k
)
T, let μ
k
+
1
=
(
x
k
+
1
,
y
k
+
1
,
λ
k
+
1
)
T be generated by (16) and (17). If
(18)
u
I
=
β
∥
A
T
A
∥
r
+
β
∥
B
T
B
∥
s
∈
(
0,1
)
,
then for any μ
*
=
(
x
*
,
y
*
,
λ
*
)
T, one has
(19)
(
μ
k
+
1
-
μ
*
)
T
η
I
(
μ
k
+
1
,
μ
k
)
≤
u
I
2
∥
μ
k
-
μ
k
+
1
∥
G
I
2
.Proof.
SinceA
x
*
+
B
y
*
=
b and β
(
A
x
k
+
1
+
B
y
k
+
1
-
b
)
=
λ
k
-
λ
k
+
1 one has
(20)
(
μ
k
+
1
-
μ
*
)
T
η
I
(
μ
k
+
1
,
μ
k
)
μ
k
+
1
=
β
(
x
k
+
1
-
x
*
y
k
+
1
-
y
*
λ
k
+
1
-
λ
*
)
T
μ
k
+
1
μ
k
+
1
×
(
A
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
B
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
0
)
μ
k
+
1
=
(
λ
k
-
λ
k
+
1
)
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
.
Applying the Cauchy-Schwarz inequality to the right term, we get
(21)
(
μ
k
+
1
-
μ
*
)
T
η
I
(
μ
k
+
1
,
μ
k
)
≤
|
(
λ
k
-
λ
k
+
1
)
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
|
≤
1
2
{
1
2
2
|
(
λ
k
-
λ
k
+
1
)
T
A
(
x
k
-
x
k
+
1
)
|
}
+
1
2
{
2
|
(
λ
k
-
λ
k
+
1
)
T
B
(
y
k
-
y
k
+
1
)
|
}
≤
1
2
{
∥
A
T
A
∥
u
I
r
|
λ
k
-
λ
k
+
1
|
2
+
u
I
r
∥
A
T
A
∥
|
A
(
x
k
-
x
k
+
1
)
|
2
}
+
1
2
{
∥
B
T
B
∥
u
I
s
|
λ
k
-
λ
k
+
1
|
2
+
u
I
s
∥
B
T
B
∥
|
B
(
y
k
-
y
k
+
1
)
|
2
}
=
1
2
{
(
∥
A
T
A
∥
u
I
r
+
∥
B
T
B
∥
u
I
s
)
|
λ
k
-
λ
k
+
1
|
2
∥
A
T
∥
+
u
I
r
∥
A
T
A
∥
|
A
(
x
k
-
x
k
+
1
)
|
2
+
u
I
s
∥
B
T
B
∥
|
B
(
y
k
-
y
k
+
1
)
|
2
}
≤
1
2
{
(
∥
A
T
A
∥
u
I
r
+
∥
B
T
B
∥
u
I
s
)
|
λ
k
-
λ
k
+
1
|
2
+
u
I
r
|
x
k
-
x
k
+
1
|
2
∥
A
T
A
∥
+
u
I
s
|
y
k
-
y
k
+
1
|
2
(
∥
A
T
A
∥
u
I
r
+
∥
B
T
B
∥
u
I
s
)
}
=
1
2
{
u
I
β
|
λ
k
-
λ
k
+
1
|
2
+
u
I
r
|
x
k
-
x
k
+
1
|
2
+
u
I
s
|
y
k
-
y
k
+
1
|
2
}
=
u
I
2
∥
μ
k
-
μ
k
+
1
∥
G
I
2
.Theorem 3.
Let the sequence{
μ
k
} be generated by FPDM (16) and (17). If
(22)
u
I
=
β
∥
A
T
A
∥
r
+
β
∥
B
T
B
∥
s
∈
(
0,1
)
,
then one has
(23)
∥
μ
k
+
1
-
μ
*
∥
G
I
2
≤
∥
μ
k
-
μ
*
∥
G
I
2
-
(
1
-
u
I
)
∥
μ
k
-
μ
k
+
1
∥
G
I
2
,
∀
μ
*
∈
Ω
*
.Proof.
Consider(24)
∥
μ
k
+
1
-
μ
*
∥
G
I
2
=
∥
μ
k
+
1
-
μ
k
+
μ
k
-
μ
*
∥
G
I
2
(25)
=

∥
μ
k
-
μ
*
∥
G
I
2

-
2
(
μ
k
-
μ
*
)
T
G
I
(
μ
k
-
μ
k
+
1
)
+
∥
μ
k
+
1
-
μ
k
∥
G
I
2
.
On the other hand, by setting μ
′
=
μ
* in (16), we have
(26)
(
μ
k
+
1
-
μ
*
)
T
G
(
μ
k
-
μ
k
+
1
)
≥
(
μ
k
+
1
-
μ
*
)
T
F
(
μ
k
+
1
)
+
(
μ
k
+
1
-
μ
*
)
η
I
(
μ
k
+
1
,
μ
k
)
.
Using the fact that F is a monotone operator, we have
(27)
(
μ
k
+
1
-
μ
*
)
T
F
(
μ
k
+
1
)
≥
(
μ
k
+
1
-
μ
*
)
T
F
(
μ
*
)
≥
0
.
With rearrangement of the term (26) and using (27), we derive that
(28)
(
μ
k
-
μ
*
)
T
G
(
μ
k
-
μ
k
+
1
)
≥
(
μ
k
-
μ
k
+
1
)
T
G
(
μ
k
-
μ
k
+
1
)
+
(
μ
k
+
1
-
μ
*
)
η
I
(
μ
k
+
1
,
μ
k
)
.
Substituting (28) into (24), we get
(29)
∥
μ
k
+
1
-
μ
*
∥
G
I
2
≤
∥
μ
k
-
μ
*
∥
G
I
2
-
2
(
μ
k
+
1
-
μ
*
)
η
I
(
μ
k
+
1
,
μ
k
)
-
∥
μ
k
+
1
-
μ
k
∥
G
I
2
.
With Lemma 1, substituting (19) into (29), we get
(30)
∥
μ
k
+
1
-
μ
*
∥
G
I
2
≤
∥
μ
k
-
μ
*
∥
G
I
2
-
(
1
-
u
I
)
∥
μ
k
-
μ
k
+
1
∥
G
I
2
,
which completes the proof.Remark 4.
Compared to the requirement of the parametersr, s, β in [8], we now allow the step sizes r, s, β to be chosen according to rule (7). In fact, the restriction on r and s proposed in [8] is
(31)
r
>
2
β
∥
A
T
A
∥
,
s
>
2
β
∥
B
T
B
∥
,
which is a special case of the rule (18), since
(32)
β
∥
A
T
A
∥
r
+
β
∥
B
T
B
∥
s
<
β
∥
A
T
A
∥
2
β
∥
A
T
A
∥
+
β
∥
B
T
B
∥
2
β
∥
B
T
B
∥
=
1
;
that is, u
I
∈
(
0,1
). Hence, the requirement on the parameters is significantly relaxed.


### 3.2. The Parameters Relaxation of the SPDM

In this subsection, we extend our analysis to the SPDM. From (5), the subproblems of SPDM can be characterized by the following VI form: find μ
k
+
1
=
(
x
k
+
1
,
y
k
+
1
,
λ
k
+
1
)
T
∈
Ω such that
(33)
(
μ
′
-
μ
k
+
1
)
T
{
F
(
μ
k
+
1
)
+
η
I
I
(
μ
k
+
1
,
μ
k
)
-
G
(
μ
k
-
μ
k
+
1
)
}
≥
0
,
η
I
I
(
μ
k
+
1
,
μ
k
)
η
I
I
(
μ
k
+
,
μ
k
)
η
I
I
(
μ
k
,
μ
k
)
η
I
I
(
μ
k
+
1
,
μ
k
)
∀
μ
′
∈
Ω
,
with
(34)
η
I
I
(
μ
k
+
1
,
μ
k
)
=
β
(
A
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
B
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
0
)
,
G
I
I
=
(
r
I
n
+
β
∥
A
T
A
∥
s
I
p
+
β
∥
B
T
B
∥
β
-
1
I
m
)
,
where η
I
I
(
μ
k
+
1
,
μ
k
)
∈
ℜ
(
n
+
p
+
m
) and G
I
I
∈
ℜ
(
n
+
p
+
m
)
×
(
n
+
p
+
m
) is a positive definite matrix.Lemma 5.
For a givenμ
k
=
(
x
k
,
y
k
,
λ
k
)
T, let μ
k
+
1
=
(
x
k
+
1
,
y
k
+
1
,
λ
k
+
1
)
T be generated by (33) and (34). If
(35)
u
I
I
=
β
∥
A
T
A
∥
r
+
β
∥
A
T
A
∥
+
β
∥
B
T
B
∥
s
+
β
∥
B
T
B
∥
∈
(
0,1
)
,
then for any μ
*
=
(
x
*
,
y
*
,
λ
*
)
T one has
(36)
(
μ
k
+
1
-
μ
*
)
T
η
I
I
(
μ
k
+
1
,
μ
k
)
≤
u
I
I
2
∥
μ
k
-
μ
k
+
1
∥
G
I
I
2
.Proof.
Analogically, we have(37)
(
μ
k
+
1
-
μ
*
)
T
η
I
I
(
μ
k
+
1
,
μ
k
)
=
(
λ
k
-
λ
k
+
1
)
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
.
Applying the Cauchy-Schwarz inequality to the right term, we get
(38)
(
μ
k
+
1
-
μ
*
)
T
η
I
I
(
μ
k
+
1
,
μ
k
)
≤
|
(
λ
k
-
λ
k
+
1
)
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
|
≤
1
2
{
2
|
(
λ
k
-
λ
k
+
1
)
T
A
(
x
k
-
x
k
+
1
)
|
}
+
1
2
{
2
|
(
λ
k
-
λ
k
+
1
)
T
B
(
y
k
-
y
k
+
1
)
|
}
≤
1
2
{
∥
A
T
A
∥
u
I
I
(
r
+
β
∥
A
T
A
∥
)
|
λ
k
-
λ
k
+
1
|
2
∥
A
T
A
∥
+
u
I
I
(
r
+
β
∥
A
T
A
∥
)
∥
A
T
A
∥
|
A
(
x
k
-
x
k
+
1
)
|
2
}
+
1
2
{
∥
B
T
B
∥
u
I
I
(
s
+
β
∥
B
T
B
∥
)
|
λ
k
-
λ
k
+
1
|
2
∥
A
T
A
∥
gg
+
u
I
I
(
s
+
β
∥
B
T
B
∥
)
∥
B
T
B
∥
|
B
(
y
k
-
y
k
+
1
)
|
2
}
=
1
2
{
(
∥
A
T
A
∥
u
I
I
(
r
+
β
∥
A
T
A
∥
)
+
∥
B
T
B
∥
u
I
I
(
s
+
β
∥
B
T
B
∥
)
)
∥
A
T
a
∥
×
|
λ
k
-
λ
k
+
1
|
2
+
u
I
I
(
r
+
β
∥
A
T
A
∥
)
∥
A
T
A
∥
|
A
(
x
k
-
x
k
+
1
)
|
2
∥
A
T
A
∥
gg
+
u
I
I
(
s
+
β
∥
B
T
B
∥
)
∥
B
T
B
∥
|
B
(
y
k
-
y
k
+
1
)
|
2
}
≤
1
2
{
(
∥
A
T
A
∥
u
I
I
(
r
+
β
∥
A
T
A
∥
)
+
∥
B
T
B
∥
u
I
I
(
s
+
β
∥
B
T
B
∥
)
)
∥
A
T
A
∥
gg
×
|
λ
k
-
λ
k
+
1
|
2
+
u
I
I
(
r
+
β
∥
A
T
A
∥
)
|
x
k
-
x
k
+
1
|
2
∥
A
T
A
∥
gg
+
u
I
I
(
s
+
β
∥
B
T
B
∥
)
|
y
k
-
y
k
+
1
|
2
(
∥
A
T
A
∥
u
I
I
(
r
+
β
∥
A
T
A
∥
)
+
∥
B
T
B
∥
u
I
I
(
s
+
β
∥
B
T
B
∥
)
)
}
=
1
2
{
u
I
I
β
|
λ
k
-
λ
k
+
1
|
2
+
u
I
I
(
r
+
β
∥
A
T
A
∥
)
|
x
k
-
x
k
+
1
|
2
∥
A
T
A
∥
gg
+
u
I
I
(
s
+
β
∥
B
T
B
∥
)
|
y
k
-
y
k
+
1
|
2
u
I
I
β
|
λ
k
-
λ
k
+
1
|
2
}
=
u
I
I
2
∥
μ
k
-
μ
k
+
1
∥
G
I
I
2
.Theorem 6.
Let the sequence{
μ
k
} be generated by SPDM (33) and (34). If
(39)
u
I
I
=
β
∥
A
T
A
∥
r
+
β
∥
A
T
A
∥
+
β
∥
B
T
B
∥
s
+
β
∥
B
T
B
∥
∈
(
0,1
)
,
then one has
(40)
∥
μ
k
+
1
-
μ
*
∥
G
I
I
2
≤
∥
μ
k
-
μ
*
∥
G
I
I
2
-
(
1
-
u
I
I
)
∥
μ
k
-
μ
k
+
1
∥
G
I
I
2
,
≤
∥
μ
k
-
μ
*
∥
G
I
I
2
-
(
1
-
u
I
I
)
Gggggggggggggg
,
GG
∀
μ
*
∈
Ω
*
.Proof.
Consider(41)
∥
μ
k
+
1
-
μ
*
∥
G
I
I
2
=
∥
μ
k
+
1
-
μ
k
+
μ
k
-
μ
*
∥
G
I
I
2
(42)
=
∥
μ
k
-
μ
*
∥
G
I
I
2
-
2
(
μ
k
-
μ
*
)
T
G
I
I
(
μ
k
-
μ
k
+
1
)
+
∥
μ
k
+
1
-
μ
k
∥
G
I
I
2
.
On the other hand, by setting μ
′
=
μ
* in (33), we have
(43)
(
μ
k
+
1
-
μ
*
)
T
G
(
μ
k
-
μ
k
+
1
)
≥
(
μ
k
+
1
-
μ
*
)
T
F
(
μ
k
+
1
)
+
(
μ
k
+
1
-
μ
*
)
η
I
I
(
μ
k
+
1
,
μ
k
)
.
By using the monotonicity of F, we have
(44)
(
μ
k
+
1
-
μ
*
)
T
F
(
μ
k
+
1
)
≥
(
μ
k
+
1
-
μ
*
)
T
F
(
μ
*
)
≥
0
.
With rearrangement of the term (43), we derive that
(45)
(
μ
k
-
μ
*
)
T
G
(
μ
k
-
μ
k
+
1
)
≥
(
μ
k
-
μ
k
+
1
)
T
G
(
μ
k
-
μ
k
+
1
)
+
(
μ
k
+
1
-
μ
*
)
η
I
I
(
μ
k
+
1
,
μ
k
)
.
Substituting (45) into (41), we get
(46)
∥
μ
k
+
1
-
μ
*
∥
G
I
I
2
≤
∥
μ
k
-
μ
*
∥
G
I
I
2
-
2
(
μ
k
+
1
-
μ
*
)
η
I
I
(
μ
k
+
1
,
μ
k
)
-
∥
μ
k
+
1
-
μ
k
∥
G
I
I
2
.
With Lemma 2, substituting (36) into (46), we get
(47)
∥
μ
k
+
1
-
μ
*
∥
G
I
I
2
≤
∥
μ
k
-
μ
*
∥
G
I
I
2
-
(
1
-
u
I
I
)
∥
μ
k
-
μ
k
+
1
∥
G
I
I
2
,
which completes the proof.Remark 7.
Compared to the requirement of the parametersr, s, β in [8], we now allow the step sizes r, s, β to be chosen according to the rule (8). In fact, the restriction on r and s proposed in [8] is
(48)
r
>
β
∥
A
T
A
∥
,
s
>
β
∥
B
T
B
∥
,
which is a special case of the rule (35), since
(49)
β
∥
A
T
A
∥
r
+
β
∥
A
T
A
∥
+
β
∥
B
T
B
∥
s
+
β
∥
A
T
A
∥
<
β
∥
A
T
A
∥
2
β
∥
A
T
A
∥
+
β
∥
B
T
B
∥
2
β
∥
B
T
B
∥
=
1
;
that is, u
I
I
∈
(
0,1
). Hence, the requirement on the parameters is significantly relaxed.


### 3.3. The Convergence

In this subsection, we give the main convergence theorem of the FPDM and SPDM under the new required parameters conditions.Theorem 8.
The sequence{
μ
k
} generated by the FPDM (resp., SPDM) under the conditions (18) (resp., (35)) converges to some solution μ
*, which is a solution of SVIs (9).Proof.
Theorem3 (resp., Theorem 6) means that the sequence {
μ
k
} generated is Fejér monotone with respect to the solution set Ω
* and the assertion follows immediately by using the property of Fejér monotonicity.


## 3.1. The Parameters Relaxation of the FPDM

From (5), the subproblems of FPDM can be, respectively, characterized by the following VI form: find μ
k
+
1
=
(
x
k
+
1
,
y
k
+
1
,
λ
k
+
1
)
T
∈
Ω such that
(16)
(
μ
′
-
μ
k
+
1
)
T
{
F
(
μ
k
+
1
)
+
η
I
(
μ
k
+
1
,
μ
k
)
-
G
(
μ
k
-
μ
k
+
1
)
}
≥
0
,
η
I
(
μ
k
+
1
,
μ
k
)
η
I
(
μ
k
+
1
,
μ
k
)
η
I
(
μ
k
+
1
,
μ
k
)
η
I
(
μ
k
+
1
,
μ
k
)
∀
μ
′
∈
Ω
,
with
(17)
η
I
(
μ
k
+
1
,
μ
k
)
=
β
(
A
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
B
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
0
)
,
G
I
=
(
r
I
n
s
I
p
β
-
1
I
m
)
,
where η
I
(
μ
k
+
1
,
μ
k
)
∈
ℜ
(
n
+
p
+
m
) and G
I
∈
ℜ
(
n
+
p
+
m
)
×
(
n
+
p
+
m
) is a positive definite matrix.Lemma 2.
For a givenμ
k
=
(
x
k
,
y
k
,
λ
k
)
T, let μ
k
+
1
=
(
x
k
+
1
,
y
k
+
1
,
λ
k
+
1
)
T be generated by (16) and (17). If
(18)
u
I
=
β
∥
A
T
A
∥
r
+
β
∥
B
T
B
∥
s
∈
(
0,1
)
,
then for any μ
*
=
(
x
*
,
y
*
,
λ
*
)
T, one has
(19)
(
μ
k
+
1
-
μ
*
)
T
η
I
(
μ
k
+
1
,
μ
k
)
≤
u
I
2
∥
μ
k
-
μ
k
+
1
∥
G
I
2
.Proof.
SinceA
x
*
+
B
y
*
=
b and β
(
A
x
k
+
1
+
B
y
k
+
1
-
b
)
=
λ
k
-
λ
k
+
1 one has
(20)
(
μ
k
+
1
-
μ
*
)
T
η
I
(
μ
k
+
1
,
μ
k
)
μ
k
+
1
=
β
(
x
k
+
1
-
x
*
y
k
+
1
-
y
*
λ
k
+
1
-
λ
*
)
T
μ
k
+
1
μ
k
+
1
×
(
A
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
B
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
0
)
μ
k
+
1
=
(
λ
k
-
λ
k
+
1
)
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
.
Applying the Cauchy-Schwarz inequality to the right term, we get
(21)
(
μ
k
+
1
-
μ
*
)
T
η
I
(
μ
k
+
1
,
μ
k
)
≤
|
(
λ
k
-
λ
k
+
1
)
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
|
≤
1
2
{
1
2
2
|
(
λ
k
-
λ
k
+
1
)
T
A
(
x
k
-
x
k
+
1
)
|
}
+
1
2
{
2
|
(
λ
k
-
λ
k
+
1
)
T
B
(
y
k
-
y
k
+
1
)
|
}
≤
1
2
{
∥
A
T
A
∥
u
I
r
|
λ
k
-
λ
k
+
1
|
2
+
u
I
r
∥
A
T
A
∥
|
A
(
x
k
-
x
k
+
1
)
|
2
}
+
1
2
{
∥
B
T
B
∥
u
I
s
|
λ
k
-
λ
k
+
1
|
2
+
u
I
s
∥
B
T
B
∥
|
B
(
y
k
-
y
k
+
1
)
|
2
}
=
1
2
{
(
∥
A
T
A
∥
u
I
r
+
∥
B
T
B
∥
u
I
s
)
|
λ
k
-
λ
k
+
1
|
2
∥
A
T
∥
+
u
I
r
∥
A
T
A
∥
|
A
(
x
k
-
x
k
+
1
)
|
2
+
u
I
s
∥
B
T
B
∥
|
B
(
y
k
-
y
k
+
1
)
|
2
}
≤
1
2
{
(
∥
A
T
A
∥
u
I
r
+
∥
B
T
B
∥
u
I
s
)
|
λ
k
-
λ
k
+
1
|
2
+
u
I
r
|
x
k
-
x
k
+
1
|
2
∥
A
T
A
∥
+
u
I
s
|
y
k
-
y
k
+
1
|
2
(
∥
A
T
A
∥
u
I
r
+
∥
B
T
B
∥
u
I
s
)
}
=
1
2
{
u
I
β
|
λ
k
-
λ
k
+
1
|
2
+
u
I
r
|
x
k
-
x
k
+
1
|
2
+
u
I
s
|
y
k
-
y
k
+
1
|
2
}
=
u
I
2
∥
μ
k
-
μ
k
+
1
∥
G
I
2
.Theorem 3.
Let the sequence{
μ
k
} be generated by FPDM (16) and (17). If
(22)
u
I
=
β
∥
A
T
A
∥
r
+
β
∥
B
T
B
∥
s
∈
(
0,1
)
,
then one has
(23)
∥
μ
k
+
1
-
μ
*
∥
G
I
2
≤
∥
μ
k
-
μ
*
∥
G
I
2
-
(
1
-
u
I
)
∥
μ
k
-
μ
k
+
1
∥
G
I
2
,
∀
μ
*
∈
Ω
*
.Proof.
Consider(24)
∥
μ
k
+
1
-
μ
*
∥
G
I
2
=
∥
μ
k
+
1
-
μ
k
+
μ
k
-
μ
*
∥
G
I
2
(25)
=

∥
μ
k
-
μ
*
∥
G
I
2

-
2
(
μ
k
-
μ
*
)
T
G
I
(
μ
k
-
μ
k
+
1
)
+
∥
μ
k
+
1
-
μ
k
∥
G
I
2
.
On the other hand, by setting μ
′
=
μ
* in (16), we have
(26)
(
μ
k
+
1
-
μ
*
)
T
G
(
μ
k
-
μ
k
+
1
)
≥
(
μ
k
+
1
-
μ
*
)
T
F
(
μ
k
+
1
)
+
(
μ
k
+
1
-
μ
*
)
η
I
(
μ
k
+
1
,
μ
k
)
.
Using the fact that F is a monotone operator, we have
(27)
(
μ
k
+
1
-
μ
*
)
T
F
(
μ
k
+
1
)
≥
(
μ
k
+
1
-
μ
*
)
T
F
(
μ
*
)
≥
0
.
With rearrangement of the term (26) and using (27), we derive that
(28)
(
μ
k
-
μ
*
)
T
G
(
μ
k
-
μ
k
+
1
)
≥
(
μ
k
-
μ
k
+
1
)
T
G
(
μ
k
-
μ
k
+
1
)
+
(
μ
k
+
1
-
μ
*
)
η
I
(
μ
k
+
1
,
μ
k
)
.
Substituting (28) into (24), we get
(29)
∥
μ
k
+
1
-
μ
*
∥
G
I
2
≤
∥
μ
k
-
μ
*
∥
G
I
2
-
2
(
μ
k
+
1
-
μ
*
)
η
I
(
μ
k
+
1
,
μ
k
)
-
∥
μ
k
+
1
-
μ
k
∥
G
I
2
.
With Lemma 1, substituting (19) into (29), we get
(30)
∥
μ
k
+
1
-
μ
*
∥
G
I
2
≤
∥
μ
k
-
μ
*
∥
G
I
2
-
(
1
-
u
I
)
∥
μ
k
-
μ
k
+
1
∥
G
I
2
,
which completes the proof.Remark 4.
Compared to the requirement of the parametersr, s, β in [8], we now allow the step sizes r, s, β to be chosen according to rule (7). In fact, the restriction on r and s proposed in [8] is
(31)
r
>
2
β
∥
A
T
A
∥
,
s
>
2
β
∥
B
T
B
∥
,
which is a special case of the rule (18), since
(32)
β
∥
A
T
A
∥
r
+
β
∥
B
T
B
∥
s
<
β
∥
A
T
A
∥
2
β
∥
A
T
A
∥
+
β
∥
B
T
B
∥
2
β
∥
B
T
B
∥
=
1
;
that is, u
I
∈
(
0,1
). Hence, the requirement on the parameters is significantly relaxed.


## 3.2. The Parameters Relaxation of the SPDM

In this subsection, we extend our analysis to the SPDM. From (5), the subproblems of SPDM can be characterized by the following VI form: find μ
k
+
1
=
(
x
k
+
1
,
y
k
+
1
,
λ
k
+
1
)
T
∈
Ω such that
(33)
(
μ
′
-
μ
k
+
1
)
T
{
F
(
μ
k
+
1
)
+
η
I
I
(
μ
k
+
1
,
μ
k
)
-
G
(
μ
k
-
μ
k
+
1
)
}
≥
0
,
η
I
I
(
μ
k
+
1
,
μ
k
)
η
I
I
(
μ
k
+
,
μ
k
)
η
I
I
(
μ
k
,
μ
k
)
η
I
I
(
μ
k
+
1
,
μ
k
)
∀
μ
′
∈
Ω
,
with
(34)
η
I
I
(
μ
k
+
1
,
μ
k
)
=
β
(
A
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
B
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
0
)
,
G
I
I
=
(
r
I
n
+
β
∥
A
T
A
∥
s
I
p
+
β
∥
B
T
B
∥
β
-
1
I
m
)
,
where η
I
I
(
μ
k
+
1
,
μ
k
)
∈
ℜ
(
n
+
p
+
m
) and G
I
I
∈
ℜ
(
n
+
p
+
m
)
×
(
n
+
p
+
m
) is a positive definite matrix.Lemma 5.
For a givenμ
k
=
(
x
k
,
y
k
,
λ
k
)
T, let μ
k
+
1
=
(
x
k
+
1
,
y
k
+
1
,
λ
k
+
1
)
T be generated by (33) and (34). If
(35)
u
I
I
=
β
∥
A
T
A
∥
r
+
β
∥
A
T
A
∥
+
β
∥
B
T
B
∥
s
+
β
∥
B
T
B
∥
∈
(
0,1
)
,
then for any μ
*
=
(
x
*
,
y
*
,
λ
*
)
T one has
(36)
(
μ
k
+
1
-
μ
*
)
T
η
I
I
(
μ
k
+
1
,
μ
k
)
≤
u
I
I
2
∥
μ
k
-
μ
k
+
1
∥
G
I
I
2
.Proof.
Analogically, we have(37)
(
μ
k
+
1
-
μ
*
)
T
η
I
I
(
μ
k
+
1
,
μ
k
)
=
(
λ
k
-
λ
k
+
1
)
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
.
Applying the Cauchy-Schwarz inequality to the right term, we get
(38)
(
μ
k
+
1
-
μ
*
)
T
η
I
I
(
μ
k
+
1
,
μ
k
)
≤
|
(
λ
k
-
λ
k
+
1
)
T
(
A
(
x
k
-
x
k
+
1
)
+
B
(
y
k
-
y
k
+
1
)
)
|
≤
1
2
{
2
|
(
λ
k
-
λ
k
+
1
)
T
A
(
x
k
-
x
k
+
1
)
|
}
+
1
2
{
2
|
(
λ
k
-
λ
k
+
1
)
T
B
(
y
k
-
y
k
+
1
)
|
}
≤
1
2
{
∥
A
T
A
∥
u
I
I
(
r
+
β
∥
A
T
A
∥
)
|
λ
k
-
λ
k
+
1
|
2
∥
A
T
A
∥
+
u
I
I
(
r
+
β
∥
A
T
A
∥
)
∥
A
T
A
∥
|
A
(
x
k
-
x
k
+
1
)
|
2
}
+
1
2
{
∥
B
T
B
∥
u
I
I
(
s
+
β
∥
B
T
B
∥
)
|
λ
k
-
λ
k
+
1
|
2
∥
A
T
A
∥
gg
+
u
I
I
(
s
+
β
∥
B
T
B
∥
)
∥
B
T
B
∥
|
B
(
y
k
-
y
k
+
1
)
|
2
}
=
1
2
{
(
∥
A
T
A
∥
u
I
I
(
r
+
β
∥
A
T
A
∥
)
+
∥
B
T
B
∥
u
I
I
(
s
+
β
∥
B
T
B
∥
)
)
∥
A
T
a
∥
×
|
λ
k
-
λ
k
+
1
|
2
+
u
I
I
(
r
+
β
∥
A
T
A
∥
)
∥
A
T
A
∥
|
A
(
x
k
-
x
k
+
1
)
|
2
∥
A
T
A
∥
gg
+
u
I
I
(
s
+
β
∥
B
T
B
∥
)
∥
B
T
B
∥
|
B
(
y
k
-
y
k
+
1
)
|
2
}
≤
1
2
{
(
∥
A
T
A
∥
u
I
I
(
r
+
β
∥
A
T
A
∥
)
+
∥
B
T
B
∥
u
I
I
(
s
+
β
∥
B
T
B
∥
)
)
∥
A
T
A
∥
gg
×
|
λ
k
-
λ
k
+
1
|
2
+
u
I
I
(
r
+
β
∥
A
T
A
∥
)
|
x
k
-
x
k
+
1
|
2
∥
A
T
A
∥
gg
+
u
I
I
(
s
+
β
∥
B
T
B
∥
)
|
y
k
-
y
k
+
1
|
2
(
∥
A
T
A
∥
u
I
I
(
r
+
β
∥
A
T
A
∥
)
+
∥
B
T
B
∥
u
I
I
(
s
+
β
∥
B
T
B
∥
)
)
}
=
1
2
{
u
I
I
β
|
λ
k
-
λ
k
+
1
|
2
+
u
I
I
(
r
+
β
∥
A
T
A
∥
)
|
x
k
-
x
k
+
1
|
2
∥
A
T
A
∥
gg
+
u
I
I
(
s
+
β
∥
B
T
B
∥
)
|
y
k
-
y
k
+
1
|
2
u
I
I
β
|
λ
k
-
λ
k
+
1
|
2
}
=
u
I
I
2
∥
μ
k
-
μ
k
+
1
∥
G
I
I
2
.Theorem 6.
Let the sequence{
μ
k
} be generated by SPDM (33) and (34). If
(39)
u
I
I
=
β
∥
A
T
A
∥
r
+
β
∥
A
T
A
∥
+
β
∥
B
T
B
∥
s
+
β
∥
B
T
B
∥
∈
(
0,1
)
,
then one has
(40)
∥
μ
k
+
1
-
μ
*
∥
G
I
I
2
≤
∥
μ
k
-
μ
*
∥
G
I
I
2
-
(
1
-
u
I
I
)
∥
μ
k
-
μ
k
+
1
∥
G
I
I
2
,
≤
∥
μ
k
-
μ
*
∥
G
I
I
2
-
(
1
-
u
I
I
)
Gggggggggggggg
,
GG
∀
μ
*
∈
Ω
*
.Proof.
Consider(41)
∥
μ
k
+
1
-
μ
*
∥
G
I
I
2
=
∥
μ
k
+
1
-
μ
k
+
μ
k
-
μ
*
∥
G
I
I
2
(42)
=
∥
μ
k
-
μ
*
∥
G
I
I
2
-
2
(
μ
k
-
μ
*
)
T
G
I
I
(
μ
k
-
μ
k
+
1
)
+
∥
μ
k
+
1
-
μ
k
∥
G
I
I
2
.
On the other hand, by setting μ
′
=
μ
* in (33), we have
(43)
(
μ
k
+
1
-
μ
*
)
T
G
(
μ
k
-
μ
k
+
1
)
≥
(
μ
k
+
1
-
μ
*
)
T
F
(
μ
k
+
1
)
+
(
μ
k
+
1
-
μ
*
)
η
I
I
(
μ
k
+
1
,
μ
k
)
.
By using the monotonicity of F, we have
(44)
(
μ
k
+
1
-
μ
*
)
T
F
(
μ
k
+
1
)
≥
(
μ
k
+
1
-
μ
*
)
T
F
(
μ
*
)
≥
0
.
With rearrangement of the term (43), we derive that
(45)
(
μ
k
-
μ
*
)
T
G
(
μ
k
-
μ
k
+
1
)
≥
(
μ
k
-
μ
k
+
1
)
T
G
(
μ
k
-
μ
k
+
1
)
+
(
μ
k
+
1
-
μ
*
)
η
I
I
(
μ
k
+
1
,
μ
k
)
.
Substituting (45) into (41), we get
(46)
∥
μ
k
+
1
-
μ
*
∥
G
I
I
2
≤
∥
μ
k
-
μ
*
∥
G
I
I
2
-
2
(
μ
k
+
1
-
μ
*
)
η
I
I
(
μ
k
+
1
,
μ
k
)
-
∥
μ
k
+
1
-
μ
k
∥
G
I
I
2
.
With Lemma 2, substituting (36) into (46), we get
(47)
∥
μ
k
+
1
-
μ
*
∥
G
I
I
2
≤
∥
μ
k
-
μ
*
∥
G
I
I
2
-
(
1
-
u
I
I
)
∥
μ
k
-
μ
k
+
1
∥
G
I
I
2
,
which completes the proof.Remark 7.
Compared to the requirement of the parametersr, s, β in [8], we now allow the step sizes r, s, β to be chosen according to the rule (8). In fact, the restriction on r and s proposed in [8] is
(48)
r
>
β
∥
A
T
A
∥
,
s
>
β
∥
B
T
B
∥
,
which is a special case of the rule (35), since
(49)
β
∥
A
T
A
∥
r
+
β
∥
A
T
A
∥
+
β
∥
B
T
B
∥
s
+
β
∥
A
T
A
∥
<
β
∥
A
T
A
∥
2
β
∥
A
T
A
∥
+
β
∥
B
T
B
∥
2
β
∥
B
T
B
∥
=
1
;
that is, u
I
I
∈
(
0,1
). Hence, the requirement on the parameters is significantly relaxed.


## 3.3. The Convergence

In this subsection, we give the main convergence theorem of the FPDM and SPDM under the new required parameters conditions.Theorem 8.
The sequence{
μ
k
} generated by the FPDM (resp., SPDM) under the conditions (18) (resp., (35)) converges to some solution μ
*, which is a solution of SVIs (9).Proof.
Theorem3 (resp., Theorem 6) means that the sequence {
μ
k
} generated is Fejér monotone with respect to the solution set Ω
* and the assertion follows immediately by using the property of Fejér monotonicity.


## 4. Numerical Experiments

In this section, we report the sensitivity of the involved parametersr, s, β of FPDM on the stable principal component pursuit problem (SPCP). Since SPDM is the extended version of FPDM and the sensitivity results of SPDM are similar to those of FPDM, we omit the numerical results of SPDM for the sake of succinctness. The problem tested is from Example 2 of [26]. Codes were all written in Matlab 2009b and all programs were run on HP notebook with Intel Core CPU 2.0 GHZ and 2 G memory.SPCP arising from compressed sensing seeks to decompose a given observation matrixM into the sum of three matrices: M
∶
=
L
+
S
+
Z, where L is a nonnegative and low-rank matrix, S is a sparse matrix, and Z is a noise matrix. The model of SPCP can be cast as
(50)
min
⁡
L
,
S
,
Z
∥
L
∥
*
+
ρ
∥
S
∥
1
+
ℐ
(
∥
Z
∥
F
≤
σ
)
+
ℐ
(
L
≥
0
)
s
.
t
.
L
+
S
+
Z
=
M
,
where ∥
·
∥
* is the so-called nuclear norm (the sum of all singular values), ∥
·
∥
1 is the l
1 norm, and ℐ
(
·
) is an indicator function.Following the procedure described in [26], by introducing an auxiliary variable K, grouping L and S as one big block [
L
;
S
], and grouping Z and K as another big block [
Z
;
K
], (50) can be reformulated as the standard form of (1) as follows:
(51)
min
⁡
L
,
S
,
Z
,
K
⁡
∥
L
∥
*
+
ρ
∥
S
∥
1
+
ℐ
(
∥
Z
∥
F
≤
σ
)
+
ℐ
(
K
≥
0
)
l
,
s
.
t
.
(
I
I
I
0
)
(
L
S
)
+
(
I
0
0
-
I
)
(
Z
K
)
=
(
M
0
)
.
Then the largest singular value of the coefficient matrix of [
L
;
S
] is 2.618. The largest singular value of the coefficient matrix of [
Z
;
K
] is 1. For a better illustration, we denote τ
1
=
2.618
,
τ
2
=
1.FPDM (5) applied to (51) yields the following iterative scheme:(52a)
L
k
+
1
=
arg
min
⁡
∥
L
∥
*
+
r
2
∥
1
r
L
-
L
k
-
1
r
(
Λ
1
k
+
Λ
2
k
-
β
(
2
L
k
+
S
k
+
Z
k
-
K
k
-
M
)
)
∥
F
2
,
(52b)
S
k
+
1
=
arg
min
⁡
ρ
∥
S
∥
1
+
r
2
∥
S
-
S
k
-
1
r
(
Λ
1
k
-
β
(
L
k
+
S
k
+
Z
k
-
M
)
)
∥
F
2
,
(52c)
Z
k
+
1
=
arg
min
⁡
ℐ
(
∥
Z
∥
F
≤
σ
)
+
s
2
∥
Z
-
Z
k
-
1
s
(
Λ
1
k
-
β
(
L
k
+
S
k
+
Z
k
-
M
)
)
∥
F
2
,
(52d)
K
k
+
1
=
arg
min
⁡
ℐ
(
K
≥
0
)
+
s
2
∥
K
-
K
k
+
1
s
(
Λ
2
k
-
β
(
K
k
-
L
k
)
)
∥
F
2
,
(52e)
Λ
1
k
+
1
=
Λ
1
k
-
β
(
L
k
+
1
+
S
k
+
1
+
Z
k
+
1
-
M
)
,
(52f)
Λ
2
k
+
1
=
Λ
2
k
-
β
(
L
k
+
1
-
K
k
+
1
)
.There are two main advantages of FPDM applied to SPCP. First, all the generated minimizations in (52a)–(52d) have closed-form solutions. Second, the subproblems (52a)–(52d) are highly parallel, making FPDM appealing for parallel or distributed computing. Now, we elaborate on the strategy of solving the resulting subproblems at each iteration.(i) TheL-subproblem (52a) amounts to evaluate the proximal operator of the nuclear norm function and is given by the matrix shrinkage operation
(53)
L
k
+
1
∶
=
MatShrink
(
L
k
+
1
r
(
Λ
1
k
+
Λ
2
k
Λ
1
k
+
Λ
2
k
Λ
1
k
+
Λ
2
k
-
β
(
2
L
k
+
S
k
+
Z
k
-
K
k
-
M
)
)
,
1
r
)
,
where the matrix shrinkage operator MatShrink
(
M
,
ξ
)
(
ξ
>
0
) is defined as
(54)
MatShrink
(
M
,
ξ
)
∶
=
U
Diag
(
max
⁡
{
σ
-
ξ
,
0
}
)
V
T
,
and U
Diag
(
σ
)
V
T is the SVD of matrix M.(ii) The closed-form solution ofS-subproblem (52b) can be given by the l
1 shrinkage operation:
(55)
S
k
+
1
∶
=
Shrink
(
S
k
+
1
r
(
Λ
1
k
-
β
(
L
k
+
S
k
+
Z
k
-
M
)
)
,
ρ
r
)
,
where the l
1 shrinkage operator Shrink
(
M
,
ξ
) is defined as
(56)
[
Shrink
(
M
,
ξ
)
]
i
j
∶
=
{
M
i
j
-
ξ
,
if
M
i
j
>
ξ
M
i
j
+
ξ
,
if
M
i
j
<
-
ξ
0
,
if
|
M
i
j
|
≤
ξ
.(iii) TheZ-subproblem (52c) amounts to projecting the matrix W
k
∶
=
M
+
(
1
/
β
)
Λ
1
k
-
(
L
k
+
S
k
) onto the Euclidean ball ∥
Z
∥
F
≤
σ, whose closed-form solution is given by
(57)
Z
k
+
1
∶
=
W
k
max
⁡
{
1
,
∥
W
k
∥
F
/
σ
}
.(iv) TheK-subproblem (52d) amounts to projecting the matrix L
k
-
(
1
/
β
)
Λ
2
k onto the the nonnegative orthant, whose closed-form solution is given by
(58)
K
k
+
1
∶
=
max
⁡
{
L
k
-
1
β
Λ
2
k
,
0
}
.
For detailed analytical methods of (52a)–(52d), the reader is referred to, for example, [26, 27].In our experiment, we generate the data of (50) randomly in the same way as [26]. For given n, r
<
n, the n
×
n rank-r matrix L
* was generated by L
*
=
R
1
R
2
T, where R
1 and R
2 are n
×
r random matrices whose entries are independently and identically (i.i.d.) uniformly distributed in [
0,1
]. Note that, in this experiment, L
* is a componentwise nonnegative and low-rank matrix we want to recover. The support of the sparse matrix S
* was chosen uniformly and randomly, and the nonzero entries of S
* were i.i.d. uniformly in the interval [
-
500,500
]. The entries of matrix Z
* for noise were generated as i.i.d. Gaussian with standard deviation 1
0
-
4.As in [26], we set M
∶
=
L
*
+
S
*
+
Z
*; we chose ρ
∶
=
1
/
n. The initial iterate for FPDM is L
0
=
K
0
=
-
M, S
0
=
Z
0
=
0, Λ
1
0
=
Λ
2
0
=
0. The stopping criterion is set as
(59)
resid
∶
=
∥
L
+
S
+
Z
-
M
∥
F
∥
M
∥
F
<
ϵ
r
,
where ϵ
r is the tolerance set as ϵ
r
=
1
0
-
4. We denoted Ran
k
r
∶
=
r
/
n so that the rank of L
* is n
*
Ran
k
r and Car
d
r
∶
=
cardinality
(
S
*
)
/
(
n
2
) so that the cardinality of S
* is n
2
*
Car
d
r. For some cases of dimension m, we report the iteration numbers (Iter.), relative error of the low-rank matrix L
(
re
l
L
), relative error of the sparse matrix S
(
re
l
S
), and CPU times in seconds (CPU(s)), where the relative errors are defined as
(60)
re
l
L
∶
=
∥
L
-
L
*
∥
F
∥
L
*
∥
F
,
re
l
S
∶
=
∥
S
-
S
*
∥
F
∥
S
*
∥
F
.
For each instance, we randomly created ten examples, so the results were averaged over ten runs.The computational results are presented in Table1. For a different instance, the value of β, r, and s chosen to satisfy the condition (7), respectively. It can be seen that if we choose r a little smaller than 2
β
∥
A
T
A
∥ and s a little larger than 2
β
∥
B
T
B
∥, the numerical performance of FPDM with the new selected parameters shows better than the case, where r
=
2
β
∥
A
T
A
∥
,
s
=
2
β
∥
B
T
B
∥.Table 1
Numerical results for stable principal component pursuit problem.
n
r
s
Iter.
re
l
L
re
l
S
CPU (s)
r
s
Iter.
re
l
L
re
l
S
CPU (s)
β
=
0.01, Ran
k
r
=
0.01, Car
d
r
=
0.01
50
2β
τ
1
2β
τ
2
97
9.01
e
-
003
2.89
e
-
005
0.3
1.9
β
τ
1
1.9
β
τ
2
/
0.9
101
9.18
e
-
003
2.87
e
-
005
0.3
100
2β
τ
1
2β
τ
2
78
5.71
e
-
003
6.16
e
-
005
1.1
1.9
β
τ
1
1.9
β
τ
2
/
0.9
76
6.57
e
-
003
5.11
e
-
005
1.0
150
2β
τ
1
2β
τ
2
81
3.52
e
-
003
4.65
e
-
005
3.2
1.9
β
τ
1
1.9
β
τ
2
/
0.9
77
3.75
e
-
003
5.19
e
-
005
2.9
200
2β
τ
1
2β
τ
2
81
3.60
e
-
003
5.53
e
-
005
6.6
1.9
β
τ
1
1.9
β
τ
2
/
0.9
76
3.61
e
-
003
6.56
e
-
005
5.9
300
2β
τ
1
2β
τ
2
83
2.33
e
-
003
5.97
e
-
005
20.4
1.9
β
τ
1
1.9
β
τ
2
/
0.9
82
2.57
e
-
003
5.31
e
-
005
19.4
β
=
0.02, Ran
k
r
=
0.01, Car
d
r
=
0.01
50
2β
τ
1
2β
τ
2
181
8.42
e
-
003
2.37
e
-
005
0.5
1.9
β
τ
1
1.9
β
τ
2
/
0.9
180
8.39
e
-
003
2.36
e
-
005
0.5
100
2β
τ
1
2β
τ
2
105
8.47
e
-
003
2.03
e
-
005
1.4
1.9
β
τ
1
1.9
β
τ
2
/
0.9
106
8.21
e
-
003
2.34
e
-
005
1.4
150
2β
τ
1
2β
τ
2
127
5.06
e
-
003
2.09
e
-
005
4.7
1.9
β
τ
1
1.9
β
τ
2
/
0.9
126
5.05
e
-
003
2.14
e
-
005
4.5
200
2β
τ
1
2β
τ
2
93
4.73
e
-
003
1.87
e
-
005
7.2
1.9
β
τ
1
1.9
β
τ
2
/
0.9
91
4.79
e
-
003
2.67
e
-
005
7.0
300
2β
τ
1
2β
τ
2
84
3.10
e
-
003
3.37
e
-
005
20.3
1.9
β
τ
1
1.9
β
τ
2
/
0.9
85
3.13
e
-
003
2.63
e
-
005
20.2
β
=
0.01, Ran
k
r
=
0.02, Car
d
r
=
0.02
50
2β
τ
1
2β
τ
2
84
1.14
e
-
002
5.10
e
-
005
0.2
1.9
β
τ
1
1.9
β
τ
2
/
0.9
85
1.24
e
-
002
3.92
e
-
005
0.2
100
2β
τ
1
2β
τ
2
79
5.76
e
-
003
5.40
e
-
005
1.2
1.9
β
τ
1
1.9
β
τ
2
/
0.9
76
5.71
e
-
003
5.02
e
-
005
1.1
150
2β
τ
1
2β
τ
2
82
3.55
e
-
003
5.99
e
-
005
3.6
1.9
β
τ
1
1.9
β
τ
2
/
0.9
81
3.80
e
-
003
4.90
e
-
005
3.4
200
2β
τ
1
2β
τ
2
84
2.90
e
-
003
6.70
e
-
005
7.3
1.9
β
τ
1
1.9
β
τ
2
/
0.9
83
2.92
e
-
003
5.81
e
-
005
7.1
300
2β
τ
1
2β
τ
2
91
2.18
e
-
003
5.42
e
-
005
22.8
1.9
β
τ
1
1.9
β
τ
2
/
0.9
90
2.33
e
-
003
4.85
e
-
005
22.5
β
=
0.01, Ran
k
r
=
0.03, Car
d
r
=
0.03
50
2β
τ
1
2β
τ
2
99
9.31
e
-
003
3.09
e
-
005
0.3
1.9
β
τ
1
1.9
β
τ
2
/
0.9
101
9.33
e
-
003
2.99
e
-
005
0.3
100
2β
τ
1
2β
τ
2
83
4.89
e
-
003
5.03
e
-
005
1.4
1.9
β
τ
1
1.9
β
τ
2
/
0.9
81
5.28
e
-
003
4.53
e
-
005
1.3
150
2β
τ
1
2β
τ
2
86
3.19
e
-
003
5.84
e
-
005
3.8
1.9
β
τ
1
1.9
β
τ
2
/
0.9
84
3.22
e
-
003
5.68
e
-
005
3.7
200
2β
τ
1
2β
τ
2
91
2.82
e
-
003
5.67
e
-
005
8.5
1.9
β
τ
1
1.9
β
τ
2
/
0.9
90
2.78
e
-
003
4.92
e
-
005
8.4
300
2β
τ
1
2β
τ
2
115
3.47
e
-
003
1.88
e
-
005
30.8
1.9
β
τ
1
1.9
β
τ
2
/
0.9
116
3.52
e
-
003
1.85
e
-
005
29.0


## 5. Conclusions

In this paper, we show that the requirement ranges on the involved parameters of the proximal-based parallel decomposition methods can be significantly enlarged. We prove the global convergence of the new scheme under the new conditions. Preliminary numerical experiments on the stable principal component pursuit problem testify to the advantages of the enlargement.


## Conflict of Interests

We declare that there is no conflict of interests regarding the publication of this article.



---

*Source: 891017-2014-01-20.xml*