# A Limited Memory BFGS Method for Solving Large-Scale Symmetric Nonlinear Equations

Authors: Xiangrong Li; Xiaoliang Wang; Xiabin Duan
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

A limited memory BFGS (L-BFGS) algorithm is presented for solving large-scale symmetric nonlinear equations, where a line search technique without derivative information is used. The global convergence of the proposed algorithm is established under some suitable conditions. Numerical results show that the given method is competitive to those of the normal BFGS methods.


---

## Body

## 1. Introduction

Consider(1)
h
(
x
)
=
0
,
x
∈
R
n
,
where h
:
R
n
→
R
n is continuously differentiable, the Jacobian ∇
h
(
x
) of g is symmetric for all x
∈
R
n, and n denotes the large-scale dimensions. It is not difficult to see that if g is the gradient mapping of some function f
:
R
n
→
R, problem (1) is the first order necessary condition for the problem min
⁡
x
∈
R
n
f
(
x
). Furthermore, considering
(2)
min
⁡
f
(
u
)
s
.
t
.
a
(
u
)
=
0
,
where a is a vector-valued function, then the KKT conditions can be represented as the system (1) with x
=
(
u
,
v
) and h
(
u
,
v
)
=
(
∇
f
(
u
)
+
∇
a
(
u
)
v
,
a
(
u
)
), where v is the vector of Lagrange multipliers. The above two cases show that problem (1) can come from an unconstrained problem or an equality constrained optimization problem in theory. Moreover, there are other practical problems that can also take the form of (1), such as the discretized two-point boundary value problem, the saddle point problem, and the discretized elliptic boundary value problem (see Chapter 1 of [1] in detail). Let θ be the norm function θ
(
x
)
=
(
1
/
2
)
∥
h
(
x
)
∥
2; then problem (1) is equivalent to the following global optimization problem:
(3)
min
⁡
θ
(
x
)
x
∈
R
n
,
where ∥
·
∥ is the Euclidean norm.In this paper we will focus on the line search method for (1), where its normal iterative formula is defined by
(4)
x
k
+
1
=
x
k
+
α
k
d
k
,
where d
k is the so-called search direction and α
k is a steplength along d
k. To begin with, we briefly review some methods for α
k.(i) Normal Line Search (Brown and Saad [2]). The stepsize α
k is determined by
(5)
θ
(
x
k
+
α
k
d
k
)
-
θ
(
x
k
)
≤
σ
α
k
∇
θ
(
x
k
)
T
d
k
,
where σ
∈
(
0,1
) and ∇
θ
(
x
k
)
=
∇
h
(
x
k
)
h
(
x
k
). The convergence is proved and some good results are obtained. We all know that the nonmonotone idea is more interesting than the normal technique in many cases. Then a nonmonotone line search technique based on this motivation is presented by Zhu [3].(ii) Nonmonotone Line Search (Zhu [3]). The stepsize α
k is determined by
(6)
θ
(
x
k
+
α
k
d
k
)
-
θ
(
x
l
(
k
)
)
≤
σ
α
k
∇
θ
(
x
k
)
T
d
k
,
θ
(
x
l
(
k
)
)
=
max
⁡
0
≤
j
≤
m
(
k
)
{
θ
(
x
k
-
j
)
}, m
(
0
)
=
0, m
(
k
)
=
min
⁡
{
m
(
k
-
1
)
+
1
,
M
} (for k
≥
1
), and M is a nonnegative integer. The global convergence and the superlinear convergence are established under mild conditions, respectively. It is not difficult to see that, for the above two line search techniques, the Jacobian matrix ∇
h
k must be computed at each iteration, which obviously increase the workload and the CPU time consumed. In order to avoid this drawback, Yuan and Lu [4] presented a new backtracking inexact technique.(iii) A New Line Search (Yuan and Lu [4]). The stepsize α
k is determined by
(7)
∥
h
(
x
k
+
α
k
d
k
)
∥
2
≤
∥
h
(
x
k
)
∥
2
+
δ
α
k
2
h
k
T
d
k
,
where δ
∈
(
0,1
) and h
k
=
h
(
x
k
). They established the global convergence and the superlinear convergence. And the numerical tests showed that the new line search technique is more effective than those of the normal line search technique. However, these three line search techniques can not directly ensure the descent property of d
k. Thus more interesting line search techniques are studied.(iv) Approximate Monotone Line Search (Li and Fukushima [5]). The stepsize α
k is determined by
(8)
θ
(
x
k
+
α
k
d
k
)
-
θ
(
x
k
)
≤
-
δ
1
∥
α
k
d
k
∥
2
-
δ
2
∥
α
k
h
k
∥
2
+
ϵ
k
∥
h
k
∥
2
,
where α
k
=
r
i
k, r
∈
(
0,1
), i
k is the smallest nonnegative integer i satisfying (8), δ
1
>
0 and δ
2
>
0 are constants, and ϵ
k is such that
(9)
∑
k
=
0
∞
ϵ
k
<
∞
.
The line search (8) can be rewritten as
(10)
∥
h
(
x
k
+
α
d
k
)
∥
2
≤
(
1
+
ϵ
k
)
∥
h
k
∥
2
-
δ
1
∥
α
h
k
∥
2
-
δ
2
∥
α
d
k
∥
2
;
it is straightforward to see that as α
→
0, the right-hand side of the above inequality goes to (
1
+
ϵ
k
)
∥
h
k
∥
2. Then it is not difficult to see that the sequence {
x
k
} generated by one algorithm with line search (8) is approximately norm descent. In order to ensure the sequence {
x
k
} is norm descent, Gu et al. [6] presented the following line search.(v) Monotone Descent Line Search (Gu et al. [6]). The stepsize α
k is determined by
(11)
∥
h
(
x
k
+
α
k
d
k
)
∥
2
-
∥
h
k
∥
2
≤
-
δ
1
∥
α
k
h
k
∥
2
-
δ
2
∥
α
k
d
k
∥
2
,
where α
k, δ
1, and δ
2 are similar to (8).In the following, we present some techniques ford
k.(i) Newton Method. The search direction d
k is defined by
(12)
∇
h
(
x
k
)
d
k
=
-
h
(
x
k
)
.
Newton method is one of the most effective methods since it normally requires a fewest number of function evaluations and is very good at handling ill-conditioning. However, its efficiency largely depends on the possibility to efficiently solve a linear system (12) which arises when computing. Moreover, the exact solution of the system (12) could be too burdensome or is not necessary when x
k is far from a solution [7]. Thus the quasi-Newton methods are proposed.(ii) Quasi-Newton Method. The search direction d
k is defined by
(13)
B
k
d
k
+
h
k
=
0
,
where B
k is the quasi-Newton update matrix. The quasi-Newton methods represent the basic approach underlying most of the Newton-type large-scale algorithms (see [3, 4, 8], etc.), where the famous BFGS method is one of the most effective quasi-Newton methods, generated by the following formula:
(14)
B
k
+
1
=
B
k
-
B
k
s
k
s
k
T
B
k
s
k
T
B
k
s
k
+
y
k
y
k
T
y
k
T
s
k
,
where s
k
=
x
k
+
1
-
x
k and y
k
=
h
k
+
1
-
h
k with h
k
=
h
(
x
k
) and h
k
+
1
=
h
(
x
k
+
α
k
d
k
). By (11) and (14), Yuan and Yao [9] proposed a BFGS method for nonlinear equations and some good results were obtained. Denote H
k
=
B
k
-
1, and then (14) has the inverse update formula represented by
(15)
H
k
+
1
=
H
k
-
y
k
T
(
s
k
-
H
k
y
k
)
s
k
s
k
T
(
y
k
T
s
k
)
2
V
+
(
s
k
-
H
k
y
k
)
s
k
T
+
s
k
(
s
k
-
H
k
y
k
)
T
(
y
k
T
s
k
)
2
=
(
I
-
s
k
y
k
T
y
k
T
s
k
)
H
k
(
I
-
y
k
s
k
T
y
k
T
s
k
)
+
s
k
s
k
T
y
k
T
s
k
.
Unfortunately, both the Newton method and the quasi-Newton method require many space to store n
×
n matrix at every iteration, which will prevent the efficiency of the algorithm for problems, especially for large-scale problems. Therefore low storage matrix information method should be necessary.(iii) Limited Memory Quasi-Newton Method. The search direction d
k is defined by
(16)
d
k
=
-
H
k
h
k
,
where H
k is generated by limited memory quasi-Newton method, where the famous limited memory quasi-Newton method is the so-called limited memory BFGS method. The L-BFGS method is an adaptation of the BFGS method for large-scale problems (see [10] in detail), which often requires minimal storage and provides a fast rate of linear convergence. The L-BFGS method has the following form:
(17)
H
k
+
1
=
V
k
T
H
k
V
k
+
ρ
k
s
k
s
k
T
=
V
k
T
[
V
k
-
1
T
H
k
-
1
V
k
-
1
+
ρ
k
-
1
s
k
-
1
s
k
-
1
T
]
V
k
+
ρ
k
s
k
s
k
T
=
⋯
=
[
V
k
T
⋯
V
k
-
m
~
+
1
T
]
H
k
-
m
~
+
1
[
V
k
-
m
~
+
1
⋯
V
k
]
V
+
ρ
k
-
m
~
+
1
[
V
k
-
1
T
⋯
V
k
-
m
~
+
2
T
]
V
×
s
k
-
m
~
+
1
s
k
-
m
~
+
1
T
[
V
k
-
m
~
+
2
⋯
V
k
-
1
]
+
⋯
+
ρ
k
s
k
s
k
T
,
where ρ
k
=
1
/
s
k
T
y
k, V
k
=
I
-
ρ
k
y
k
s
k
T, m
~
>
0 is an integer, and I is the unit matrix. Formula (17) shows that matrix H
k is obtained by updating the basic matrix H
0
m
~ times using BFGS formula with the previous m
~ iterations. By (17), together with (7) and (8), Yuan et al. [11] presented the L-BFGS method for nonlinear equations and got the global convergence. At present, there are many papers proposed for (1) (see [6, 12–15], etc.).In order to effectively solve large-scale nonlinear equations and possess good theory property, based on the above discussions ofα
k and d
k, we will combine (11) and (16) and present a L-BFGS method for (1) since (11) can make the norm function be descent and (16) need less low storage. The main attributes of the new algorithm are stated as follows.(i)
A L-BFGS method with (11) is presented.
(ii)
The norm function is descent.
(iii)
The global convergence is established under appropriate conditions.
(iv)
Numerical results show that the given algorithm is more competitive than the normal algorithm for large-scale nonlinear equations.This paper is organized as follows. In the next section, the backtracking inexact L-BFGS algorithm is stated. Section3 will present the global convergence of the algorithm under some reasonable conditions. Numerical experiments are done to test the performance of the algorithms in Section 4.


