# Smoothing Nonmonotone Barzilai-Borwein Gradient Method and Its Application to Stochastic Linear Complementarity Problems

Authors: Xiangli Li
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

A new algorithm for nonsmooth box-constrained minimization is introduced. The method is a smoothing nonmonotone Barzilai-Borwein (BB) gradient method. All iterates generated by this method are feasible. We apply this method to stochastic linear complementarity problems. Numerical results show that our method is promising.


---

## Body

## 1. Introduction

In this paper, we consider a problem(1)
m
i
n
f
x
s
.
t
.
x
∈
X
,where (2)
X
=
x
∈
R
n
∣
l
≤
x
≤
u
,
l
,
u
∈
R
n, and f
:
R
n
→
R. If f is differentiable on the feasible set, there are many methods for (1), such as trust region method [1], projected gradient method [2], projected Barzilai-Borwein method [3], Newton method [4], and active-set projected trust region [5]. If f is semismooth, there are few methods for (1). In this paper, we only consider that f is locally Lipschitzian, but not necessarily differentiable.In [6], a smoothing projected gradient method (SPG) was introduced for nonsmooth optimization problems with nonempty closed convex set. This algorithm is easy to implement. At each iteration, authors approximate the objective function by a smooth function with a fixed smoothing parameter and employ the classical projected gradient method to obtain a new point. If a certain criterion is satisfied, then authors update the smoothing parameter using the new point for the next iteration.The main motivation for the current work come from the numerical results of [6]. Through analyzing the algorithm [6], we find that it takes a lot of time to calculate projection when test problems are large-scale. In order to avoid this shortcoming, we propose a smoothing nonmonotone BB gradient method. In our method, we use an active set and a nonmonotone line search strategy. The search direction consists of two parts: some of the components are simply defined; the other components are determined by the Barzilai-Borwein gradient method. We apply it to stochastic linear complementarity problems.Throughout this paper,· will be the Euclidean norm. For all y
∈
R
n, the orthogonal projection of y onto a set S will be denoted by P
S
(
y
). For a given matrix D
=
[
d
i
j
]
∈
R
n
×
n, D
i
· will be the ith row of D.The paper can be outlined as follows. In Section2, we describe our method. In Section 3, stochastic linear complementarity problems are introduced. In Section 4, we apply our method to stochastic linear complementarity problems and numerical results are illustrated and discussed. Finally, we make some concluding remarks in Section 5.


## 2. Smoothing Nonmonotone BB Gradient Method

