# A Nonmonotone Weighting Self-Adaptive Trust Region Algorithm for Unconstrained Nonconvex Optimization

Authors: Yunlong Lu; Weiwei Yang; Wenyu Li; Xiaowei Jiang; Yueting Yang
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

A new trust region method is presented, which combines nonmonotone line search technique, a self-adaptive update rule for the trust region radius, and the weighting technique for the ratio between the actual reduction and the predicted reduction. Under reasonable assumptions, the global convergence of the method is established for unconstrained nonconvex optimization. Numerical results show that the new method is efficient and robust for solving unconstrained optimization problems.


---

## Body

## 1. Introduction

Consider the following unconstrained optimization problem:(1)min⁡x∈Rnfx,where f:Rn→R is continuously differentiable.The trust region methods calculate a trial stepdk by solving the subproblem at each iteration,(2)min⁡qkd=fxk+12dTBkd+gkTds.t.d≤Δk,where gk=∇f(xk) and Bk is symmetric matrix approximating the Hessian of f(x) at xk and Δk>0 is a trust region radius at xk. Throughout this paper, · denotes the Euclidean norm on Rn. Define the ratio (3)rkO=fxk-fxk+dkqk0-qkdk,and the numerator and the denominator are called the actual reduction and the predicted reduction, respectively.The nonmonotone line search technique is firstly proposed by Grippo et al. [1] in line search framework for Newton’s method. At each iteration, the selected function value is taken as(4)flk=max0≤j≤mk⁡fxk-j,where m(0)=0,0≤m(k)≤min⁡{m(k-1)+1,M},M is a positive integer. Although many algorithms based on (4) work well in many cases, a “good” function value generated as the iteration process is not selected because of the max function in (4), and the choice of M is sensitive to some numerical tests sometimes. To overcome shortages, Zhang and Hager [2] proposed a new nonmonotone line search technique and they used Ck to replace the function in (4), where(5)Ck=ζk-1Qk-1Ck-1+fxkQk,where Qk=ζk-1Qk-1+1,Q0=1, andC0=f(x0),ζk-1∈[0,1]. Numerical tests have shown that the new nonmonotone algorithm is more effective.Many researchers proposed many trust region methods by considering the ratiork and the updating trust region radius to solve effectively unconstrained optimization problem. Dai and Xu [3] proposed the following weighting formula:(6)r^k=∑i=0min⁡k,mωkirk-iO,where m is some positive integer and ωki∈[0,1] is the weight of rk-i, such that (7)∑i=0min⁡k,mωki=1.Many self-adaptive adjustment strategies are developed to update the trust region radius, such as [4–14]. In addition, many adaptive nonmonotonic trust region methods have been proposed in literatures [15–21].In this paper, we propose a new self-adaptive weighting trust region method based on the nonmonotone technique (4) in [2], the weighting technique (5) in [3], and L-function in [6].The rest of the paper is organized as follows. In Section2, we define L-function to introduce a new update rule and a new nonmonotone self-adaptive trust region algorithm is presented. In Section 3, the convergence properties of the proposed algorithm are investigated. In Section 4, numerical results are given. In Section 5 conclusions are summarized.


## 2.L-Function and the New Nonmonotone Self-Adaptive Trust Region Algorithm

To obtain the new trust region radius update rules, we recallL-function L(t),t∈R.Definition 1 (see [6]).
A functionL(t) is called an L-function if it satisfies the following.(1)
L(t) is nondecreasing in (-∞,η2] and nonincreasing in (2-η2,+∞), L(t)=β2, for t∈[η2,2-η2],(2)
limt→-∞⁡L(t)=c1,(3)
L(0)=c2,(4)
limt→η2-⁡L(t)=1,(5)
limt→0+⁡L(t)=β1,(6)
L(t)<1, for t>η3,(7)
limt→+∞⁡L(t)=β3,where the constants β1, β2, β3, η2, η3, c1, and c2 are positive constants such that (8)0<c1<c2<β1≤β3<1<β2,η3>2-η2,0.5≤η2<1.Now we describe the new nonmonotone self-adaptive trust region algorithm.Algorithm 2.
Step  1. Given x0∈Rn,B0∈Rn×n,0<η2<1, 0<c1<c2<1,0<β1≤β3<1≤β2, and Δ0>0;m is a given small positive integer; ɛ≥0;0≤ζmin≤ζmax<1, Q0=1; and set k:=0.
Step  2. If gk≤ɛ, stop.
Step  3. Solve subproblem (2) to get dk.
Step  4. Compute (9)rk=AredkPredk=Ck-fxk+dkϕk0-ϕkdkand r^k by (6). If r^k≤0, go to Step  5. Else go to Step  6.
Step  5. Choose some L-function and compute Δk+1=L(r^k)Δk, and then go to Step 3.
Step  6. Set xk+1=xk+dk. Update the trust region radius (10)Δk+1=Lr^kΔk.Step  7. Compute gk+1 and Bk+1; choose ζk+1∈[ζmin,ζmax], set k:=k+1, and go to Step 2.