## 2. Algorithms

This section will state the L-BFGS method in association with the new backtracking line search technique (11) for solving (1).Algorithm 1.
Step  0.Choose an initial point x
0
∈
R
n, an initial symmetric positive definite matrix H
0
∈
R
n
×
n, positive constants δ
1, δ
2, constants r
,
ρ
∈
(
0,1
), and a positive integer m
1. Let k
:
=
0.
Step  1.Stop if ∥
h
k
∥
=
0.
Step  2.Determine d
k by (16).
Step  3.If
(18)
∥
h
(
x
k
+
d
k
)
∥
≤
ρ
∥
h
(
x
k
)
∥
,
then take α
k
=
1 and go to Step  5. Otherwise go to Step  4.
Step  4.Let i
k be the smallest nonnegative integer i such that (11) holds for α
=
r
i. Let α
k
=
r
i
k.
Step  5.Let the next iterative be x
k
+
1
=
x
k
+
α
k
d
k.
Step  6.Let m
~
=
min
⁡
{
k
+
1
,
m
1
}. Put s
k
=
x
k
+
1
-
x
k
=
α
k
d
k and y
k
=
h
k
+
1
-
h
k. Update H
0 for m
~ times to get H
k
+
1 by (17).
Step  7.Let k
:
=
k
+
1. Go to Step  1.In the following, to conveniently analyze the global convergence, we assume that the algorithm updatesB
k (the inverse of H
k) with the basically bounded and positive definite matrix B
0   (H
0’s inverse). Then Algorithm 1 with B
k has the following steps.Algorithm 2.
Step  2.Determine d
k by
(19)
B
k
d
k
=
-
h
k
.Step  6.Let m
~
=
min
⁡
{
k
+
1
,
m
1
}. Put s
k
=
x
k
+
1
-
x
k
=
α
k
d
k and y
k
=
h
k
+
1
-
h
k. Update B
0 for m
~ times; that is, for l
=
k
-
m
~
+
1
,
…
,
k compute
(20)
B
k
l
+
1
=
B
k
l
-
B
k
l
s
l
s
l
T
B
k
l
s
l
T
B
k
l
s
l
+
y
l
y
l
T
y
l
T
s
l
,
where s
l
=
x
l
+
1
-
x
l
,
y
l
=
h
l
+
1
-
h
l, and B
k
k
-
m
~
+
1
=
B
0 for all k.Remark 3.
Algorithms1 and 2 are mathematically equivalent. Throughout this paper, Algorithm 2 is given only for the purpose of analysis, so we only discuss Algorithm 2 in theory. In the experiments, we implement Algorithm 1.