In this section, we propose a smoothing nonmonotone BB gradient method for (1), where f is a general locally Lipschitz continuous function.Definition 1.
Letf
:
R
n
→
R be a locally Lipschitz continuous function. One calls f
-
:
R
n
×
R
+
→
R a smoothing function of f, if f
-
(
·
,
μ
) is continuously differentiable in R
n for any μ
∈
R
+
+, and, for any x
∈
R
n, (3)
lim
z
→
x
,
μ
↓
0
⁡
f
-
z
,
μ
=
f
xand {
l
i
m
z
→
x
,
μ
↓
0
∇
x
f
-
(
z
,
μ
)
} is nonempty and bounded.LetN
=
{
1,2
,
…
,
n
}. Consider the associated set at the stationary point x
∗ of function f
-
x
,
μ
k: (4)
L
-
=
i
:
l
i
=
x
i
∗
,
U
-
=
i
:
u
i
=
x
i
∗
,
F
-
=
N
∖
L
-
∪
U
-
,where μ
k is a fixed parameter. For x
k
∈
X, we define index set L
(
x
k
), U
(
x
k
), and F
(
x
k
) as follows:(5)
L
x
k
≔
i
:
l
i
≤
x
i
k
≤
l
i
+
λ
k
∇
f
-
i
x
k
,
μ
k
,
U
x
k
≔
i
:
u
i
+
λ
k
∇
f
-
i
x
k
,
μ
k
≤
x
i
k
≤
u
i
,
F
x
k
≔
N
∖
L
x
k
∪
U
x
k
,where λ
m
i
n
≤
λ
k
≤
λ
m
a
x
(
0
<
λ
m
i
n
<
λ
m
a
x
). The set L
x
k
∪
U
(
x
k
) is an estimate of the active set at point x
k. For simplicity, we abbreviate L
(
x
k
), U
(
x
k
), and F
(
x
k
) defined by (5) as L
k, U
k, and F
k, respectively. We determine d
k by the following process:(6)
d
i
k
=
l
i
-
x
i
k
,
i
f
i
∈
L
k
u
i
-
x
i
k
,
i
f
i
∈
U
k
-
λ
k
∇
x
f
-
i
x
k
,
μ
k
,
i
f
i
∈
F
k
.It is easy to show x
k
+
d
k
∈
X.Now, we state algorithm as follows.Algorithm 2.
(
s
.
0
)
Choose positive constantsμ
0, γ, a tolerance parameter ɛ
>
0, integer M
≥
1, constants δ
,
τ
,
σ
,
ρ
∈
(
0,1
), and parameters λ
m
a
x
>
λ
m
i
n
>
0; choose an initial point l
≤
x
0
≤
u, λ
0
∈
[
λ
m
i
n
,
λ
m
a
x
]. Set k
=
0.
(
s
.
1
)
Stop ifμ
k
≤
ɛ. Otherwise, set (7)
k
′
=
0
,
t
k
′
=
x
k
,
λ
k
′
=
λ
k
,
C
k
′
=
f
-
t
k
′
,
μ
k
,
m
k
′
=
0
.
(
s
.
2
)
IfP
X
[
t
k
′
-
∇
x
f
-
(
t
k
′
,
μ
k
)
]
-
t
k
′
<
γ
μ
k, choose μ
k
+
1
≤
σ
μ
k, and set x
k
+
1
=
t
k
′. Let k
=
k
+
1, and go to Step  1.
(
s
.
3
)
DetermineL
k
′
=
L
(
t
k
′
), U
k
′
=
U
(
t
k
′
), and F
k
′
=
F
(
t
k
′
) according to (5).
(
s
.
4
)
Compute directiond
k
′ according to (6).
(
s
.
5
)
Compute the step sizeν
k
′ by the Armijo line search, ν
k
′
=
m
a
x
{
δ
0
,
δ
1
,
…
} satisfying (8)
f
-
t
k
′
+
ν
k
′
d
k
′
,
μ
k
≤
C
k
′
+
ρ
ν
k
′
∇
x
f
-
t
k
′
,
μ
k
T
d
k
′
.
Sett
k
′
+
1
=
t
k
′
+
ν
k
′
d
k
′, s
k
′
=
t
k
′
+
1
-
t
k
′, and y
k
′
=
∇
x
f
-
(
t
k
′
+
1
,
μ
k
)
-
∇
x
f
-
(
t
k
′
,
μ
k
).
(
s
.
6
)
Computen
k
′
=
(
s
k
′
)
T
y
k
′, m
k
′
=
s
k
′
2, and w
k
′
=
y
k
′
2.
Ifn
k
′
≤
0, λ
B
B
1
k
′
+
1
=
λ
m
a
x; otherwise, λ
B
B
1
k
′
+
1
=
m
k
′
/
n
k
′.
Ifw
k
′
=
0, λ
B
B
2
k
′
+
1
=
λ
m
a
x; otherwise, λ
B
B
2
k
′
+
1
=
n
k
′
/
w
k
′.
Set(9)
λ
k
′
+
1
=
min
⁡
λ
m
a
x
,
max
⁡
λ
m
i
n
,
λ
A
B
B
k
′
+
1
,
where(10)
λ
A
B
B
k
′
+
1
=
λ
B
B
1
k
′
+
1
,
f
o
r
o
d
d
k
′
+
1
λ
B
B
2
k
′
+
1
,
f
o
r
e
v
e
n
k
′
+
1
.
(
s
.
7
)
Letm
(
k
′
+
1
)
=
m
i
n
{
m
(
k
′
)
+
1
,
M
} and C
k
′
+
1
=
τ
·
m
(
k
′
+
1
)
C
k
′
+
f
-
(
t
k
′
+
1
,
μ
k
)
/
τ
·
m
(
k
′
+
1
)
+
1.
(
s
.
8
)
Letk
′
=
k
′
+
1
. Go to Step  2.Remark 3.
In Step  2 of Algorithm2, we use μ
k
+
1
≤
σ
μ
k to update the smoothing parameter.Remark 4.
Algorithm2 employs a two-loop approach: the outer loop updates smoothing parameter μ, and the inner loop computes a stationary point of f
-
(
·
,
μ
k
). In Step  4, the alternate BB step is used to compute the direction d
k
′.Remark 5.
Note thatl
i
m
k
→
∞
μ
k
=
0, so there exists an infinite subsequence K
1
⊆
K such that (11)
P
X
x
k
-
∇
x
f
-
x
k
,
μ
k
-
1
-
x
k
=
0
.This implies that every limit point generated by Algorithm 2 is a stationary point of (1).The convergence of Algorithm2 is similar to literature [6, 7], so we omit the process here.


