# A Line-Search-Based Partial Proximal Alternating Directions Method for Separable Convex Optimization

Authors: Yu-hua Zeng; Yu-fei Yang; Zheng Peng
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

We propose an appealing line-search-based partial proximal alternating directions (LSPPAD) method for solving a class of separable convex optimization problems. These problems under consideration are common in practice. The proposed method solves two subproblems at each iteration: one is solved by a proximal point method, while the proximal term is absent from the other. Both subproblems admit inexact solutions. A line search technique is used to guarantee the convergence. The convergence of the LSPPAD method is established under some suitable conditions. The advantage of the proposed method is that it provides the tractability of the subproblem in which the proximal term is absent. Numerical tests show that the LSPPAD method has better performance compared with the existing alternating projection based prediction-correction (APBPC) method if both are employed to solve the described problem.


---

## Body

## 1. Introduction

In this paper, we consider a separable convex optimization problem of the form(1)
min
⁡
θ
1
(
x
)
+
θ
2
(
y
)
,
s
.
t
.
A
x
-
y
=
0
,
where x
∈
𝒳, y
∈
𝒴, θ
1
:
𝒳
→
R, and θ
2
:
𝒴
→
R are convex functions; 𝒳
⊂
R
n, 𝒴
⊂
R
m are closed convex sets; A
∈
R
m
×
n is a given matrix; and rank
⁡
(
A
)
=
min
⁡
{
m
,
n
}.The augmented Lagrangian function associated with the problem (1) is
(2)
L
β
(
x
,
y
,
λ
)
=
θ
1
(
x
)
+
θ
2
(
y
)
-
λ
T
(
A
x
-
y
)
+
β
2
∥
A
x
-
y
∥
2
.For simplicity of analysis, we assume the objective function is continuously differentiable. Letf
(
x
)
=
∇
θ
1
(
x
) and g
(
y
)
=
∇
θ
2
(
y
); by the convexity of the functions θ
1 and θ
2, f and g are monotone in 𝒳 and 𝒴, respectively. Thus, by the optimality, the problem (1) is equivalent to the following monotone variational inequalities: find (
x
,
y
,
λ
)
∈
𝒲 such that
(3)
(
x
′
-
x
)
T
[
f
(
x
)
-
A
T
(
λ
-
β
(
A
x
-
y
)
)
]
≥
0
,
∀
x
′
∈
𝒳
,
(
y
′
-
y
)
T
[
g
(
y
)
+
(
λ
-
β
(
A
x
-
y
)
)
]
≥
0
,
∀
y
′
∈
𝒴
,
(
λ
′
-
λ
)
T
(
A
x
-
y
)
≥
0
,
∀
λ
′
∈
R
m
,
where 𝒲
=
𝒳
×
𝒴
×
R
m.Chen and Teboulle [1] investigated the problem (1) and proposed a proximal-based decomposition method. Tseng [2] interpreted Chen and Teboulle's approach as an alternating version of the proximal point method and the extragradient method. Furthermore, Tseng generalized their method to solve much broader classes of problems and to yield new decomposition methods for convex programming and variational inequalities.Indeed, there are many methods to deal with the problem (1), or its equivalent version (3), in the literature. Among these methods, proximal point method and alternating directions method are power tools, for example, [3–8].Throughout this paper, we assume that the solution set of the problem (1) or, equivalently, the solution set of SVIs (3), denoted by 𝒲
*, is nonempty. The notation ∥
·
∥ denotes the Euclidean norm, ∥
·
∥
∞ denotes the infinite norm defined by ∥
u
∥
∞
=
max
⁡
i
{
|
u
i
|
}, and ∥
·
∥
∞ denotes the l
1-norm defined by ∥
u
∥
1
=
∑
i
=
1
n
‍
|
u
i
|.From a givenw
k
=
(
x
k
,
y
k
,
λ
k
), the classical proximal alternating directions method produces the new iterate triple w
k
+
1
=
(
x
k
+
1
,
y
k
+
1
,
λ
k
+
1
) via the following scheme.(
1
) Find x
^
k via solving
(4)
x
∈
𝒳
,
(
x
′
-
x
)
T
{
f
(
x
k
)
-
A
T
[
λ
k
-
β
k
(
A
x
k
-
y
k
)
]
+
r
k
(
x
-
x
k
)
}
≥
0
,
∀
x
'
∈
𝒳
.(
2
) Find y
^
k via solving
(5)
y
∈
𝒴
,
(
y
′
-
y
)
T
×
{
g
(
y
k
)
+
[
λ
k
-
β
k
(
A
x
^
k
-
y
k
)
]
+
s
k
(
y
-
y
k
)
}
≥
0
,
∀
y
′
∈
𝒴
.(
3
) Update λ
^
k via
(6)
λ
^
k
=
λ
k
-
β
k
(
A
x
^
k
-
y
^
k
)
,
where β
k is a given penalty parameter of the linear constraint A
x
-
y
=
0. The coefficients r
k
>
0 in formulas (4) and s
k
>
0 in (5) are referred to as proximal parameters. The method is convergent by setting w
k
+
1
=
w
^
k
=
(
x
^
k
,
y
^
k
,
λ
^
k
) (for a proof see [3]).However, finding a solution of the subproblem (4) or (5) is not an easy task, since each of them requires an implicit projection. He et al. [4] suggested solving inexactly the subproblems (4) and (5). Their method is referred to as alternating projection based prediction-correction (APBPC) method. In [4], the authors considered a generalized version of the problem (1) with the constraints A
x
+
B
y
=
b. The problem under consideration in this paper, that is, problem (1), has some features depending on B
=
-
I. These features provide some advantages for constructing more efficient method.This paper is organized as follows. Section2 proposes a line-search-based partial proximal alternating directions method for solving the problem (1) and states some useful notation. The proposed method can be looked as to a proximal alternating directions method by setting s
k
=
0 in (5) and admits inexact solution at all iterations. Thus, the proposed method is actually an inexact partial proximal alternating direction method using a certain line-search technique. In Section 3, we provide two descent directions of a given merit function and prove the descent property of the proposed method. In Section 4, the convergence property of the proposed method is established under some suitable conditions. Section 5 gives some preliminary numerical experimental results on the compressed sensor problem. These results show that the proposed method has better performance compared with the existing APBPC method, when both are used to solve the problem with the described features. Finally, some concluding remarks are given in Section 6.