## 3. Global Convergence

Define the level setΩ by
(21)
Ω
=
{
x
∣
∥
h
(
x
)
∥
≤
∥
h
(
x
0
)
∥
}
.
In order to establish the global convergence of Algorithm 2, similar to [4, 11], we need the following assumptions.Assumption A.
g is continuously differentiable on an open convex set Ω
1 containing Ω. Moreover the Jacobian of g is symmetric, bounded, and positive definite on Ω
1; namely, there exist positive constants M
≥
m
>
0 satisfying
(22)
∥
∇
h
(
x
)
∥
≤
M
∀
x
∈
Ω
1
,
m
∥
d
∥
2
≤
d
T
∇
h
(
x
)
d
∀
x
∈
Ω
1
,
d
∈
R
n
.Assumption B.
B
k is a good approximation to ∇
g
k; that is,
(23)
∥
(
∇
h
k
-
B
k
)
d
k
∥
≤
ϵ
∥
h
k
∥
,
where ϵ
∈
(
0,1
) is a small quantity.Remark 4.
Assumption A implies(24)
∥
y
k
∥
≤
M
∥
s
k
∥
,
y
k
T
s
k
≥
m
∥
s
k
∥
2
.The relations in (24) can ensure that B
k
+
1 generated by (20) inherits symmetric and positive definiteness of B
k. Thus, (19) has a unique solution for each k. Moreover, the following lemma holds.Lemma 5 (see Theorem  2.1 in [16] or see Lemma 3.4 of [11]).
Let AssumptionA hold and let {
α
k
,
d
k
,
x
k
+
1
,
g
k
+
1
} be generated by Algorithm 2. Then, for any r
0
∈
(
0,1
) and k
≥
0, there are positive constants β
j, j
=
1,2
,
3; the following relations
(25)
β
2
∥
s
i
∥
2
≤
s
i
T
B
i
s
i
≤
β
3
∥
s
i
∥
2
,
∥
B
i
s
i
∥
≤
β
1
∥
s
i
∥
hold for at least ⌈
r
0
k
⌉ values of i
∈
[
0
,
k
].By Assumption B, similar to [4, 9, 11, 15], it is easy to get the following lemma.Lemma 6.
Let AssumptionB hold and let {
α
k
,
d
k
,
x
k
+
1
,
h
k
+
1
} be generated by Algorithm 2. Then d
k is a descent direction for θ
(
x
) at x
k; that is, ∇
θ
(
x
k
)
T
d
k
<
0 holds.Based on the above lemma, by Assumption B, similar to Lemma  3.8 in [2], we can get the following lemma.Lemma 7.
Let Assumption B hold and let{
α
k
,
d
k
,
x
k
+
1
,
h
k
+
1
} be generated by Algorithm 2. Then {
x
k
}
⊂
Ω. Moreover, {
∥
h
k
∥
} converges.Lemma 8.
Let AssumptionsA andB hold. Then, in a finite number of backtracking steps, Algorithm 2 will produce an iterate x
k
+
1
=
x
k
+
α
k
d
k.Proof.
It is sufficient for us to prove that the line search (11) is reasonable. By Lemma  3.8 in [2], we can deduce that, in a finite number of backtracking steps, α
k is such that
(26)
∥
h
(
x
k
+
α
k
d
k
)
∥
2
-
∥
h
(
x
k
)
∥
2
≤
δ
α
k
h
(
x
k
)
T
∇
h
(
x
k
)
d
k
,
δ
∈
(
0,1
)
.
By (19), we get
(27)
∇
θ
(
x
k
)
T
d
k
=
h
(
x
k
)
T
∇
h
(
x
k
)
d
k
=
h
(
x
k
)
T
[
(
∇
h
(
x
k
)
-
B
k
)
d
k
-
h
(
x
k
)
]
=
h
(
x
k
)
T
(
∇
h
(
x
k
)
-
B
k
)
d
k
-
h
(
x
k
)
T
h
(
x
k
)
.
Thus
(28)
∇
θ
(
x
k
)
T
d
k
+
∥
h
k
∥
2
≤
h
(
x
k
)
T
(
∇
h
(
x
k
)
-
B
k
)
d
k
≤
∥
h
(
x
k
)
∥
∥
(
∇
h
(
x
k
)
-
B
k
)
d
k
∥
.
By Assumption B, we have
(29)
∇
θ
(
x
k
)
T
d
k
≤
∥
h
(
x
k
)
∥
∥
(
∇
h
(
x
k
)
-
B
k
)
d
k
∥
-
∥
h
(
x
k
)
∥
2
≤
-
(
1
-
ϵ
)
∥
h
(
x
k
)
∥
2
.
Using (19) again and α
k
≤
1, we obtain
(30)
α
k
h
(
x
k
)
T
∇
h
(
x
k
)
d
k
≤
-
α
k
(
1
-
ϵ
)
∥
h
(
x
k
)
∥
2
=
-
(
1
-
ϵ
)
2
α
k
∥
α
k
h
k
∥
2
-
(
1
-
ϵ
)
2
α
k
∥
α
k
B
k
d
k
∥
2
≤
-
(
1
-
ϵ
)
2
∥
α
k
h
k
∥
2
-
β
2
2
(
1
-
ϵ
)
2
∥
α
k
d
k
∥
2
.
Setting δ
1
∈
(
0
,
δ
(
(
1
-
ϵ
)
/
2
)
) and δ
2
∈
(
0
,
δ
(
β
2
2
(
1
-
ϵ
)
/
2
)
) implies (11). This completes the proof.Remark 9.
The above lemma shows that Algorithm2 is well defined. By a way similar to Lemma 3.2 and Corollary  3.4 in [5], it is not difficult to deduce that
(31)
α
k
≥
β
2
r
β
1
2
σ
1
+
σ
2
+
M
2
holds; we do not prove it anymore. Now we establish the global convergence theorem.Theorem 10.
Let Assumptions A and B hold. Then the sequence{
x
k
} generated by Algorithm 2 converges to the unique solution x
* of (1).Proof.
Lemma7 implies that {
∥
h
k
∥
} converges. If
(32)
lim
⁡
k
→
∞
∥
h
k
∥
=
0
,
then every accumulation point of {
x
k
} is a solution of (1). Assumption A means that (1) has only one solution. Moreover, since Ω is bounded, {
x
k
}
⊆
Ω has at least one accumulation point. Therefore {
x
k
} itself converges to the unique solution of (1). Therefore, it suffices to verify (32).
If (18) holds for infinitely many k’s, then (32) is trivial. Otherwise, if (18) holds for only finitely many k’s, we conclude that Step  3 is executed for all k sufficiently large. By (11), we have
(33)
δ
1
∥
α
k
h
k
∥
2
+
δ
2
∥
s
k
∥
2
≤
∥
h
k
∥
2
-
∥
h
k
+
1
∥
2
.
Since {
∥
h
k
∥
} is bounded, by adding these inequalities, we get
(34)
∑
k
=
0
∞
∥
α
k
h
k
∥
2
<
∞
,
∑
k
=
0
∞
∥
α
k
d
k
∥
2
<
∞
.
Then we have
(35)
lim
⁡
k
→
∞
∥
α
k
h
k
∥
=
0
,
which together with (31) implies (32). This completes the proof.