## 3. Stochastic Linear Complementarity Problems

Let(
Ω
,
F
,
P
) be a probability space with Ω being a subset of R
m. Suppose that the probability distribution P is known. The stochastic linear complementarity problem (SLCP) [8] is to find x
∈
R
n such that(12)
M
ω
x
+
q
ω
≥
0
,
x
≥
0
,
x
T
M
ω
x
+
q
ω
=
0
,
ω
∈
Ω
,where M
(
ω
)
∈
R
n
×
n and q
(
ω
)
∈
R
n for ω
∈
Ω are random matrices and vectors. Throughout this paper, we assume that M
(
ω
) and q
(
ω
) are measurable functions of ω and satisfy (13)
E
M
ω
2
+
q
ω
2
<
∞
,where E stands for the expectation. IfΩ only contains a single realization, then (12) reduces to the standard LCP. The LCP has been studied by many researchers [9–14]. Since, in many practical problems, some elements may involve uncertain data, problem (12) has been receiving much attention in recent literature [8, 15–20].In general, there is nox satisfying (12) for almost ω
∈
Ω. A deterministic formulation for the SLCP provides a decision vector which is optimal in a certain sense. Different deterministic formulations may yield different solutions that are optimal in different senses. There are two reformulations of (12) that have been proposed: the expected value (EV) formulation [15] and the expected residual minimization (ERM) formulation [8]. In this paper, we concentrate on ERM. ERM is to find a vector x
∈
R
+
n that minimizes the expected residual of the SLCP (
M
(
ω
)
,
q
(
ω
)
); that is,(14)
min
x
∈
R
+
n
⁡
g
x
=
E
Φ
x
,
ω
2
,where Φ
:
R
n
×
Ω
→
R
n is defined by (15)
Φ
x
,
ω
=
ϕ
M
ω
x
1
+
q
1
ω
,
x
1
⋮
ϕ
M
ω
x
n
+
q
n
ω
,
x
n
.
[
x
]
i denotes the ith component of the vector x. Here, ϕ
:
R
2
→
R is an NCP function which has the property (16)
ϕ
a
,
b
=
0
⟺
a
≥
0
,
b
≥
0
,
a
b
=
0
.In this paper, we choose ϕ
(
a
,
b
)
=
m
i
n
(
a
,
b
).Letθ
w
x
=
1
/
2
Φ
x
,
ω
2; by [6], we know that g
(
x
)
=
2
E
(
θ
w
(
x
)
) is semismooth and ϕ
(
a
,
b
,
μ
) is a smoothing function of ϕ
(
a
,
b
), where (17)
ϕ
a
,
b
,
μ
=
b
,
i
f
a
-
b
≥
μ
2
a
-
1
2
μ
a
-
b
+
μ
2
2
,
i
f
-
μ
2
<
a
-
b
<
μ
2
a
,
i
f
a
-
b
≤
-
μ
2
.Hence, g
-
(
x
,
μ
) is a smoothing function of g
(
x
), where (18)
g
-
x
,
μ
=
2
E
θ
-
ω
x
,
μ
,and θ
-
ω
:
R
n
×
R
+
+
→
R is defined by (19)
θ
-
ω
x
,
μ
=
1
2
Φ
x
,
ω
,
μ
2
,
Φ
(
x
,
ω
,
μ
)
i
=
ϕ
(
[
M
(
ω
)
x
]
i
+
q
i
(
ω
)
,
x
i
,
μ
).In [6], authors use sample average approximation (SAA) [21], which replaces (14) by its approximation(20)
g
^
N
x
≔
2
N
∑
i
=
1
N
θ
ω
i
x
.Here, the sample ω
1
,
…
,
ω
N is generated by Monte Carlo sampling method, following the same probability distribution as ω. So, a smoothing function of g
^
N
(
x
) is (21)
g
~
N
x
,
μ
≔
2
N
∑
i
=
1
N
θ
-
ω
i
x
,
μ
.In the next section, we apply Algorithm 2 to (20).