## 2. Method Description

In this section, we first describe the line-search-based partial proximal alternating directions method for the problem (3) in what follows.Line-Search-Based Partial Proximal Alternating Directions (LSPPAD) Method. Let ν
∈
(
0,1
). For a given w
k
=
(
x
k
,
y
k
,
λ
k
)
∈
𝒲, the LSPPAD method produces the new triple w
k
+
1
=
(
x
k
+
1
,
y
k
+
1
,
λ
k
+
1
) via the following scheme.(s1)
Solving the following variational inequality, findx
∈
𝒳 such that
(7)
(
x
′
-
x
)
T
{
f
(
x
k
)
-
A
T
[
λ
k
-
β
k
(
A
x
k
-
y
k
)
]
+
r
k
(
x
-
x
k
)
}
≥
0
,
∀
x
′
∈
𝒳
.
And denote the solution byx
^
k. Let ξ
x
k
=
f
(
x
k
)
-
f
(
x
^
k
)
+
β
k
A
T
A
(
x
k
-
x
^
k
), if
(8)
∥
ξ
x
k
∥
≥
ν
r
k
∥
x
k
-
x
^
k
∥
.
Letr
k
←
2
*
r
k, and go back to (s1).
(s2)
Solving the following variational inequality, findy
∈
𝒴 such that
(9)
(
y
′
-
y
)
T
{
g
(
y
k
)
+
[
λ
k
-
β
k
(
A
x
^
k
-
y
)
]
}
≥
0
,
∀
y
'
∈
𝒴
,
And denote the solution byy
^
k. Let ξ
y
k
=
g
(
y
k
)
-
g
(
y
^
k
), if
(10)
∥
ξ
y
k
∥
≥
ν
β
k
2
2
∥
y
k
-
y
^
k
∥
.Letβ
k
←
2
*
β
k, and go back to (s2).
(s3) Updateλ
^
k via
(11)
λ
^
k
=
λ
k
-
β
k
(
A
x
^
k
-
y
^
k
)
.
(s4)
Compute the step lengthα
k
>
0. Let
(12)
M
k
=
(
r
k
I
β
k
I
1
β
k
I
)
,
ξ
k
=
(
ξ
x
k
ξ
y
k
0
)
,
(13)
w
k
+
1
=
w
k
-
α
k
(
M
k
(
w
k
-
w
^
k
)
-
ξ
k
)
.Remark 1.
(
1
) The main difference between the APBPC method [4] and the proposed LSPPAD method is that the proximal term (
s
k
/
2
)
∥
y
-
y
k
∥
2 appears in the prediction step 2 of the APBPC method, while it vanishes in the LAPPAD method.
(2) In the LSPPAD method, (s1) is inherent one iteration of the projection gradient method for thex-subproblem based on the augmented Lagrangian function L
β
(
x
,
y
,
λ
) (see (2)) with the fixed y
=
y
k and step length 1
/
r
k. That is
(14)
x
^
k
=
P
𝒳
{
x
k
-
1
r
k
[
f
(
x
k
)
-
A
T
(
λ
k
-
β
k
(
A
x
k
-
y
k
)
)
]
}
.
And (s2) is one iteration of the same method for they-subproblem with the fixed x
=
x
^
k and step length 1
/
β
k; that is,
(15)
y
^
k
=
P
𝒴
{
y
k
-
1
β
k
[
g
(
y
k
)
+
(
λ
k
-
β
k
(
A
x
^
k
-
y
k
)
)
]
}
.Combining (7) and (9) together with (11) and by a manipulation we have
(16)
(
x
′
-
x
^
k
y
′
-
y
^
k
λ
′
-
λ
^
k
)
T
×
(
f
(
x
^
k
)
-
A
T
λ
^
k
+
β
k
A
T
(
y
k
-
y
^
k
)
+
r
k
(
x
^
k
-
x
k
)
+
ξ
x
k
g
(
y
^
k
)
+
λ
^
k
-
β
k
(
y
k
-
y
^
k
)
+
β
k
(
y
^
k
-
y
k
)
+
ξ
y
k
A
x
^
k
-
y
^
k
+
1
β
k
(
λ
^
k
-
λ
k
)
)
≥
0
.The following notations are useful for convenience in the future discussion:(17)
F
(
w
)
=
(
f
(
x
)
-
A
T
λ
g
(
y
)
+
λ
A
x
-
y
)
,
η
(
β
,
w
,
w
^
)
=
(
β
A
T
(
y
-
y
^
)
-
β
(
y
-
y
^
)
0
)
.
(18)
d
1
(
w
k
,
w
^
k
,
ξ
k
)
=
M
k
(
w
k
-
w
^
k
)
-
ξ
k
.
(19)
d
2
(
w
k
,
w
^
k
)
=
F
(
w
^
k
)
-
η
(
β
k
,
w
k
,
w
^
k
)
.
(20)
φ
(
w
k
,
w
^
k
,
ξ
k
)
=
(
λ
^
k
-
λ
k
)
T
(
y
k
-
y
^
k
)
+
(
w
k
-
w
^
k
)
T
d
1
(
w
k
,
w
^
k
,
ξ
k
)
.By these notations, the variational inequality (16) can be rewritten into a compact form:
(21)
w
^
k
∈
𝒲
,
(
w
′
-
w
^
k
)
T
[
d
2
(
w
k
,
w
^
k
)
-
d
1
(
w
k
,
w
^
k
,
ξ
k
)
]
≥
0
,
hhhhhhhhhhhhhhhhhhhhhhhhhhhhh
∀
w
′
∈
𝒲
.