## 3. Convergence of Algorithm2

In the section, we consider the convergence properties of Algorithm2. We give the following assumption.Assumption 3.
(i) The functionf is bounded on the level set S={x∣f(x)≤f(x0)} and twice continuously differentiable. (ii) The sequence {Bk} is uniformly bounded in norm; that is, for some constant M, Bk≤M. (iii) The solution dk of subproblem (2) satisfies(11)qk0-qkdk≥σgkmin⁡Δk,gkBk,where σ∈(0,1].Lemma 4.
Suppose that (i) and (ii) in Assumption3 hold. Then(12)fxk+dk-qdk≤12Mdk2+Cdkdk,where Cdk arbitrarily decreases with dk decreasing.Proof.
Since, from Taylor theorem, we have(13)fxk+dk=fxk+gkTdk+∫01∇fxk+tdk-gxkTdkdt,it follows from the definition of qk(d) in (2) that(14)fxk+dk-qkdk=12dkTBkdk-∫01∇fxk+tdk-gxkTdkdt≤12Mdk2+Cdkdk,where Cdk arbitrarily decreases with dk decreasing.Lemma 5.
Assume that the sequence{xk} is generated by Algorithm 2. Then the sequence {xk}⊆S.Proof.
From Lemma3.1 in [22] and x0∈S in Assumption 3 (i), we have {xk}⊆S.The next lemma shows that the loop through Step3 to Step 5 cannot cycle infinitely and the sequence {xk} is well defined.Lemma 6.
Suppose that Assumption3 holds. Assume also gk≠0, and there exists a sufficiently small constant Δ¯>0 such that(15)Δk≤Δ¯.Then(16)Δk+1≥Δkholds.Proof.
By Assumption3 and gk≠0, there exist ɛ>0 and a positive index k0 such that(17)gk≥ɛ,∀k≥k0.
Combining (11), we have that, for k≥k0,(18)qk0-qkdk≥σgkmin⁡Δk,gkBk≥σɛmin⁡Δk,ɛM.Combining (12) and (18), we have(19)rkO-1=fxk+dk-qkdkqk0-qkdk≤1/2Mdk2+Cdkdkσɛmin⁡Δk,ɛ/M≤ΔkMΔk+2Cdkσɛmin⁡Δk,ɛ/M.By (15), we can choose sufficiently small Δ¯ such that (20)Δk≤Δ¯≤ɛM,MΔk+2Cdk≤1-η2σɛ,and furthermore, for sufficiently large k≥k0, (21)rkO-1≤1-η2.
For the abovek, we know that(22)rk+jO-1≤1-η2,j=1,2,…,m.
From (6) and (22), for sufficiently large k≥k0+m, we know that r^k formulate always the form(23)r^k-1=∑i=0mωkirk-iO-∑i=0mωki≤∑i=0mωkirk-iO-1≤∑i=0mωki1-η2≤1-η2.
From (23), for sufficient large k, we have 2-η2≥r^k≥η2. By Algorithm 2 and the definition of L-function, we have Δk+1≥Δk, where Δk falls below Δ¯.We will show the global convergence of Algorithm2.Theorem 7.
Suppose that Assumption3 holds. Let the sequence {xk} be generated by Algorithm 2. Then(24)liminfk→∞⁡gk=0.Proof.
For the purpose of deriving a contradiction, suppose that there exists a positive constantδ>0 such that(25)gk≥δ>0.For convenience, we denote one index set as follows: (26)J=k∣r^k≥η2.
First, assume that the setJ has infinite elements. That is, for any k∈J, r^k≥η2 holds. For any k∈J, using Algorithm 2 and (12), we have that(27)Ck-fxk+1≥η2qk0-qkdk≥ση2gkmin⁡Δk,gkBk≥ση2δmin⁡Δk,δM.
Thus, from (27),(28)fxk+1≤Ck-ση2δmin⁡Δk,δM.From (5) and (28), we have that (29)Ck+1=ζkQkCk+fxk+1Qk+1≤ζkQkCk+Ck-ση2δmin⁡Δk,δ/MQk+1=Ck-ση2δmin⁡Δk,δ/MQk+1.From Lemma 3.1 in [22] and Assumption 3 (i), we know the sequence {Ck} is nonincreasing and convergent. Then (30)limk→∞⁡Δk=0,which contradicts (16). Next, we assume that the set J has finite elements. Then, for sufficient large k, we have that r^k<η2. From the definition of L-function and Steps 5 and 6 in Algorithm 2, we have that the trust region Δk is decreasing as the iteration process. Furthermore, the limit (31)limk→∞⁡Δk=0holds, which gives a contradiction to (16). The proof is completed.