## 4. Numerical Results

The test problems are randomly generated. The procedure of generating the tested problems is employed from [16, 20]. We omit the procedure here. All these problems are tested in Matlab (version 7.5).Several parameters are needed to generate the problem:n
x, σ, and β. A vector x
^
∈
R
+
n is randomly generated. When the parameter β
=
0, then x
^ is the unique global solution of the test problems and g
(
x
^
)
=
0. If β
>
0, the global solution is unknown.Algorithm2 contains several parameters; we use the values (22)
μ
0
=
1
,
γ
=
1
0
3
,
ɛ
=
1
0
-
6
,
M
=
5
,
δ
=
0.5
,
τ
=
0.3
,
σ
=
0.1
,
ρ
=
0.1
,
λ
m
i
n
=
1
0
-
6
,
λ
m
a
x
=
1
,
λ
0
=
1in all numerical experiments. We terminate the iteration if one of the following conditions is satisfied: (23)
μ
k
≤
ɛ
o
r
k
≥
k
m
a
x
=
100
.We start from the same randomly generated initial point(24)
x
0
=
f
l
o
o
r
1
+
10
∗
rand
⁡
n
,
1and compare our method with SPG. The numerical results can be seen in Tables 1-2. Let (25)
r
x
=
min
⁡
x
,
∇
g
xif g is differentiable at x. In Tables 1-2, n denote the number of variables; r
(
x
t
) and r
(
x
f
) present r
(
·
) at the finial iterates x
t and x
f, respectively; g
(
x
t
) and g
(
x
f
) denote the value of g
(
·
) at the final iterates x
t and x
f, respectively.Table 1
Numerical results forβ
=
0.
(N, n, n
x, σ)
Algorithm2
SPG
r
(
x
t
)
g
(
x
t
)
CPU
r
(
x
f
)
g
(
x
f
)
CPU
(100, 20, 10, 20)
1.450e − 04
1.923e − 11
0.047
2.907e − 04
8.295e − 11
0.281
(100, 20, 10, 10)
9.718e − 05
2.741e − 11
0.047
2.757e − 04
2.872e − 10
0.156
(100, 20, 10, 0)
6.125e − 04
3.791e − 07
0.313
1.098e − 03
1.144e − 06
2.438
(100, 40, 20, 20)
6.406e − 04
1.943e − 10
0.188
6.900e − 04
1.340e − 10
1.531
(100, 40, 20, 10)
2.363e − 04
9.364e − 11
0.156
6.327e − 04
4.385e − 10
1.188
(100, 40, 20, 0)
9.764e − 04
1.156e − 06
0.703
3.012e − 03
1.027e − 06
5.953
(200, 60, 30, 20)
2.083e − 04
9.858e − 12
1.016
8.388e − 04
1.658e − 10
12.547
(200, 60, 30, 10)
3.174e − 04
8.098e − 11
1.000
6.856e − 04
4.393e − 10
7.625
(200, 60, 30, 0)
9.381e − 04
1.015e − 06
5.109
1.127e − 03
9.025e − 07
52.625
(200, 80, 40, 20)
2.786e − 04
1.487e − 11
1.922
2.383e − 04
1.293e − 11
10.547
(200, 80, 40, 10)
7.646e − 05
4.496e − 12
1.781
4.530e − 04
1.849e − 10
7.984
(200, 80, 40, 0)
6.546e − 04
1.187e − 07
10.453
1.122e − 03
7.939e − 07
60.391
(200, 100, 50, 20)
2.178e − 04
8.540e − 12
3.031
1.552e − 04
4.652e − 12
12.609
(200, 100, 50, 10)
3.605e − 04
7.120e − 11
2.750
2.961e − 04
6.574e − 11
9.297
(200, 100, 50, 0)
9.332e − 04
9.131e − 07
16.828
3.471e − 03
9.422e − 07
117.703
(300, 120, 60, 20)
9.365e − 04
9.237e − 11
6.313
4.712e − 05
3.370e − 13
17.797
(300, 120, 60, 10)
2.435e − 04
2.555e − 11
5.781
9.311e − 05
5.264e − 12
14.078
(300, 120, 60, 0)
8.956e − 04
1.009e − 06
35.656
1.359e − 03
8.088e − 07
231.656
(1000, 50, 25, 10)
1.183e − 04
1.785e − 11
3.078
8.176e − 04
6.966e − 10
49.734
(1000, 50, 25, 0)
7.092e − 04
1.117e − 07
24.359
1.439e − 03
9.236e − 07
137.047Table 2
Numerical results forβ
>
0.
(N, n, n
x, σ)
Algorithm2
SPG
r
(
x
t
)
g
(
x
t
)
CPU
r
(
x
f
)
g
(
x
f
)
CPU
(100, 20, 10, 20, 10)
2.384e − 04
5.326e + 02
0.109
6.918e − 04
5.325e + 02
0.469
(100, 20, 10, 20, 5)
6.564e − 05
1.455e + 02
0.078
3.865e − 04
1.455e + 02
0.484
(100, 40, 20, 20, 10)
5.222e − 05
9.491e + 02
0.250
2.156e − 04
9.491e + 02
0.859
(100, 40, 20, 20, 5)
7.980e − 04
3.096e + 02
0.234
4.781e − 04
3.096e + 02
1.625
(100, 40, 20, 10, 20)
8.711e − 04
2.413e + 03
0.531
2.632e − 04
2.416e + 03
0.734
(200, 60, 30, 20, 10)
9.097e − 04
1.752e + 03
1.109
5.129e − 04
1.752e + 03
13.016
(200, 60, 30, 20, 5)
5.947e − 04
4.115e + 02
1.078
4.898e − 04
4.115e + 02
17.047
(200, 80, 40, 20, 10)
9.220e − 04
1.773e + 03
2.109
4.182e − 04
1.773e + 03
16.828
(200, 80, 40, 20, 5)
5.758e − 04
6.038e + 02
1.984
4.215e − 04
6.038e + 02
13.859
(200, 100, 50, 20, 10)
8.910e − 04
2.577e + 03
4.922
2.475e − 04
2.577e + 03
20.859
(200, 100, 50, 20, 5)
5.727e − 04
7.772e + 02
3.078
1.726e − 04
7.772e + 02
14.063
(200, 100, 50, 10, 20)
5.363e − 04
7.329e + 03
5.359
2.786e − 04
7.328e + 03
21.297
(300, 120, 60, 20, 10)
7.976e − 04
2.953e + 03
7.578
3.600e − 04
2.953e + 03
40.125
(300, 120, 60, 20, 5)
9.890e − 05
9.607e + 02
6.609
1.061e − 04
9.607e + 02
21.828
(300, 120, 60, 10, 20)
9.449e − 04
7.566e + 03
13.922
4.752e − 04
7.567e + 03
44.484
(300, 120, 60, 20, 20)
3.839e − 04
8.263e + 03
8.313
3.692e − 04
8.262e + 03
35.453
(1000, 50, 25, 20, 10)
4.506e − 04
1.405e + 03
3.656
4.315e + 00
1.405e + 03
22.391
(1000, 50, 25, 10, 5)
2.947e − 04
3.753e + 02
3.297
5.873e − 04
3.753e + 02
23.734
(1000, 100, 50, 5, 10)
1.118e − 04
2.836e + 03
20.797
3.124e − 04
2.836e + 03
85.547
(1000, 100, 50, 10, 5)
1.700e − 04
8.009e + 02
13.484
9.510e − 05
8.009e + 02
53.516The results reported in Tables1-2 show that smoothing nonmonotone BB gradient method is quite promising. From results shown in Tables 1-2, we observe that, firstly, Algorithm 2 has less time for all test problems. Secondly, the function values of Algorithm 2 and SPG are close for most test problems. Through analysis, we find that Algorithm 2 drops faster than SPG in each step. This is mainly attributed to the active set and BB step.


## 5. Concluding Remarks

In this paper, we present a smoothing nonmonotone Barzilai-Borwein gradient method for nonsmooth box-constrained minimization. The main idea of our method is to use a parametric smoothing approximation function in nonmonotone BB gradient method. In order to have a high speed of convergence, we calculate two-step size. We use BB method and inexact line search, which make sure that the algorithm has high efficiency. We apply it to stochastic linear complementarity problems. Numerical results show that our method is promising.



---

*Source: 425351-2015-09-30.xml*