## 3. Descent Directions of the Merit Function(
1
/
2
)
∥
w
-
w
*
∥
2

For the convenience of analysis, we ignore the indexk of the matrices, vectors, and scalars in the section.It is easy to show that, for allw
*
∈
𝒲
*, (
w
-
w
*
) is the gradient of the unknown merit function (
1
/
2
)
∥
w
-
w
*
∥
2 at the point w. The vector d is a descent direction of the merit function (
1
/
2
)
∥
w
-
w
*
∥
2 if and only if (
w
-
w
*
)
T
d
<
0. In the section, under suitable conditions, we will show that both -
d
1
(
w
,
w
^
,
ξ
) and -
d
2
(
w
,
w
^
) (see (18) and (19), resp.) are the descent directions of (
1
/
2
)
∥
w
-
w
*
∥
2 while w
∈
𝒲
∖
𝒲
*.Hereafter, we denoteu
T
H
u by the compact form ∥
u
∥
H
2 whenever H is a semidefinite symmetric matrix. It is obvious that ∥
u
∥
H
2
≥
0 by the semidefinite property of matrix H.Lemma 2.
For a givenw
∈
𝒲, let w
^
=
(
x
^
,
y
^
,
λ
^
) be generated by (s1) to (s3) of the LSPPAD method, and let φ
(
w
,
w
^
,
ξ
) be defined by (20). Then one has
(22)
φ
(
w
,
w
^
,
ξ
)
>
β
2
∥
A
x
^
-
y
∥
2
+
τ
2
∥
d
1
(
w
,
w
^
,
ξ
)
∥
2
,
where τ
=
min
⁡
⁡
{
1
/
r
,
1
/
2
β
,
β
}
>
0.Proof.
By a manipulation, we get(23)
φ
(
w
,
w
^
,
ξ
)
=
(
λ
^
-
λ
)
T
(
y
-
y
^
)
+
(
w
-
w
^
)
T
[
M
(
w
-
w
^
)
-
ξ
]
=
(
λ
^
-
λ
)
T
(
y
-
y
^
)
+
∥
w
-
w
^
∥
M
2
-
(
w
-
w
^
)
T
ξ
=
(
λ
^
-
λ
)
T
(
y
-
y
^
)
+
r
∥
x
-
x
^
∥
2
+
β
∥
y
-
y
^
∥
2
+
1
β
∥
λ
-
λ
^
∥
2
-
(
x
-
x
^
)
T
ξ
x
-
(
y
-
y
^
)
T
ξ
y
=
[
(
λ
^
-
λ
)
T
(
y
-
y
^
)
+
1
2
β
∥
y
-
y
^
∥
2
+
1
2
β
∥
λ
-
λ
^
∥
2
]
+
1
2
β
∥
λ
-
λ
^
∥
2
+
r
∥
x
-
x
^
∥
2
-
(
x
-
x
^
)
T
ξ
x
+
1
2
β
∥
y
-
y
^
∥
2
-
(
y
-
y
^
)
T
ξ
y
.
Substituting λ
^
-
λ
=
-
β
(
A
x
^
-
y
^
) into the first term of the right side of (23), we get
(24)
(
λ
^
-
λ
)
T
(
y
-
y
^
)
+
1
2
β
∥
y
-
y
^
∥
2
+
1
2
β
∥
λ
-
λ
^
∥
2
=
β
2
[
-
2
(
A
x
^
-
y
^
)
T
(
y
-
y
^
)
+
∥
y
-
y
^
∥
2
+
∥
A
x
^
-
y
^
∥
2
]
=
β
2
∥
A
x
^
-
y
∥
2
.
By (s1), we have ∥
ξ
x
k
∥
≤
ν
r
k
∥
x
k
-
x
^
k
∥. Note that ν
∈
(
0,1
); we get
(25)
r
∥
x
-
x
^
∥
2
-
(
x
-
x
^
)
T
ξ
x
=
1
2
r
∥
x
-
x
^
∥
2
-
(
x
-
x
^
)
T
ξ
x
+
1
2
r
∥
x
-
x
^
∥
2
=
1
2
r
[
r
2
∥
x
-
x
^
∥
2
-
2
r
(
x
-
x
^
)
T
ξ
x
+
r
2
∥
x
-
x
^
∥
2
]
>
1
2
r
[
r
2
∥
x
-
x
^
∥
2
-
2
r
(
x
-
x
^
)
T
ξ
x
+
∥
ξ
x
∥
2
]
=
1
2
r
∥
r
(
x
-
x
^
)
-
ξ
x
∥
2
.
Similarly, we have
(26)
1
2
β
∥
y
-
y
^
∥
2
-
(
y
-
y
^
)
T
ξ
y
=
1
4
β
∥
y
-
y
^
∥
2
-
(
y
-
y
^
)
T
ξ
y
+
1
4
β
∥
y
-
y
^
∥
2
=
1
β
[
∥
1
2
β
(
y
-
y
^
)
∥
2
-
1
2
β
(
y
-
y
^
)
T
ξ
y
+
∥
1
2
ξ
y
∥
2
+
1
4
β
2
∥
y
-
y
^
∥
2
-
∥
1
2
ξ
y
∥
2
-
1
2
β
(
y
-
y
^
)
T
ξ
y
]
=
1
4
β
∥
β
(
y
-
y
^
)
-
ξ
y
∥
2
+
1
β
[
1
4
β
2
∥
y
-
y
^
∥
2
-
∥
1
2
ξ
y
∥
2
-
1
2
β
(
y
-
y
^
)
T
ξ
y
]
.
By (s2), we have ∥
ξ
y
k
∥
≤
(
ν
β
k
/
2
2
)
∥
y
k
-
y
^
k
∥. Using Cauchy-Schwarz inequality, we get
(27)
β
2
(
y
-
y
^
)
T
ξ
y
≤
β
2
∥
y
-
y
^
∥
·
∥
ξ
y
∥
≤
β
2
4
2
∥
y
-
y
^
∥
2
.
Again using ∥
ξ
y
k
∥
≤
(
ν
β
k
/
2
2
)
∥
y
k
-
y
^
k
∥, we get
(28)
1
β
[
1
4
β
2
∥
y
-
y
^
∥
2
-
∥
1
2
ξ
y
∥
2
-
1
2
β
(
y
-
y
^
)
T
ξ
y
]
≥
β
4
7
2
-
8
8
2
∥
y
-
y
^
∥
2
≥
0
.
Thus
(29)
1
2
β
∥
y
-
y
^
∥
2
-
(
y
-
y
^
)
T
ξ
y
≥
1
4
β
∥
β
(
y
-
y
^
)
-
ξ
y
∥
2
.
Substituting (24), (25), and (29) into (23), we have
(30)
φ
(
w
,
w
^
,
ξ
)
>
1
2
β
∥
A
x
^
-
y
∥
2
+
1
2
r
∥
r
(
x
-
x
^
)
-
ξ
x
∥
2
+
1
4
β
∥
β
(
y
-
y
^
)
-
ξ
y
∥
2
+
1
2
β
∥
λ
-
λ
^
∥
2
.
Recalling
(31)
τ
=
min
⁡
{
1
r
,
1
2
β
,
β
}
,
we obtain
(32)
φ
(
w
,
w
^
,
ξ
)
>
β
2
∥
A
x
^
-
y
∥
2
+
τ
2
∥
d
1
(
w
,
w
^
,
ξ
)
∥
2
.Lemma 3.
By the same conditions of Lemma2 one has
(33)
φ
(
w
,
w
^
,
ξ
)
≥
(
1
-
ν
)
r
∥
x
-
x
^
∥
2
+
1
2
(
1
-
2
2
ν
)
β
∥
y
-
y
^
∥
2
+
1
2
β
∥
λ
-
λ
^
∥
2
.Proof.
By Cauchy-Schwarz inequality, we get(34)
(
x
-
x
^
)
T
ξ
x
≤
∥
x
-
x
^
∥
∥
ξ
x
∥
,
(
y
-
y
^
)
T
ξ
y
≤
∥
y
-
y
^
∥
∥
ξ
y
∥
.
Noting that β
>
0, we have
(35)
1
2
(
β
∥
y
-
y
^
∥
2
+
1
β
∥
λ
-
λ
^
∥
2
)
≥
1
β
∥
λ
-
λ
^
∥
β
∥
y
-
y
^
∥
≥
(
λ
-
λ
^
)
T
(
y
-
y
^
)
.
Then by (s1) and (s2), we get
(36)
φ
(
w
,
w
^
,
λ
)
=
(
λ
^
-
λ
)
T
(
y
-
y
^
)
+
(
w
-
w
^
)
T
[
M
(
w
-
w
^
)
-
ξ
]
=
(
λ
^
-
λ
)
T
(
y
-
y
^
)
+
(
x
-
x
^
)
T
r
(
x
-
x
^
)
-
(
x
-
x
^
)
T
ξ
x
+
(
y
-
y
^
)
T
β
(
y
-
y
^
)
-
(
y
-
y
^
)
T
ξ
y
+
(
λ
-
λ
^
)
T
1
β
(
λ
-
λ
^
)
≥
(
1
-
ν
)
r
∥
x
-
x
^
∥
2
+
(
1
-
ν
2
2
)
β
∥
y
-
y
^
∥
2
+
1
β
∥
λ
-
λ
^
∥
2
-
(
λ
-
λ
^
)
T
(
y
-
y
^
)
≥
(
1
-
ν
)
r
∥
x
-
x
^
∥
2
+
1
2
(
1
-
2
2
ν
)
β
∥
y
-
y
^
∥
2
+
1
2
β
∥
λ
-
λ
^
∥
2
.Lemma 4.
For a givenw
=
(
x
,
y
,
λ
)
∈
𝒲, let w
^
=
(
x
^
,
y
^
,
λ
^
) be generated by (s1) to (s3) of the LSPPAD method. Let φ
(
w
,
w
^
,
ξ
) be defined by (20), and let d
1
(
w
,
w
^
,
ξ
) and d
2
(
w
,
w
^
) be defined by (18) and (19), respectively. One has
(37)
(
w
^
-
w
*
)
T
d
2
(
w
,
w
^
)
≥
φ
(
w
,
w
^
,
ξ
)
-
(
w
-
w
^
)
T
d
1
(
w
,
w
^
,
ξ
)
.Proof.
Sincef
(
x
) (resp., g
(
x
)) is monotone with respect to 𝒳 (resp., 𝒴), it follows that F
(
w
) (see (17)) is a monotone operator with respect to 𝒲, we have
(38)
(
w
^
-
w
*
)
T
[
F
(
w
^
)
-
F
(
w
*
)
]
≥
0
,
and, consequently,
(39)
(
w
^
-
w
*
)
T
F
(
w
^
)
≥
(
w
^
-
w
*
)
T
F
(
w
*
)
.
Note that w
* is a solution of (3), which implies (
w
^
-
w
*
)
T
F
(
w
*
)
≥
0 for w
^
∈
𝒲. Thus (
w
^
-
w
*
)
T
F
(
w
^
)
≥
0. We have
(40)
(
w
^
-
w
*
)
T
d
2
(
w
,
w
^
)
=
(
w
^
-
w
*
)
T
F
(
w
^
)
-
(
w
^
-
w
*
)
T
η
(
β
k
,
w
k
,
w
^
k
)
≥
-
(
w
^
-
w
*
)
T
η
(
β
k
,
w
k
,
w
^
k
)
=
-
β
(
A
x
^
-
A
x
*
)
T
(
y
-
y
^
)
+
(
y
^
-
y
*
)
β
(
y
-
y
^
)
=
(
y
-
y
^
)
T
β
(
y
^
-
A
x
^
)
=
(
y
-
y
^
)
T
(
λ
^
-
λ
)
.
Recalling the definition of φ
(
w
,
w
^
,
ξ
), the inequality (37) follows from (40) directly.Theorem 5.
For a givenw
=
(
x
,
y
,
λ
)
∈
𝒲, let w
^
=
(
x
^
,
y
^
,
λ
^
) be generated by (s1) to (s3) of the LSPPAD method. Then one has
(41)
(
w
-
w
*
)
T
d
1
(
w
,
w
^
,
ξ
)
≥
φ
(
w
,
w
^
,
ξ
)
,
∀
w
*
∈
𝒲
*
,
(42)
(
w
-
w
*
)
T
d
2
(
w
,
w
^
)
≥
φ
(
w
,
w
^
,
ξ
)
,
∀
w
*
∈
𝒲
*
.Proof.
By (21), we get (by letting w
′
=
w
*)
(43)
(
w
^
-
w
*
)
T
d
1
(
w
,
w
^
,
ξ
)
≥
(
w
^
-
w
*
)
T
d
2
(
w
,
w
^
)
,
∀
w
^
∈
𝒲
.
Combining (43) and (37), we have
(44)
(
w
^
-
w
*
)
T
d
1
(
w
,
w
^
,
ξ
)
≥
φ
(
w
,
w
^
,
ξ
)
-
(
w
-
w
^
)
d
1
(
w
,
w
^
,
ξ
)
.
Thus (41) follows from (44). Adding (37) and (21), we get
(45)
(
w
′
-
w
*
)
T
d
2
(
w
,
w
^
)
≥
φ
(
w
,
w
^
,
ξ
)
-
(
w
-
w
′
)
T
d
1
(
w
,
w
^
,
ξ
)
,
∀
w
′
∈
𝒲
,
∀
w
*
∈
𝒲
*
.
By letting w
′
=
w, we get (42) from (45) directly.