## 4. Numerical Experiments

In this section, we present preliminary numerical results to illustrate the performance of Algorithm2, denoted by NTRW. In Algorithm 2, we choose(32)Lrk=c1+c2-c1exp⁡rk,ifrk≤0,1-β1exp⁡η21-exp⁡η2-1-β1exp⁡η21-exp⁡η2exp⁡rk-η2,if0<rk<η2,β2,ifη2≤rk≤2-η2,β3+β2-β3exp⁡-rk+η2-2η2-22,ifrk>2-η2,where β1=0.5,β2=2,β3=0.7,c1=0.12,c2=0.14, andη2=0.75. In the framework of Algorithm 2, we compare NTRW with the following algorithms: the basic trust region method, denoted by BTR; the basic trust region method with Grippo’s nonmonotone technique, denoted by NTR1, m=3; the basic trust region method with Hager’s nonmonotone technique, denoted by NTR2, ζ=0.5. All tests are implemented by using Matlab R2008a on a PC with CPU 2.40 GHz and 2.00 GB RAM. The test problem collections for unconstrained minimization in Table 1 are taken from Moré et al. in [23], the CUTEr collection [24, 25].Table 1
Test problems.
Number
Problem name
1
Helical valley function
2
Biggs EXP6 function
3
Gaussian function
4
Box function
5
Variable dimension function
6
Watson function
7
Penalty function I
8
Penalty function II
9
Brown badly scaled function
10
Brown and Dennis function
11
Gulf function
12
Extended Rosenbrock function
13
Beale function
14
Wood function
15
Chebyquad function
16
Boundary value function
17
Separable cubic function
18
Powell singular function
19
Linear function, full rank
20
Linear function, rank 1
21
FLETCHCR function
22
BDQRTIC function
23
TRIDIA function
24
ARGLINB function
25
ARWHEAD function
26
NONDIA function
27
NONDQUAR function
28
Generalized Rosenbrock function
29
Broyden tridiagonal function
30
Allgower function
31
EG2 function
32
CURLY20 function
33
LIARWHD function
34
POWER function
35
ENGVAL1 function
36
ARGLINC function
37
NONSCOMP function
38
VARDIM function
39
QUARTC function
40
Extended DENSCHNB function
41
Extended DENSCHNF function
42
DIXON3DQ function
43
BiGGSB1 function
44
Nearly separable function
45
Schittkowski function 302
46
Discrete integral equation function
47
DQDRTIC function
48
EDENSCH function
49
Bdexp function
50
COSINE function
51
HIMMELBG functionIn all algorithms in this paper, the matrixBk is updated by BFGS formula [26, 27]. The trial step dk, for small-scale problems, is computed by trust m file in Optimization Toolbox of Matlab, for middle-scale and large-scale problems, and is computed by CG-Steihaug algorithm in [26]. The iteration is terminated by the following condition: (33)gk≤ɛ,where ɛ=10-5. In Tables 1, 2, 3, and 4, we give the dimension (Dim) of each test problem (P), the number iter of iterations, the number nf of function evaluations, and the CPU (cpu) time for solving the test problem.Table 2
Numerical comparisons for some small-scale test problems.
P/Dim
BTR
NTR1
NTR2
NTRW
iter/nf
iter/nf
iter/nf
iter/nf
1
/
3
32
/
43
31
/
51
30
/
51
38
/
45
2
/
6
38
/
45
37
/
42
36
/
41
40
/
41
3
/
3
3
/
4
3
/
4
3
/
4
3
/
4
4
/
3
33
/
47
33
/
46
33
/
46
38
/
41
5
/
5
21
/
30
11
/
28
11
/
28
14
/
19
6
/
5
23
/
31
23
/
32
24
/
35
24
/
27
7
/
5
188
/
240
19
/
36
19
/
36
65
/
76
8
/
5
18
/
26
18
/
26
18
/
26
8
/
11
9
/
2
69
/
124
∗
∗
∗
∗
105
/
117
10
/
4
72
/
92
219
/
349
184
/
261
44
/
57
11
/
3
9
/
10
9
/
10
9
/
10
9
/
10
12
/
6
41
/
62
44
/
76
44
/
72
51
/
58
13
/
2
12
/
15
17
/
20
17
/
20
15
/
17
14
/
4
34
/
50
140
/
254
/
140
/
188
104
/
125
15
/
5
8
/
10
8
/
10
8
/
10
9
/
11
16
/
10
23
/
27
23
/
34
23
/
28
20
/
22
17
/
10
8
/
9
8
/
9
8
/
9
8
/
9
18
/
4
32
/
44
26
/
36
33
/
43
27
/
31
19
/
10
3
/
4
3
/
4
3
/
4
3
/
4
20
/
10
7
/
20
14
/
48
14
/
48
3
/
8
21
/
10
38
/
58
43
/
94
44
/
98
49
/
62
22
/
10
35
/
48
35
/
79
35
/
80
39
/
50
23
/
10
33
/
44
32
/
64
32
/
57
52
/
64
24
/
10
∗
∗
∗
∗
∗
∗
∗
∗
25
/
10
9
/
13
9
/
14
9
/
14
11
/
15
26
/
10
43
/
80
24
/
58
24
/
58
76
/
93
27
/
10
98
/
102
98
/
105
98
/
105
85
/
93
28
/
20
110
/
150
107
/
203
102
/
182
119
/
147
29
/
20
30
/
56
30
/
82
30
/
82
57
/
72
30
/
20
65
/
93
69
/
138
75
/
127
64
/
86
31
/
20
22
/
24
22
/
24
24
/
26
23
/
25
32
/
20
∗
∗
64
/
145
63
/
131
65
/
81
33
/
20
30
/
58
30
/
72
30
/
72
40
/
51
34
/
20
74
/
107
77
/
157
77
/
145
92
/
115
35
/
20
28
/
55
26
/
77
25
/
70
42
/
50
36
/
30
∗
∗
∗
∗
∗
∗
∗
∗
37
/
30
346
/
475
388
/
580
334
/
455
258
/
321
38
/
30
∗
∗
∗
∗
∗
∗
60
/
70
39
/
30
17
/
18
17
/
18
17
/
18
19
/
20
40
/
30
8
/
9
8
/
9
8
/
9
8
/
9
41
/
30
37
/
76
38
/
100
38
/
100
47
/
57
42
/
30
37
/
64
34
/
68
36
/
69
53
/
63
43
/
30
36
/
59
37
/
73
38
/
79
52
/
62
∗
∗ means that the algorithm reaches 500 iterations.Table 3
Numerical comparisons for some middle-scale test problems.
P/Dim
BTR
NTR1
NTR2
NTRW
iter/nf/cpu
iter/nf/cpu
iter/nf/cpu
iter/nf/cpu
5
/
500
45
/
114
/
0.64
160
/
534
/
1.47
369
/
1192
/
3.01
73
/
92
/
2.85
7
/
500
113
/
228
/
4.35
123
/
361
/
2.79
259
/
700
/
5.57
86
/
99
/
3.99
16
/
500
6
/
11
/
0.33
16
/
36
/
0.78
9
/
23
/
0.44
7
/
8
/
0.19
17
/
500
8
/
10
/
0.64
8
/
10
/
0.69
8
/
10
/
0.75
9
/
11
/
0.78
22
/
500
∗
∗
227
/
500
/
15.60
251
/
450
/
16.05
∗
∗
23
/
500
4407
/
7001
/
211.49
4205
/
11668
/
253.84
4179
/
8214
/
213.60
∗
∗
25
/
500
16
/
31
/
0.56
11
/
28
/
0.42
11
/
28
/
0.36
28
/
35
/
1.09
26
/
500
21
/
40
/
0.70
308
/
552
/
2.26
196
/
310
/
1.84
10
/
15
/
0.37
29
/
500
149
/
236
/
7.43
153
/
471
/
9.64
153
/
358
/
7.63
109
/
142
/
4.73
31
/
500
13
/
24
/
0.55
15
/
30
/
0.62
20
/
41
/
0.75
50
/
55
/
2.04
33
/
500
26
/
38
/
1.11
24
/
56
/
0.86
31
/
80
/
1.05
33
/
43
/
1.37
35
/
500
42
/
96
/
2.53
43
/
144
/
2.84
37
/
134
/
2.67
56
/
66
/
3.32
37
/
500
∗
∗
66
/
224
/
4.60
71
/
227
/
4.74
54
/
65
/
3.10
38
/
500
62
/
135
/
1.31
202
/
666
/
2.64
354
/
1182
/
3.14
73
/
92
/
3.03
39
/
500
14
/
18
/
0.83
14
/
18
/
0.75
14
/
18
/
0.70
12
/
14
/
0.58
40
/
500
8
/
13
/
0.48
11
/
16
/
0.56
11
/
16
/
0.70
7
/
9
/
0.31
41
/
500
∗
∗
∗
∗
37
/
183
/
0.39
27
/
33
/
1.20
44
/
500
∗
∗
116
/
280
/
8.85
2686
/
3879
/
248.02
50
/
62
/
4.62
45
/
500
49
/
108
/
0.90
134
/
457
/
1.29
257
/
852
/
1.98
80
/
96
/
2.28
46
/
500
76
/
208
/
59.83
140
/
486
/
85.19
∗
∗
∗
∗
47
/
500
67
/
116
/
3.85
∗
∗
84
/
224
/
3.40
137
/
162
/
7.36
48
/
500
35
/
80
/
1.67
33
/
131
/
2.15
33
/
112
/
1.83
∗
∗
49
/
500
18
/
19
/
1.00
18
/
19
/
1.05
18
/
19
/
1.00
24
/
25
/
1.48
50
/
500
90
/
154
/
5.80
42
/
127
/
3.56
88
/
204
/
6.33
63
/
71
/
3.74
51
/
500
7
/
8
/
0.45
7
/
8
/
0.39
7
/
8
/
0.33
28
/
29
/
1.50
∗
∗ means that the algorithm reaches 5000 iterations.Table 4
Numerical comparisons for some large-scale test problems.
P/Dim
BTR
NTR1
NTR2
NTRW
iter/nf/cpu
iter/nf/cpu
iter/nf/cpu
iter/nf/cpu
2
6
/
1000
37
/
54
/
3.74
603
/
1072
/
9.20
220
/
358
/
4.44
221
/
260
/
39.12
26
/
3000
56
/
75
/
44.42
1787
/
3148
/
174.64
642
/
929
/
75.06
491
/
582
/
431.90
29
/
1000
10
/
12
/
3.60
10
/
12
/
3.04
10
/
12
/
3.16
8
/
10
/
2.26
29
/
3000
10
/
13
/
14.18
10
/
13
/
14.35
10
/
13
/
14.07
7
/
9
/
9.76
33
/
1000
20
/
35
/
1.99
27
/
65
/
2.91
99
/
199
/
4.66
24
/
30
/
2.87
33
/
3000
56
/
115
/
46.00
36
/
86
/
16.34
26
/
59
/
12.38
80
/
95
/
83.33
33
/
5000
25
/
40
/
45.81
29
/
70
/
27.12
39
/
87
/
45.13
38
/
50
/
81.99
37
/
1000
55
/
186
/
9.47
55
/
197
/
9.68
55
/
186
/
9.34
57
/
69
/
7.80
37
/
3000
—
—
—
48
/
57
/
35.81
37
/
5000
—
—
—
102
/
123
/
186.96
38
/
1000
95
/
202
/
7.83
1058
/
3335
/
21.27
∗
∗
25
/
47
/
1.76
38
/
3000
—
—
—
19
/
45
/
9.67
39
/
1000
18
/
22
/
3.58
16
/
20
/
2.99
16
/
20
/
4.16
18
/
20
/
2.67
39
/
3000
18
/
23
/
14.00
17
/
22
/
13.63
17
/
22
/
12.13
28
/
31
/
21.29
39
/
5000
18
/
23
/
33.38
16
/
22
/
29.99
16
/
22
/
28.34
28
/
31
/
52.21
40
/
1000
7
/
13
/
2.45
8
/
18
/
2.45
8
/
18
/
2.54
8
/
11
/
2.65
40
/
3000
7
/
15
/
11.04
9
/
21
/
12.18
9
/
21
/
12.64
9
/
12
/
13.85
40
/
5000
7
/
14
/
22.92
796
/
2482
/
436.10
15
/
29
/
27.44
10
/
13
/
30.00
41
/
1000
∗
∗
∗
∗
39
/
196
/
2.39
29
/
38
/
9.73
41
/
3000
—
—
47
/
236
/
12.35
10
/
15
/
9.07
41
/
5000
—
—
49
/
246
/
34.24
22
/
30
/
41.85
44
/
1000
120
/
327
/
32.46
—
120
/
327
/
22.86
91
/
113
/
34.32
44
/
3000
—
—
112
/
472
/
66.40
80
/
98
/
111.91
44
/
5000
—
—
—
79
/
95
/
224.81
50
/
1000
44
/
89
/
17.55
48
/
143
/
22.74
61
/
158
/
26.38
65
/
73
/
26.05
50
/
3000
36
/
77
/
36.08
—
—
78
/
87
/
57.06
50
/
5000
161
/
250
/
341.79
—
—
58
/
66
/
108.62
— means that the algorithm does not end in 30 minutes;∗∗ means that the algorithm reaches 5000 iterations.In Table2, we compare 43 small-scale problems for the four algorithms, and the results are concluded as follows:(i)
19 problems where NTRW was superior to BTR,(ii)
11 problems where BTR was superior to NTRW,(iii)
13 problems where NTR2 was superior to NTR1,(iv)
5 problems where NTR1 was superior to NTR2,(v)
25 problems where NTRW was superior to NTR2,(vi)
10 problems where NTR2 was superior to NTRW. For problems 12, 18, 24, 30, and 36 especially, the iterations of four algorithms are similar while nf of NTRW are much less than the others. It means that the number of subproblem evaluations of NTRW is much less than the others. Therefore, our self-adaptive technique is efficient. For problems 10, 20, 27, 32, and 38, NTRW is superior to the others clearly. And cpu of NTRW is less than the others. So the performance of our algorithm is better than the others.In Table3, we compare 25 middle-scale problems of the four algorithms. There are 12 problems that show NTRW is much superior than the others, 7 problems that show the performance of the four algorithms is similar, and only 4 problems that show NTRW is bad.In Table4, we compare 10 large-scale problems of the four algorithms. There are 5 problems that show NTRW is much superior than the others, 4 problems that show the performance of the four algorithms is similar, and only 1 problem that shows NTRW is bad. Note that, for problems 33 and 35, the iteration of our algorithm is similar to NTR2, while the CPU time is much more than NTR2. Exponential function called in Matlab environment maybe consume more time, which is contained in L-function in (32).Further result is shown in Figures1 and 2, which is characterized by means of performance profile proposed in [28]. The performance ratio q(τ) is the probability for solver s for the test problems, where a log-scale ratio is not greater than the factor τ. More details are founded in [28]. As we can see from Figures 1 and 2, NTRW is obviously superior than NTR1 and NTR2 in the number of iterations and function evaluations. NTRW is superior than the other three algorithms in the number of function evaluations.Figure 1
Performance profile comparing the number of iterations.Figure 2
Performance profile comparing the number of function evaluations.


## 5. Conclusion

This paper presents a nonmonotone weighting self-adaptive trust region algorithm for unconstrained nonconvex optimization. The new algorithm is very simple and easily implemented. The convergence properties of the method are established under reasonable assumptions. Numerical experiments show that the new algorithm is quite robust and effective, and the numerical performance is comparable to or better than that of other trust region algorithms in the same frame.



---

*Source: 825839-2015-11-17.xml*