## 4. Numerical Results

This section reports numerical results with Algorithm1 and normal BFGS algorithm. The test problems with the associated initial guess x
0 are listed with
(36)
h
(
x
)
=
(
f
1
(
x
)
,
f
2
(
x
)
,
…
,
f
n
(
x
)
)
T
.Problem 1.
Exponential function 1:(37)
f
1
(
x
)
=
e
x
1
-
1
-
1
,
f
i
(
x
)
=
i
(
e
x
i
-
1
-
x
i
)
,
i
=
2,3
,
…
,
n
.
Initial guess: x
0
=
(
1
/
n
2
,
1
/
n
2
,
…
,
1
/
n
2
)
T.Problem 2.
Exponential function 2:(38)
f
1
(
x
)
=
e
x
1
-
1
,
f
i
(
x
)
=
i
10
(
e
x
i
+
x
i
-
1
-
i
)
,
i
=
2,3
,
…
,
n
.
Initial guess: x
0
=
(
1
/
n
2
,
1
/
n
2
,
…
,
1
/
n
2
)
T.Problem 3.
Trigonometric function:(39)
f
i
(
x
)
=
2
(
n
+
i
(
1
-
cos
⁡
x
i
)
-
sin
x
i
-
∑
j
=
1
n
cos
⁡
x
j
)
×
(
2
sin
x
i
-
cos
⁡
x
i
)
,
i
=
1,2
,
3
,
…
,
n
.
Initial guess: x
0
=
(
101
/
100
n
,
101
/
100
n
,
…
,
101
/
100
n
)
T.Problem 4.
Singular function:(40)
f
1
(
x
)
=
1
3
x
1
3
+
1
2
x
2
2
,
f
i
(
x
)
=
-
1
2
x
i
2
+
i
3
x
i
3
+
1
2
x
i
+
1
2
,
i
=
2,3
,
…
,
n
-
1
,
f
n
(
x
)
=
-
1
2
x
n
2
+
n
3
x
n
3
.
Initial guess: x
0
=
(
1,1
,
…
,
1
)
T.Problem 5.
Logarithmic function:(41)
f
i
(
x
)
=
ln
⁡
(
x
i
+
1
)
-
x
i
n
,
i
=
1,2
,
3
,
…
,
n
.
Initial guess: x
0
=
(
1,1
,
…
,
1
)
T.Problem 6.
Broyden tridiagonal function [17, pages 471-472]:
(42)
f
1
(
x
)
=
(
3
-
0.5
x
1
)
x
1
-
2
x
2
+
1
,
f
i
(
x
)
=
(
3
-
0.5
x
i
)
x
i
-
x
i
-
1
+
2
x
i
+
1
+
1
,
i
=
2,3
,
…
,
n
-
1
,
f
n
(
x
)
=
(
3
-
0.5
x
n
)
x
n
-
x
n
-
1
+
1
.
Initial guess: x
0
=
(
-
1
,
-
1
,
…
,
-
1
)
T.Problem 7.
Trigexp function [17, page 473]:
(43)
f
1
(
x
)
=
3
x
1
3
+
2
x
2
-
5
+
sin
(
x
1
-
x
2
)
sin
(
x
1
+
x
2
)
,
f
i
(
x
)
=
-
x
i
-
1
e
x
i
-
1
-
x
i
+
x
i
(
4
+
3
x
i
2
)
+
2
x
i
+
1
+
sin
(
x
i
-
x
i
+
1
)
sin
(
x
i
+
x
i
+
1
)
-
8
,
V
V
V
V
V
V
V
V
V
i
=
2,3
,
…
,
n
-
1
,
f
n
(
x
)
=
-
x
n
-
1
e
x
n
-
1
-
x
n
+
4
x
n
-
3
.
Initial guess: x
0
=
(
0,0
,
…
,
0
)
T.Problem 8.
Strictly convex function 1 [18, page 29]: h
(
x
) is the gradient of h
(
x
)
=
∑
i
=
1
n
(
e
x
i
-
x
i
). Consider
(44)
f
i
(
x
)
=
e
x
i
-
1
,
i
=
1,2
,
3
,
…
,
n
.
Initial guess: x
0
=
(
1
/
n
,
2
/
n
,
…
,
1
)
T.Problem 9.
Linear function-full rank:(45)
f
i
(
x
)
=
x
i
-
2
n
∑
j
=
1
n
x
j
+
1
.
Initial guess: x
0
=
(
100,100
,
…
,
100
)
T.Problem 10.
Penalty function:(46)
f
i
(
x
)
=
1
0
-
5
(
x
i
-
1
)
,
i
=
1,2
,
3
,
…
,
n
-
1
,
f
n
(
x
)
=
(
1
4
n
)
∑
j
=
1
n
x
j
2
-
1
4
.
Initial guess: x
0
=
(
1
/
3
,
1
/
3
,
…
,
1
/
3
)
T.Problem 11.
Variable dimensioned function:(47)
f
i
(
x
)
=
x
i
-
1
,
i
=
1,2
,
3
,
…
,
n
-
2
,
f
n
-
1
(
x
)
=
∑
j
=
1
n
-
2
j
(
x
j
-
1
)
,
f
n
(
x
)
=
(
∑
j
=
1
n
-
2
j
(
x
j
-
1
)
)
2
.
Initial guess: x
0
=
(
1
-
(
1
/
n
)
,
1
-
(
2
/
n
)
,
…
,
0
)
T.Problem 12.
Tridiagonal system [19]:
(48)
f
1
(
x
)
=
4
(
x
1
-
x
2
2
)
,
f
i
(
x
)
=
8
x
i
(
x
i
2
-
x
i
-
1
)
-
2
(
1
-
x
i
)
+
4
(
x
i
-
x
i
+
1
2
)
,
i
=
2,3
,
…
,
n
-
1
,
f
n
(
x
)
=
8
x
n
(
x
n
2
-
x
n
-
1
)
-
2
(
1
-
x
n
)
.
Initial guess: x
0
=
(
12,12
,
…
,
12
).Problem 13.
Five-diagonal system [19]:
(49)
f
1
(
x
)
=
4
(
x
1
-
x
2
2
)
+
x
2
-
x
3
2
,
f
2
(
x
)
=
8
x
2
(
x
2
2
-
x
1
)
-
2
(
1
-
x
2
)
+
4
(
x
2
-
x
3
2
)
+
x
3
-
x
4
2
,
f
i
(
x
)
=
8
x
i
(
x
i
2
-
x
i
-
1
)
-
2
(
1
-
x
i
)
+
4
(
x
i
-
x
i
+
1
2
)
+
x
i
-
1
2
-
x
i
-
2
+
x
i
+
1
-
x
i
+
2
2
,
i
=
3,4
,
…
,
n
-
2
,
f
n
-
1
(
x
)
=
8
x
n
-
1
(
x
n
-
1
2
-
x
n
-
2
)
-
2
(
1
-
x
n
-
1
)
+
4
(
x
n
-
1
-
x
n
2
)
+
x
n
-
2
2
-
x
n
-
3
,
f
n
(
x
)
=
8
x
n
(
x
n
2
-
x
n
-
1
)
-
2
(
1
-
x
n
)
+
x
n
-
1
2
-
x
n
-
2
.
Initial guess: x
0
=
(
-
2
,
-
2
,
…
,
-
2
).Problem 14.
Extended Freudentein and Roth function (n is even) [20]: for i
=
1,2
,
…
,
n
/
2
(50)
f
2
i
-
1
(
x
)
=
x
2
i
-
1
+
(
(
5
-
x
2
i
)
x
2
i
-
2
)
x
2
i
-
13
,
f
2
i
(
x
)
=
x
2
i
-
1
+
(
(
1
+
x
2
i
)
x
2
i
-
14
)
x
2
i
-
29
.
Initial guess: x
0
=
(
6,3
,
6,3
,
…
,
6,3
).Problem 15.
Discrete boundry value problem [21]:
(51)
f
1
(
x
)
=
2
x
1
+
0.5
h
2
(
x
1
+
t
)
3
-
x
2
,
f
i
(
x
)
=
2
x
i
+
0.5
h
2
(
x
i
+
t
i
)
3
-
x
i
-
1
+
x
i
+
1
,
i
=
2,3
,
…
,
n
-
1
,
f
n
(
x
)
=
2
x
n
+
0.5
h
2
(
x
n
+
t
n
)
3
-
x
n
-
1
,
t
=
1
n
+
1
.
Initial guess: x
0
=
(
t
(
t
-
1
)
,
t
(
2
t
-
1
)
,
…
,
t
(
n
t
-
1
)
).Problem 16.
Troesch problem [22]:
(52)
f
1
(
x
)
=
2
x
1
+
ϱ
h
2
sin
t
(
ϱ
x
1
)
-
x
2
,
f
i
(
x
)
=
2
x
i
+
ϱ
h
2
sin
t
(
ϱ
x
i
)
-
x
i
-
1
-
x
i
+
1
,
i
=
2,3
,
…
,
n
-
1
,
f
n
(
x
)
=
2
x
n
+
ϱ
h
2
sin
t
(
ϱ
x
n
)
-
x
n
-
1
,
t
=
1
n
+
1
,
ϱ
=
10
.
Initial guess: x
0
=
(
0,0
,
…
,
0
).In the experiments, the parameters in Algorithm1 and the normal BFGS method were chosen as r
=
0.1, ρ
=
0.5, m
1
=
6, δ
1
=
δ
2
=
0.001, H
0 and is the unit matrix. All codes were written in MATLAB r2013b and run on PC with 6600@2.40 GHz Core 2 CPU processor and 4.00 GB memory and Windows 7 operation system. We stopped the program when the condition ∥
h
(
x
)
∥
≤
1
0
-
4 was satisfied. Since the line search cannot always ensure the descent condition d
k
T
h
k
<
0, uphill search direction may occur in the numerical experiments. In this case, the line search rule maybe fails. In order to avoid this case, the stepsize α
k will be accepted if the searching time is larger than eight in the inner circle for the test problems. We also stop this program if the iteration number arrived at 1000. The columns of the tables have the following meaning.Dim: the dimension. NI: the total number of iterations.
NG: the number of the norm function evaluations. Time: the CPU time in second.
GN: the normal value of∥
h
(
x
)
∥ when the program stops.
NaN: not-a-number, impling that the code fails to get a real value.
Inf: returning the IEEE arithmetic representation for positive infinity or infinity which is also produced by operations like dividing by zero.From the numerical results in Table1, it is not difficult to show that the proposed method is more successful than the normal BFGS method. We can see that there exist many problems which can not be successfully solved by the normal BFGS method. Moreover, the normal BFGS method fails to get real value for several problems. Then we can conclude that the presented method is more competitive than the normal BFGS method.Table 1
Nr.
Dim
Algorithm1
Normal BFGS algorithm
NI/NG
GN
Time
NI/NG
GN
Time
Problem1
500
24/25
9.908338e − 05
2.901619e + 01
23/87
NaN
1.950013e + 00
1000
9/10
5.697414e − 05
5.366434e + 01
23/87
NaN
1.124767e + 01
1500
9/10
3.363290e − 05
1.689803e + 02
NI > 1000
Inf
8.094892e + 01
2000
9/10
2.706880e − 05
3.880213e + 02
NI > 1000
Inf
1.550962e + 02
Problem2
500
8/16
3.660478e − 05
6.926444e + 00
60/390
NaN
7.269647e + 00
1000
8/16
6.406401e − 05
4.513109e + 01
40/314
NaN
2.857938e + 01
1500
9/17
7.655321e − 05
1.689959e + 02
33/258
NaN
7.102726e + 01
2000
9/17
9.651851e − 05
3.881617e + 02
29/226
NaN
1.410717e + 02
Problem3
500
18/33
7.747640e − 06
2.110694e + 01
NI > 1000
5.905028e + 04
1.220396e + 02
1000
17/32
8.381440e − 05
1.270472e + 02
NI > 1000
1.577282e + 05
5.830069e + 02
1500
17/32
6.658002e − 05
3.975217e + 02
NI > 1000
2.929920e + 05
1.645561e + 03
2000
17/32
5.689277e − 05
9.154451e + 02
NI > 1000
4.345902e + 05
3.776363e + 03
Problem4
500
809/3134
9.614778e − 05
1.113785e + 03
9/73
NaN
1.107607e + 00
1000
960/3894
9.865549e − 05
8.674373e + 03
8/65
NaN
5.725237e + 00
1500
197/695
8.562547e − 05
5.509394e + 03
8/65
NaN
1.584970e + 01
2000
220/676
9.847745e − 05
1.418851e + 04
8/65
NaN
3.584903e + 01
Problem5
500
6/7
4.925073e − 06
4.305628e + 00
6/7
4.925073e − 06
7.488048e − 01
1000
6/7
6.747222e − 06
2.725337e + 01
6/7
6.747222e − 06
4.477229e + 00
1500
6/7
8.176417e − 06
8.352294e + 01
6/7
8.176417e − 06
1.340049e + 01
2000
6/7
9.391335e − 06
1.925364e + 02
6/7
9.391335e − 06
3.001459e + 01
Problem6
500
96/97
9.183793e − 05
1.272812e + 02
65/66
9.473359e − 05
8.346053e + 00
1000
17/18
7.206980e − 05
1.263140e + 02
63/64
8.700852e − 05
4.623870e + 01
1500
17/18
6.663689e − 05
3.956965e + 02
63/64
9.605270e − 05
1.402917e + 02
2000
17/18
6.136239e − 05
9.107026e + 02
64/65
8.724048e − 05
3.194588e + 02
Problem7
500
14/15
7.551200e − 05
1.533490e + 01
52/53
9.761790e − 05
6.333641e + 00
1000
15/16
5.530847e − 05
1.084051e + 02
55/63
8.871231e − 05
3.985826e + 01
1500
14/15
8.445286e − 05
3.119708e + 02
60/68
7.722045e − 05
1.336617e + 02
2000
15/16
4.705617e − 05
7.805354e + 02
13/63
NaN
5.564556e + 01
Problem8
500
6/7
4.600878e − 05
4.196427e + 00
6/7
2.375490e − 05
7.020045e − 01
1000
6/7
6.434846e − 05
2.658257e + 01
6/7
3.327487e − 05
4.461629e + 00
1500
6/7
7.851881e − 05
8.319533e + 01
6/7
4.062329e − 05
1.335369e + 01
2000
6/7
9.049762e − 05
1.928484e + 02
6/7
4.683284e − 05
2.985859e + 01
Problem9
500
2/10
2.027911e − 10
5.460035e − 01
NI > 1000
4.514037e + 117
1.037407e + 01
1000
2/10
2.666034e − 10
2.698817e + 00
NI > 1000
6.383813e + 117
2.861058e + 01
1500
2/10
1.379742e − 09
8.330453e + 00
NI > 1000
7.818542e + 117
5.319634e + 01
2000
2/10
1.701735e − 09
1.942212e + 01
NI > 1000
9.028075e + 117
8.375694e + 01
Problem10
500
435/2865
5.154286e − 05
5.901362e + 02
41/210
NaN
3.806424e + 00
1000
637/4215
5.701191e − 05
5.749432e + 03
67/425
NaN
3.689424e + 01
1500
303/1914
4.003848e − 05
8.526469e + 03
63/491
NaN
1.146919e + 02
2000
473/3281
3.558910e − 05
3.074095e + 04
64/499
NaN
2.622845e + 02
Problem11
500
1/2
0.000000e + 00
1.092007e − 01
1/2
0.000000e + 00
1.560010e − 01
1000
1/2
0.000000e + 00
7.956051e − 01
1/2
0.000000e + 00
6.864044e − 01
1500
1/2
0.000000e + 00
2.277615e + 00
1/2
0.000000e + 00
2.324415e + 00
2000
1/2
0.000000e + 00
5.101233e + 00
1/2
0.000000e + 00
5.210433e + 00
Problem12
500
260/800
1.654459e − 05
3.509398e + 02
8/51
NaN
7.800050e − 01
1000
324/1053
8.997051e − 05
2.902289e + 03
8/51
NaN
5.226033e + 00
1500
254/829
1.257117e − 05
7.123224e + 03
8/51
NaN
1.583410e + 01
2000
372/1353
9.331122e − 05
2.414117e + 04
8/51
NaN
3.046700e + 01
Problem13
500
96/209
9.194537e − 05
1.287632e + 02
10/74
NaN
1.185608e + 00
1000
53/89
5.718492e − 05
4.531049e + 02
10/74
NaN
6.021639e + 00
1500
NI
>
1000
1.180195e + 10
2.835008e + 04
10/74
NaN
1.790891e + 01
2000
54/132
3.919816e − 05
3.337298e + 03
10/74
NaN
4.031066e + 01
Problem14
500
18/68
5.826508e − 05
2.076373e + 01
16/115
NaN
6.240040e − 01
1000
18/68
8.239959e − 05
1.357989e + 02
16/115
NaN
3.354021e + 00
1500
19/69
5.002681e − 05
4.532921e + 02
16/115
NaN
9.765663e + 00
2000
19/69
5.774900e − 05
1.042820e + 03
16/115
NaN
2.148134e + 01
Problem15
500
8/9
6.870902e − 05
6.910844e + 00
22/23
8.899350e − 05
2.667617e + 00
1000
7/8
7.203786e − 05
3.561503e + 01
16/17
9.828207e − 05
1.174688e + 01
1500
7/8
4.809670e − 05
1.122739e + 02
13/14
9.654107e − 05
2.903179e + 01
2000
7/8
3.609946e − 05
2.583845e + 02
11/12
9.465949e − 05
5.519315e + 01
Problem16
500
0/1
0.000000e + 00
0.000000e + 00
0/1
0.000000e + 00
0.000000e + 00
1000
0/1
0.000000e + 00
0.000000e + 00
0/1
0.000000e + 00
0.000000e + 00
1500
0/1
0.000000e + 00
1.560010e − 02
0/1
0.000000e + 00
0.000000e + 00
2000
0/1
0.000000e + 00
1.560010e − 02
0/1
0.000000e + 00
1.560010e − 02



---

*Source: 716019-2014-08-05.xml*