## 4. Convergence Analysis

For establishing the convergence, we first prove the following contractility property.Lemma 6.
For a givenw
k
∈
𝒲, let w
k
+
1 be generated by the LSPPAD method. Then one has
(46)
∥
w
k
-
w
*
∥
2
-
∥
w
k
+
1
-
w
*
∥
2
≥
2
α
k
φ
(
w
k
,
w
~
k
,
ξ
k
)
-
α
k
2
∥
d
1
(
w
k
,
w
~
k
,
ξ
k
)
∥
2
.Proof.
Recall the definition ofd
1
(
w
k
,
w
^
k
,
ξ
k
) and the iteration formula (13); by a straightforward computation and Theorem 5, we get
(47)
∥
w
k
-
w
*
∥
2
-
∥
w
k
+
1
-
w
*
∥
2
=
∥
w
k
-
w
*
∥
2
-
∥
w
k
-
α
k
d
1
(
w
k
,
w
^
k
,
ξ
k
)
-
w
*
∥
2
=
2
α
k
(
w
k
-
w
*
)
T
d
1
(
w
k
,
w
^
k
,
ξ
k
)
-
α
k
2
∥
d
1
(
w
k
,
w
^
k
,
ξ
k
)
∥
2
≥
2
α
k
φ
(
w
k
,
w
~
k
,
ξ
k
)
-
α
k
2
∥
d
1
(
w
k
,
w
~
k
,
ξ
k
)
∥
2
.By Lemma6 we have
(48)
∥
w
k
+
1
-
w
*
∥
2
≤
∥
w
k
-
w
*
∥
2
+
α
k
2
∥
d
1
(
w
k
,
w
~
k
,
ξ
k
)
∥
2
-
2
α
k
φ
(
w
k
,
w
~
k
,
ξ
k
)
.
Thus, we can get the maximal drop-out value at each iteration by maximizing the following function:
(49)
Δ
k
(
α
)
=
-
α
2
∥
d
1
(
w
k
,
w
~
k
,
ξ
k
)
∥
2
+
2
α
φ
(
w
k
,
w
~
k
,
ξ
k
)
.
This quadratic function Δ
k
(
α
) reaches its maximum at the point
(50)
α
k
*
=
φ
(
w
k
,
w
~
k
,
ξ
k
)
∥
d
1
(
w
k
,
w
~
k
,
ξ
k
)
∥
2
,
with its value
(51)
Δ
k
(
α
k
*
)
=
α
k
*
φ
(
w
k
,
w
~
k
,
ξ
k
)
.
Thus, by Lemma 2 we have the following.Corollary 7.
If the constant sequences{
r
k
} and {
β
k
} are positive and bounded above for all iteration k, then one has
(52)
α
k
*
>
τ
2
.We will show later that the conditions of Corollary7 can be satisfied in practice.The numerical experiment [5] suggests that for fast convergence one can use a relaxation factor γ
∈
[
1,2
) and let α
k
=
γ
α
k
* at each iteration. To do so, we get
(53)
Δ
k
(
γ
α
k
*
)
=
γ
(
2
-
γ
)
Δ
k
(
α
k
*
)
.
By (46) or (49), we have
(54)
∥
w
k
+
1
-
w
*
∥
2
≤
∥
w
k
-
w
*
∥
2
-
γ
(
2
-
γ
)
α
k
*
φ
(
w
k
,
w
~
k
,
ξ
k
)
.
Furthermore, by Corollary 7, we have
(55)
∥
w
k
+
1
-
w
*
∥
2
≤
∥
w
k
-
w
*
∥
2
-
τ
2
γ
(
2
-
γ
)
φ
(
w
k
,
w
~
k
,
ξ
k
)
with
(56)
τ
=
min
⁡
k
{
1
r
k
,
1
2
β
k
,
β
k
}
.
The inequality (55) plays an important role in proving convergence of the proposed method.Letting(57)
N
=
(
2
(
1
-
ν
)
r
I
0
0
0
(
1
-
2
2
ν
)
β
I
0
0
0
1
β
I
)
,
by Lemma 3 we have
(58)
φ
(
w
,
w
^
,
ξ
)
≥
1
2
∥
w
-
w
^
∥
N
2
.
Combing (55) and (58), we get the Fejér monotonicity of the generated sequence {
w
k
}.Theorem 8.
Suppose the sequence{
w
k
} be generated by the LSPPAD method and the conditions of Corollary 7 hold. Then the sequence {
w
k
} converges to w
∞, which is a solution of the problem (3), or, equivalently, the problem (1).Proof.
By (55) and (58), we get
(59)
∥
w
k
+
1
-
w
*
∥
2
≤
∥
w
k
-
w
*
∥
2
-
τ
γ
(
2
-
γ
)
4
∥
w
k
-
w
^
k
∥
N
2
.
Consequently,
(60)
∥
w
k
+
1
-
w
*
∥
2
≤
∥
w
0
-
w
*
∥
2
,
∀
k
.
It follows that the sequence {
w
k
} is bounded. Moreover, we get
(61)
τ
γ
(
2
-
γ
)
4
∑
k
=
0
∞
‍
∥
w
k
-
w
^
k
∥
N
2
≤
∥
w
0
-
w
*
∥
2
,
from which it follows that
(62)
lim
⁡
k
→
∞
∥
w
k
-
w
^
k
∥
N
2
=
0
.
Thus {
w
^
k
} is bounded and it has at least one cluster point. Let w
∞ be a cluster point of {
w
^
k
}, and suppose the subsequence {
w
^
k
j
} converges to w
∞. It follows from (62) that
(63)
lim
⁡
k
→
∞
∥
x
k
-
x
^
k
∥
=
0
,
lim
⁡
k
→
∞
∥
y
k
-
y
^
k
∥
=
0
,
lim
⁡
k
→
∞
∥
λ
k
-
λ
^
k
∥
=
0
,
and, consequently (by (s1) and (s2)),
(64)
lim
⁡
k
→
∞
∥
ξ
x
k
∥
=
0
,
lim
⁡
k
→
∞
∥
ξ
y
k
∥
=
0
.
Then, by (7), (9), and (11), we get
(65)
w
^
k
∈
𝒲
,
{
lim
⁡
k
→
∞
(
x
′
-
x
^
k
)
T
{
f
(
x
^
k
)
-
A
T
λ
^
k
}
≥
0
,
lim
⁡
k
→
∞
(
y
′
-
y
^
k
)
T
{
g
(
y
^
k
)
+
λ
^
k
}
≥
0
,
lim
⁡
k
→
∞
(
A
x
^
k
-
y
^
k
)
=
0
,
∀
w
′
∈
𝒲
,
(66)
w
^
k
j
∈
𝒲
,
{
lim
⁡
k
j
→
∞
(
x
′
-
x
^
k
j
)
T
{
f
(
x
^
k
j
)
-
A
T
λ
^
k
j
}
≥
0
,
lim
⁡
k
j
→
∞
(
y
′
-
y
^
k
j
)
T
{
g
(
y
^
k
j
)
+
λ
^
k
j
}
≥
0
,
lim
⁡
k
j
→
∞
(
A
x
^
k
j
-
y
^
k
j
)
=
0
,
∀
w
′
∈
𝒲
,
which implies that
(67)
w
^
∞
∈
𝒲
,
{
(
x
′
-
x
^
∞
)
T
{
f
(
x
^
∞
)
-
A
T
λ
^
∞
}
≥
0
,
(
y
′
-
y
^
∞
)
T
{
g
(
y
^
∞
)
+
λ
^
∞
}
≥
0
,
(
A
x
^
∞
-
y
^
∞
)
=
0
,
∀
w
'
∈
𝒲
.
Thus w
∞ solves the variational inequalities (3).
Since{
w
^
k
j
}
→
w
∞, by (62), for any ɛ
>
0, there exists an integer l
>
0 such that
(68)
∥
w
k
l
-
w
^
k
l
∥
N
<
ɛ
2
,
∥
w
^
k
l
-
w
∞
∥
N
<
ɛ
2
.
Therefore, for any k
≥
k
l, we have
(69)
∥
w
k
-
w
∞
∥
N
≤
∥
w
k
l
-
w
∞
∥
N
≤
∥
w
k
l
-
w
^
k
l
∥
N
+
∥
w
^
k
l
-
w
∞
∥
N
<
ɛ
,
which implies that the sequence {
w
k
} converges to w
∞, which is a solution of the problem (3) or the problem (1).


## 5. Practical Implementation and Numerical Results

For the implementation of the proposed method, we have to give some rules to determine the proximal parameterr
k and penalty parameter β
k.It follows from (56) that if the sequences {
r
k
}
,
{
β
k
} are positive and bounded, then τ is well defined and τ
>
0, which guarantees that the conditions of Corollary 7 hold.On the penalty parameter sequence{
β
k
}, He et al. [9] proposed a self-adaptive rule at each iteration based on the iterate information, which is referred to as self-adaptive penalty parameters method, and showed that the sequence {
β
k
} generated by the method is bounded and away from zero. In the proposed method of this paper, we use directly the self-adaptive penalty parameters method (Method 3, Strategy S3 in [9]). The self-adaptive rule is
(70)
2
*
β
k
,
if
∥
y
k
+
1
-
y
k
∥
∞
<
0.25
∥
λ
k
+
1
-
λ
k
∥
∞
,
0.5
*
β
k
,
if
0.25
∥
y
k
+
1
-
y
k
∥
∞
>
∥
λ
k
+
1
-
λ
k
∥
∞
,
β
k
,
otherwise
.
Combing (70) and the line search in (s2) of the LSPPAD method, we have that the sequence {
β
k
} is positive, away from zero and bounded above.We next focus on the proximal parameter sequence{
r
k
}.Lemma 9.
Iff is monotone and Lipschitz continuous with constant L
f, that is,
(71)
∥
f
(
x
)
-
f
(
x
^
)
∥
≤
L
f
∥
x
-
x
^
∥
,
∀
x
,
x
^
∈
𝒳
,
then, whenever
(72)
r
k
≥
L
f
+
β
k
∥
A
T
A
∥
ν
one has ∥
ξ
x
∥
≤
ν
r
k
∥
x
-
x
k
∥.Proof.
Recall the definition ofξ
x
k in (s1) of the LSPPAD method; by (71) we get
(73)
∥
ξ
x
k
∥
=
∥
f
(
x
k
)
-
f
(
x
)
+
β
k
A
T
A
(
x
k
-
x
)
∥
≤
∥
f
(
x
k
)
-
f
(
x
)
∥
+
∥
β
k
A
T
A
(
x
k
-
x
)
∥
≤
L
f
∥
x
k
-
x
∥
+
β
k
∥
A
T
A
∥
∥
x
k
-
x
∥
≤
ν
r
k
∥
x
-
x
k
∥
.Lemma9 indicates that the line search in (s1) will terminate in finite number of iterations.In practice we use a self-adaptive rule to guaranteer
k not tend to infinity under the line search in (s1) of the LSPPAD method. The self-adaptive rule is letting r
k
=
r
k
*
κ
*
ρ whenever κ
=
∥
ξ
x
k
∥
/
r
k
∥
x
k
-
x
^
k
∥
<
0.5, where ρ
=
1.85. By this rule and the step (s1) of the LAPPAD method, {
r
k
} is obviously bounded away from zero; thus the condition on {
r
k
} of Corollary 7 holds.Finally, we give some numerical experiments on compressed sensor problem; see [10]. These experiments are tested on a laptop with 166 GHz CPU, 2.5 GB RAM, and Matlab 6.5.The separable convex optimization formulation of compressed sensor problem is(74)
min
⁡
1
2
∥
D
x
-
b
∥
2
2
+
μ
∥
y
∥
1
,
s
.
t
.
x
-
y
=
0
,
where x
,
y
∈
R
n
,
D
∈
R
m
×
n
,
b
∈
R
m
,
and
μ
>
0. In the test problem, θ
2
(
y
)
=
μ
∥
y
∥
1 is nonsmooth. However, the special structure of the problem (74) admits the equivalence relation between the problems (1) and (3) if the subderivative of the absolute value function |
u
| is specialized as follows:
(75)
∂
(
|
u
|
)
∋
g
(
u
)
=
{
1
,
if
u
>
0
,
0
,
if
u
=
0
,
-
1
,
if
u
<
0
.
So the proposed method is available for this problem.The test data of the problem (74) is generated by the following style: D
∈
R
m
×
n is a random matrix with D
i
j
∈
(
1,2
) according to uniform distribution, and b
∈
R
m is a given signal vector with a random noise, μ
=
0.2. The practical parameters of the LSPPAD method are given in the following: ν
=
0.95
,
r
0
=
0.51
*
max
⁡
(
σ
(
A
A
T
)
) (where σ
(
A
A
T
) denotes the eigenvalue of A
A
T), β
0
=
1.5
,
x
0
=
0
n
×
1
,
y
0
=
1
n
×
1
,
λ
0
=
1
n
×
1
,
and
γ
=
1.5. The experimental results are stated in Table 1. The notation in Table 1 is as follows: m
,
n, and cputime are clear; sp denotes the required sparse degree; function evaluations is the number of computation of product on matrix and vector (which is the main cost of the proposed method). The process stops whenever max
⁡
{
∥
x
k
-
x
^
k
∥
∞
,
∥
y
k
-
y
^
k
∥
∞
,
∥
λ
k
-
λ
^
k
∥
∞
}
<
1.0
×
1
0
-
3.Table 1
Numerical results on compressed sensor problems.
m
n
sp
Iteration number
Function evaluations
Cputime (in second)
LSPPAD
APBPC
LSPPAD
APBPC
LSPPAD
APBPC
1024
4096
160
/
4096
95
152
291
496
3.92
7.24
1600
8192
320
/
8192
104
212
318
632
13.0
24.4
2048
12000
400
/
12000
104
238
318
756
24.8
56.8
3052
16438
512
/
16438
106
252
324
812
49.1
120.6The numerical results show that the proposed LSPPAD method has better performance compared with the APBPC method for the test problem.


## 6. Conclusions

In this paper, we present a line-search-based partial proximal alternating directions (LSPPAD) method for solving a class of structured convex optimization problems. This kind of problems is common in practice. The LSPPAD method makes full use of the special structure of the described problem. In the LSPPAD method, two subproblems are solved in an alternative fashion. The subproblem ofy variable is solved without the proximal term, while the x-subproblem is solved by a proximal point method; both used line-search technique to guarantee the convergence. To do so provides some advantages for the tractability. The convergence property of the LSPPAD method is established. Numerical tests show that, due to the described problem, the LSPPAD method has better performance compared with the APBPC method which solves both subproblems by the inexact proximal point method.



---

*Source: 540450-2014-05-07.xml*