# A Trust-Region-Based BFGS Method  with Line Search Technique for Symmetric  Nonlinear Equations

Authors: Gonglin Yuan; Shide Meng; Zengxin Wei
Journal: Advances in Operations Research
 (2009)

---

## Abstract

A trust-region-based BFGS method is proposed for solving symmetric
nonlinear equations. In this given algorithm, if the trial step is unsuccessful, the
linesearch technique will be used instead of repeatedly solving the subproblem of the
normal trust-region method. We establish the global and superlinear convergence
of the method under suitable conditions. Numerical results show that the given
method is competitive to the normal trust region method.


---

## Body

## 1. Introduction

Consider the following system of nonlinear equations:(1.1)g(x)=0,x∈ℜn,
where g:ℜn→ℜn is continuously differentiable, and the Jacobian ∇g(x) of g is symmetric for all x∈ℜn. Let ϑ be the norm function  defined by ϑ(x)=1/2∥g(x)∥2. Then the nonlinear equations (1.1) is equivalent to the following global optimization problem:(1.2)minϑ(x),x∈ℜn.There are two ways for nonlinear equations by numerical methods. One is the line search method and the other is the trust region method. For the line search method, the following iterative formula is often used to solve (1.1):(1.3)xk+1=xk+αkdk,
where xk is the kth iteration point, αk is a steplength, and dk is search direction. To begin, we briefly review some methods for (1.1) by line search technique. First, we give some techniques for αk. Brown and Saad [1] proposed the following line search method to obtain the stepsize αk:(1.4)ϑ(xk+αkdk)-ϑ(xk)≤σαk∇ϑ(xk)Tdk,
where σ∈(0,1). Based on this technique, Zhu [2] gave the nonmonotone line search technique:(1.5)ϑ(xk+αkdk)-ϑ(xl(k))≤σαk∇ϑ(xk)Tdk,∥ϑ(xl(k))∥=max0≤j≤m(k){∥ϑ(xk-j)∥},m(0)=0 and m(k)=min{m(k-1)+1,M},k≥1, and M is a nonnegative integer. From these two techniques (1.4) and (1.5), it is easy to see that the Jacobian matrix ∇gk must be computed at every iteration, which will increase the workload especially for large-scale problems or this matrix is expensive to calculate. Considering these points, we [3] presented a new backtracking inexact technique to obtain the stepsize αk:(1.6)∥g(xk+αkdk)∥2≤∥g(xk)∥2+δαk2gkTdk,
where δ∈(0,1),gk=g(xk), and dk is a solution of the system of linear (1.15). We established the global convergence and the superlinear convergence of this method. The numerical results showed that the new line search technique is more effective than the normal methods. Li and Fukashima [4] proposed an approximate monotone line search technique to obtain the step-size αk satisfying(1.7)ϑ(xk+αkdk)-ϑ(xk)≤-δ1∥αkdk∥2-δ2∥αkgk∥2+ϵk∥g(xk)∥2,
where δ1>0 and δ2>0 are positive constants, αk=rik,r∈(0,1),ik is the smallest nonnegative integer i such that (1.7), and ϵk satisfies(1.8)∑k=0∞ϵk<∞.
Combining the line search (1.7) with one special BFGS update formula, they got some better results (see [4]). Inspired by their idea, Wei [5] and Yuan [6–8] presented several approximate methods. Further work can be found in [9].Second, we present some techniques fordk. One of the most effective methods is Newton method. It normally requires a fewest number of function evaluations, and it is very good at handling ill-conditioning. However, its efficiency largely depends on the possibility of solving a linear system efficiently which arises when computing the search dk in each iteration:(1.9)∇g(xk)dk=-g(xk).
Moreover, the exact solution of the system (1.9) could be too burdensome, or it is not necessary when xk is far from a solution [10]. Inexact Newton methods [2, 3, 10] represent the basic approach underlying most of the Newton-type large-scale algorithms. At each iteration, the current estimate of the solution is updated by approximately solving the linear system (1.9) using an iterative algorithm. The inner iteration is typically “truncated” before the solution to the linear system is obtained. Griewank [11] firstly proposed the Broyden's rank one method for nonlinear equations and obtained the global convergence. At present, a lot of algorithms have been proposed for solving these two problems (1.1) and (1.2)(see [12–22] etc.).Trust region method is a kind of important and efficient methods in the area of nonlinear optimization. This method can be traced back to the works of Levenberg [17] and Marquardt [18] on nonlinear least-squares problems and the work of Goldfeld et al. [23] for unconstrained optimization. Powell [24] was the first to establish the convergence result of trust region method for unconstrained optimization. Fletcher [25, 26] firstly proposed trust region algorithms for linearly constrained optimization problems and nonsmooth optimization problems, respectively. This method has been studied by many authors [15, 27–31] and has been applied to equality constrained problems [32–34]. Byrd et al. [35], Fan [36], Powell and Yuan [37], Vardi [38], Yuan [39, 40], Yuan et al. [41], and Zhang and Zhu [42] proposed various trust region algorithms for constrained optimization problems and established the convergence. Fan [36], Yuan [39], and Zhang [43] presented the trust region algorithms for nonlinear equations and got some results.The normal trust-region subproblem for nonlinear equations is to find the trial stepdk such that(1.10)minqk*(d)=dT∇g(xk)g(xk)+12dT∇g(xk)T∇g(xk)ds.t.∥d∥≤Δk,
where Δk>0 is a scalar called the trust region radium. Define the predicted descent of the objective function g(x) at kth iteration by(1.11)Predk*=qk*(0)-qk*(dk),
the actual descent of g(x) by(1.12)Aredk*=ϑ(xk)-ϑ(xk+dk),
and the ratio of actual descent to predicted descent:(1.13)rk*=Aredk*Predk*.
For the normal trust region algorithm, if rk*≥ρ (ρ∈(0,1), this case is called a successful iteration), the next iteration is xk+1=xk+dk, and go to the next step; otherwise reduce the trust region radium Δk and solve this subproblem (1.10) repeatedly. Sometimes, we must do this work many times and compute the Jacobian matrix ∇g(xk) and ∇g(xk)T∇g(xk) at every time, which obviously increases the work time and workload, especially for large-scale problems. Even more detrimental, the trust region subproblem is not very easy (see [36, 39] etc.) to be solved for most of the practical problems.In order to alleviate the above bad situation that traditional algorithms have to compute Jacobian matrix∇g(xk) and ∇g(xk)T∇g(xk) at each and every iteration while repeatedly resolving the trust region subproblem, in this paper, we would like to rewrite the following trust-region subproblem as(1.14)minqk(d)=g(xk)Td+12dTBkds.t.∥d∥≤Δk,
where matrix Bk is the approximation to the Jacobian matrix of g(x) at xk. Due to the boundness of the region {d∣∥d∥≤Δk}, (1.14) has a solution regardless of Bk′s definiteness (see [43]). This implies that it is valid to adopt a BFGS update formula to generate Bk for trust region methods and the BFGS update is presented as follows:(1.15)Bk+1=Bk+ykykTskTyk-BkskskTBkskTBksk,
where yk=gk+1-gk,sk=xk+1-xk. Define the predicted descent of the objective function g(x) at kth iteration by(1.16)Predk=qk(0)-qk(dk),
the actual descent of g(x) by(1.17)Aredk=∥g(xk)∥2-∥g(xk+dk)∥2,
and the ratio of actual descent to predicted descent:(1.18)rk=∥g(xk)∥2-∥g(xk+dk)∥2qk(0)-qk(dk).
If rk≥ρ (ρ∈(0,1), called a successful iteration ), the next iteration is xk+1=xk+dk. Otherwise, we use a search technique to obtain the steplength λk and let the next iteration be xk+1=xk+λkdk. Motivated by the idea of the paper [4], we propose the following linesearch technique to obtain λk:(1.19)∥g(xk+λkdk)∥2-∥gk∥2≤-σ1∥λkgk∥2-σ2∥λkdk∥2+σ3λkdkTgk,
where σ1, σ2, and σ3 are some positive constants. In Section 3, we will show (1.19) is well-defined. Here and throughout this paper, ∥·∥ denotes the Euclidian norm of vectors or its induced matrix norm. g(xk) is replaced by gk.In the next section, the proposed algorithm for solving (1.1) is given. The global and superlinear convergence of the presented algorithm are stated in Section 3 and Section 4, respectively. The numerical results of the method are reported in Section 5.


## 2. Algorithms

Algorithm 2.1.
Initial: choose ρ, r∈(0,1), 0<τ1<τ2<1<τ3, σ1,σ2,σ3>0,Δmin>0, x0∈ℜn. Let k:=0;Step 1: LetΔk=Δmin;Step 2: If∥gk∥=0, stop. Otherwise go to Step 3;Step 3: Solve the subproblem (1.14) with Δ=Δk to get dk;Step 4: If(2.1)rk≜∥g(xk)∥2-∥g(xk+dk)∥2qk(0)-qk(dk)<ρ,
Go to Step 5; Otherwise Let xk+1=xk+dk,Δk+1∈[∥dk∥,τ3∥dk∥], and go to Step 6;Step 5: Letk be the smallest nonnegative integer i such that (1.19) holds for λ=ri. Let λk=rik and xk+1=xk+λkdk, Δk+1∈[τ1∥dk∥,τ2∥dk∥];Step 6: Update Bk to get Bk+1 by (1.15). Let k:=k+1. Go to Step 2.Here we also give a normal trust-region method for (1.1) and call it Algorithm 2.2.Algorithm 2.2 (the normal Trust-Region Algorithm [44]).
Initial: Given a starting point x0∈ℜn,Δ0>0 is the initial trust region radium, an upper bound of trust region radius Δ′,0<Δ0≤Δ′. Set 0<μ<1,0<η1<η2<1<η3,k:=0.Step 1: If∥gk∥=0, stop. Otherwise, go to Step 2.Step 2: Solve the trust-region subproblem (1.10) to obtain dk.Step 3: Let(2.2)rk=ϑ(xk)-ϑ(xk+dk)qk*(0)-qk*(dk),
if rk<η1, set Δk+1=η1Δk; If rk>η2 and ∥dk∥=Δk, let Δk+1=min{η3Δk,Δ′}; Otherwise, let Δk+1=Δk.Step 4: Ifrk>μ, let xk+1=xk+dk and go to Step 5; otherwise, let xk+1=xk, go to Step 2.Step 5: Setk:=k+1. Go to Step 1.Remark 2.3.
Byyk=gk+1-gk, we have the following approximate relations:
(2.3)yk=gk+1-gk≈∇gk+1sk.
Since Bk+1 satisfies the secant equation Bk+1sk=yk and ∇gk+1 is symmetric, we have approximately
(2.4)Bk+1sk≈∇gk+1sk=∇gk+1Tsk.
This means that Bk+1 approximates ∇gk+1 along direction sk.


## 3. The Global Convergence

In this section, we will establish the global convergence of Algorithm2.1. Let Ω be the level set defined by(3.1)Ω={x∣∥g(x)∥≤∥g(x0)∥},
which is bounded.Assumption 1.
(A)g is continuously differentiable on an open convex set Ω1 containing Ω.
(B) The Jaconbian ofg is symmetric and bounded on Ω1 and there exists a positive constant M such that
(3.2)∥∇g(x)∥≤M∀x∈Ω1.
(C)∇g is positive definite on Ω1; that is, there is a constant m>0 such that
(3.3)m∥d∥2≤dT∇g(x)d∀x∈Ω1,d∈ℜn.
(D)ϑ(x) is differentiable and its gradient satisfies
(3.4)∥∇ϑ(x)-∇ϑ(y)∥≤L∥x-y∥,∀x,y∈Ω1,
where L is the Lipschitz constant. By Assumptions 1(A) and 1(B), it is not difficult to get the following inequality:
(3.5)∥yk∥≤M∥sk∥.
According to Assumptions 1(A) and 1(C), we have
(3.6)skTyk=skT∇g(ξ)sk≥m∥sk∥2,
where ξ=xk+ϑ0(xk+1-xk),ϑ0∈(0,1), which means that the update matrix Bk is always positive definite. By (3.5) and (3.6), we have
(3.7)skTyk∥sk∥2≥m,∥yk∥2skTyk≤M2m.Lemma 3.1 ([see Theorem 2.1 in [45]]).
Suppose that Assumption1 holds. Let Bk be updated by BFGS formula (1.15) and let B0 be symmetric and positive definite. For any k≥0,sk and yk satisfy (3.7). Then there exist positive constants β1,β2, and β3 such that, for any positive integer k̃(3.8)β1∥dk∥2≤dkTBkdk≤β2∥dk∥2,β1∥dk∥≤∥Bkdk∥≤β3∥dk∥
hold for at least ⌈k̃/2⌉ value of k∈{1,2,…,k̃}.Considering the subproblem (1.14), we give the following assumption similar to (1.14). Similar to [2], the following assumption is needed.Assumption 2.
Bk is a good approximation to ∇gk, that is,
(3.9)∥(∇gk-Bk)dk∥≤ε0∥gk∥,
and dk satisfies
(3.10)∥gk+Bkdk∥≤ε1∥gk∥,
where ε0∈(0,1) is a small quantity, and ε1>0,ε0+ε1∈(0,1).Lemma 3.2.
Let Assumption2 hold. Then dk is descent direction for ϑ(x) at xk, that is,
(3.11)∇ϑ(xk)Tdk<0.Proof.
Letrk be the residual associated with dk so that gk+Bkdk=rk:
(3.12)∇ϑ(xk)Tdk=g(xk)T∇g(xk)dk=g(xk)T[(∇g(xk)-Bk)dk+(rk-g(xk))]=g(xk)T(∇g(xk)-Bk)dk+g(xk)Trk-g(xk)Tg(xk).
So we have
(3.13)∇ϑ(xk)Tdk+∥g(xk)∥2=g(xk)T(∇g(xk)-Bk)dk+g(xk)Trk.
Therefore, taking the norm in the right-hand side of the above equality, we have that from Assumption 2(3.14)∇ϑ(xk)Tdk≤∥g(xk)∥∥(∇g(xk)-Bk)dk∥+∥g(xk)∥∥rk∥-∥g(xk)∥2≤-(1-ε0-ε1)∥g(xk)∥2.
Hence, for ε0+ε1∈(0,1), the lemma is satisfied.According to the above lemma, it is easy to deduce that the norm functionϑ(x) is descent, which means that ∥gk+1∥≤∥gk∥ is true.Lemma 3.3.
Let{xk} be generated by Algorithm 2.1 and suppose that Assumption 2 holds. Then {xk}⊂Ω. Moreover, {∥gk∥} converges.Proof.
By Lemma3.2, we have ∥gk+1∥≤∥gk∥. Then we conclude from Lemma 3.3 in [46] that {∥gk∥} converges. Moreover, we have for all k(3.15)∥gk+1∥≤∥gk∥≤∥gk-1∥≤⋯≤∥g(x0)∥.
This implies that {xk}⊂Ω.Lemma 3.4.
Let Assumption1 hold. Then the following inequalities
(3.16)gkTdk≤-β1∥dk∥2,∥gk∥2≥β12∥dk∥2(3.17)-1β1∥gk∥2≤gkTdk
hold.Proof.
Since the update matrixBk is positive definite. Then, problem (1.14) has a unique solution dk, which together with some multiplier αk≥0 satisfies the following equations:
(3.18)Bkdk+αkdk=-gk,αk(∥dk∥-Δk)=0.
From (3.18), we can obtain
(3.19)dkTBkdk+gkTdk=-αk∥dk∥2≤0,(3.20)αk=-gkTdk-dkTBkdk∥dk∥2.
By (3.19) and (3.8), we get (3.16), which also imply that the inequality (3.17) holds.The next lemma will show that (1.19) is reasonable, and then Algorithm 2.1 is well defined.Lemma 3.5.
Let Assumptions1(D) and 2 hold. Then there exists a step-size λk such that (1.19) in a finite number of backtracking steps.Proof.
From Lemma 3.8 in [1] we have that in a finite number of backtracking steps, λk must satisfy
(3.21)∥g(xk+αkdk)∥2-∥g(xk)∥2≤δλkg(xk)T∇g(xk)dk,δ∈(0,1).
By (3.12) and (3.14), let β0=(1-ε0-ε1), and we have
(3.22)g(xk)T∇g(xk)dk≤-β0∥gk∥2=-β03∥gk∥2-β03∥gk∥2-β03∥gk∥2≤-β03∥gk∥2-β03β12∥dk∥2+β03β1gkTdk,
where the last inequality follows (3.16) and (3.17). By λk≤1, let σ1∈(0,(β0/3)δ),σ2∈(0,(β0/3)β12δ),σ3∈(0,(β0/3)β1δ), then we obtain (1.19). The proof is complete.Lemma 3.6.
Let{xk} be generated by the Algorithm 2.1. Suppose that Assumptions 1 and 2 hold. Then one has
(3.23)∑k=0∞(-gkTdk)<∞,∑k=0∞dkTBkdk<∞.
In particular, one has
(3.24)limk→∞(-gkTdk)=0,limk→∞dkTBkdk=0.Proof.
By (3.8) and (3.19), we have
(3.25)qk(dk)=gkTdk+12dkTBkdk≤12gkTdk≤-12dkTBkdk.
From Step 4 of Algorithm 2.1, if rk≥ρ is true, we get
(3.26)∥g(xk+1)∥2-∥g(xk)∥2≤qk(dk)≤12gkTdk≤-12dkTBkdk,
otherwise, if rk<ρ is true, by Step 5 of Algorithm 2.1, (3.8), and (3.26), we can obtain
(3.27)∥g(xk+1)∥2-∥g(xk)∥2≤-σ1∥λkgk∥2-σ2∥λkdk∥2+σ3λkdkTgk≤σ3λkdkTgk≤-σ3λkdkTBkdk.
By Lemma 3.5, we know that (1.19) can be satisfied in a finite number of backtracking steps, which means that there exists a constant λ*∈(0,1) satisfying λ*≤λk for all k. By (3.26) and (3.27), we have
(3.28)∥g(xk+1)∥2-∥g(xk)∥2≤ρ1gkTdk≤-ρ1dkTBkdk≤-ρ1β1∥dk∥2<0,
where ρ1=min{1/2,σ3λ*}. According to (3.28), we get
(3.29)∑k=0∞dkTBkdk≤∑k=0∞(-gkTdk)≤1ρ1∑k=0∞(∥g(xk)∥2-∥g(xk+1)∥2)=1ρ1limN→∞∑k=0N(∥g(xk)∥2-∥g(xk+1)∥2)=1ρ1limN→∞(∥g(x0)∥2-∥g(xN+1)∥2),
and by Lemma 3.3, we know that {∥gk∥} is convergent. Therefore, we deduce that (3.23) holds. According to (3.23), it is easy to deduce (3.24). The proof is complete.Lemma 3.7.
Suppose that Assumptions1 and 2 hold. There are positive constants b1≤b2,andb3 such that for any k, if ∥dk∥≠Δmin, then the following inequalities hold:
(3.30)b1∥gk∥≤∥dk∥≤b2∥gk∥,αk≤b3.Proof.
We will prove this lemma in the following two cases.Case 1 (∥dk∥<Δk).
By (3.18), we have αk=0 and Bkdk=-gk. Together with (3.8) and (3.19), we get
(3.31)β1∥dk∥2≤dkTBkdk=-dkTgk≤∥dk∥∥gk∥,∥-gk∥=∥gk∥=∥Bkdk∥≤β3∥dk∥.
Then (3.30) holds with b1=1/β3≤b2=1/β1 and b3=0.Case 2 (∥dk∥=Δk).
From (3.19) and (3.8), we have
(3.32)β1∥dk∥2≤dkTBkdk≤-gkTdk≤∥gk∥∥dk∥.
Then, we get ∥dk∥≤1/β1∥gk∥. By (3.10) and (3.8), it is easy to deduce that
(3.33)(1-ε1)∥gk∥≤∥Bkdk∥≤β3∥dk∥.
So we obtain ∥dk∥≥(1-ε1)/β3∥gk∥. Using (3.20), we have
(3.34)αk=-gkTdk-dkTBkdk∥dk∥2≤∥gk∥∥dk∥≤β31-ε1.
Therefore, (3.30) holds. The proof is complete.In the next theorem, we establish the global convergence of Algorithm2.1.Theorem 3.8.
Let{xk} be generated by Algorithm 2.1 and the conditions in Assumptions 1 and 2 hold. Then one has
(3.35)limk→∞∥gk∥=0.Proof.
By Lemma3.6, we have
(3.36)limk→∞-gkTdk=limk→∞dkTBkdk=0.
Combining (3.8) and (3.36), we get
(3.37)limk→∞∥dk∥=0.
Together with (3.30), we obtain (3.35). The proof is complete.


## 4. The Superlinear Convergence Analysis

In this section, we will present the superlinear convergence of Algorithm2.1.Assumption 3.
∇g is Hölder continuous at x*; that is, for every x in a neighborhood of x*, there are positive constants M1 and γ such that
(4.1)∥∇g(x)-∇g(x*)∥≤M1∥x-x*∥γ,
where x* stands for the unique solution of (1.1) in Ω1.Lemma 4.1.
Let{xk} be generated by Algorithm 2.1 and the conditions in Assumptions 1 and 2 hold. Then, for any fixed γ>0, one has
(4.2)∑k=0∞∥xk-x*∥γ<∞.
Moreover, one has
(4.3)∑k=0∞χk(γ)<∞,
where χk(γ)=max{∥xk-x*∥γ,∥xk+1-x*∥γ}.Proof.
Using Assumption1, we can have the following inequality:
(4.4)m∥x-x*∥≤∥g(x)∥=∥g(x)-g(x*)∥≤M∥x-x*∥,x∈Ω1.
By (3.8) and (3.30), we have
(4.5)-β2∥dk∥2≤-dkTBkdk≤-β1∥dk∥2,-b22∥gk∥2≤-∥dk∥2≤-b12∥gk∥2.
Together with (3.28), we get
(4.6)∥gk+1∥2-∥gk∥2≤ρ1gkTdk≤-ρ1dkTBkdk≤-ρ1β1∥dk∥2≤-ρ1β1b12∥gk∥2,
and let ρ0=min{ρ1β1b12,ρ}∈(0,1). Suppose that there exists a positive integer k0, as k≥k0, (3.8) holds. Then we obtain
(4.7)∥gk+1∥2≤∥gk∥2-ρ0∥gk∥2=(1-ρ0)∥gk∥2≤⋯≤(1-ρ0)k-k0+1∥gk0∥2=c0c1k,
where c0=(1-ρ0)1-k0∥g0∥2,c1=(1-ρ0)∈(0,1). This together with (4.4) shows that ∥xk+1-x*∥2≤m-2c0c1k holds for all k large enough. Therefore, for any γ, we have (4.2). Notice that χk(γ)≤∥xk-x*∥γ+∥xk+1-x*∥γ; from (4.2), we can get (4.3).Lemma 4.2.
Let Assumptions1, 2, and 3 hold. Then, for all k sufficiently large, there exists a positive constant M2 such that
(4.8)∥yk-∇g(x*)sk∥≤M2χk∥sk∥,
where χk=max{∥xk-x*∥γ,∥xk+1-x*∥γ}.Proof.
From Theorem3.8 and (4.4), it is not difficult to get xk→x*. Then (4.1) holds for all k large enough. Using the mean value theorem, for all k sufficiently large, we have
(4.9)∥yk-∇g(x*)sk∥=∥∇g(xk+t0(xk+1-xk))sk-∇g(x*)sk∥≤∥∇g(xk+t0(xk+1-xk))-∇g(x*)∥∥sk∥≤M1∥xk+t0(xk+1-xk)-x*∥γ∥sk∥≤M2χk∥sk∥,
where M2=M1(2t0+1),t0∈(0,1). Therefore, the inequality of (4.8) holds.Lemma 4.3.
Let Assumptions1, 2, and 3 hold and let {xk} be generated by Algorithm 2.1. Denote Q=∇g(x*)-1/2, Hk=Bk-1. Then, for all large k, there are positive constants ei, i=1,2,3,4, and η∈(0,1) such that
(4.10)∥Bk+1-∇g(x*)∥Q,F≤(1+e1χk)∥Bk-∇g(x*)∥Q,F+e2χk,(4.11)∥Hk+1-∇g(x*)-1∥Q-1,F≤(1-ηϖk2+e3χk)∥Hk-∇g(x*)-1∥Q-1,F+e4χk,
where ∥A∥Q,F=∥QTAQ∥F, ∥·∥F is the Frobenius norm of a matrix and ϖk is defined as follows:
(4.12)ϖk=∥Q-1(Hk-∇g(x*)-1)yk∥∥Hk-∇g(x*)-1∥Q-1,F∥Qyk∥.
In particular, {∥Bk∥}F and {∥Hk∥}F are bounded.Proof.
From (1.15), we have
(4.13)∥Bk+1-∇g(x*)∥Q,F=∥Bk-∇g(x*)+BkskskTBkskTBksk+ykykTskTyk∥Q,F≤(1+e1τk)∥Bk-∇g(x*)∥Q,F+e2χk,
where the last inequality follows the inequality (49) of [47]. Hence, (4.10) holds. By (4.8), in a way similar to that of [46], we can prove that (4.11) holds and ∥Bk∥ and ∥Hk∥ are bounded. The proof is complete.Lemma 4.4.
Let{xk} be generated by Algorithm 2.1 and the conditions in Assumptions 1, 2 and 3 hold. Then
(4.14)limk→∞∥(Bk-∇g(x*))sk∥∥sk∥=0,
where sk=xk+1-xk.Proof.
In a similar way to [46], it is not difficult to obtain
(4.15)limk→∞∥Q-1(Hk-∇g(x*)-1)yk∥∥Qyk∥=0.
On the other hand, we have
(4.16)∥Q-1(Hk-∇g(x*)-1)yk∥=∥Q-1Hk(∇g(x*)-Bk)∇g(x*)-1yk∥≥∥Q-1Hk(∇g(x*)-Bk)sk∥-∥Q-1Hk(∇g(x*)-Bk)(sk-∇g(x*)-1yk)∥≥∥Q-1Hk(∇g(x*)-Bk)sk∥-∥Q-1∥∥Hk∥(∥∇g(x*)∥+∥Bk∥)∥∇g(x*)-1(yk-∇g(x*)sk)∥≥∥Q-1Hk(∇g(x*)-Bk)sk∥-M2χk∥Q-1∥∥Hk∥(∥∇g(x*)∥+∥Bk∥)∥∇g(x*)-1∥∥sk∥=∥Q-1Hk(∇g(x*)-Bk)sk∥-o(∥sk∥),
where the last inequality follows from (4.8). We know that {∥Bk∥} and {∥Hk∥} are bounded, and {Hk} is positive definite. By (3.5), we get
(4.17)∥Qyk∥≤M∥Q∥∥sk∥.
Combining (4.15) and (4.17), we conclude that (4.14) holds. The proof is complete.Theorem 4.5.
Let the conditions in Assumptions1, 2 and 3 hold. If ε1→0 in (3.10). Then the sequence {xk} generated by Algorithm 2.1 converges to x* superlinearly for λk=1.Proof.
For allxk∈Ω1, we get
(4.18)∥gk+1∥∥dk∥=∥gk+Bkdk+(∇gk-Bk)dk+O(∥dk∥2)∥∥dk∥≤∥gk+Bkdk∥∥gk∥∥gk∥∥dk∥+∥(∇gk-Bk)dk∥∥dk∥+O(∥dk∥2)∥dk∥≤ε1∥gk∥∥dk∥+∥(∇gk-Bk)dk∥∥dk∥+O(∥dk∥),
where the last inequality follows (3.10). By (3.5), we have
(4.19)∥gk∥≤∥gk+1-gk∥+∥gk+1∥≤M∥dk∥+∥gk+1∥.
Dividing both sides by ∥dk∥, we get
(4.20)∥gk∥∥dk∥≤M+∥gk+1∥∥dk∥.
Substituting this into (4.18), we can obtain
(4.21)∥gk+1∥∥dk∥≤ε1(M+∥gk+1∥∥dk∥)+∥(∇gk-Bk)dk∥∥dk∥+O(∥dk∥),
which means that
(4.22)∥gk+1∥∥dk∥≤(Mε1+∥(∇gk-Bk)dk∥/∥dk∥+O(∥dk∥))(1-ε1).
Since ε1→0, and ∥dk∥→0 as k→∞, by (4.14) and (3.10), we have
(4.23)limk→∞∥gk+1∥∥dk∥=0.
Using (3.16), we get
(4.24)limk→∞∥gk+1∥∥gk∥=0.
Considering (4.4), we have
(4.25)limk→∞∥xk+dk-x*∥∥xk-x*∥=0.
Therefore, we get the result of the superlinear convergence.


## 5. Numerical Results

In this section, we test the proposed BFGS trust-region method on symmetric nonlinear equations and compare it with Algorithm2.2. The following problems with various sizes will be solved.Problem 1.
The discretized two-point boundary value problem like the problem in [48] is
(5.1)g(x)≜Ax+1(n+1)2F(x)=0,
where A is the n×n tridiagonal matrix given by
(5.2)A=[8-1-18-1-18-1⋱⋱⋱⋱⋱-1-18],
and F(x)=(F1(x),F2(x),…,Fn(x))Twith Fi(x)=sinxi-1,i=1,2,…,n.Problem 2.
Unconstrained optimization problem is(5.3)minf(x),x∈Rn,
with Engval function [49] f:Rn→R defined by
(5.4)f(x)=∑i=2n[(xi-12+xi2)2-4xi-1+3].
The related symmetric nonlinear equation is
(5.5)g(x)≜14∇f(x)=0,
where g(x)=(g1(x),g2(x),…,gn(x))T with
(5.6)g1(x)=x1(x12+x22)-1,gi(x)=xi(xi-12+2xi2+xi+12)-1,i=2,3,…,n-1,gn(x)=xn(xn-12+xn2).
In the experiments, the parameters in Algorithm 2.1 were chosen as τ1=0.5,τ2=0.9,τ3=3,r=0.1,Δmin=∥g0∥, B0=I,ρ=0.25, σ1=σ2=10-5, and σ3=0.9. We obtain dk from subproblem (1.14) by the well-known Dogleg method. The parameters in Algorithm 2.2 were chosen as Δ′=Δ0=∥g0∥,η1=0.25,η2=0.75,μ=0.01, and η3=2. Since the matrices ∇g(xk)T∇g(xk) will be singular, we solve (1.10) by ExtremeMinimizationwith2-DimensionSubspaceMethod to obtain dk. The program was coded in MATLAB6.5.1. We stopped the iteration when the condition ∥g(x)∥≤10-6 was satisfied. If the iteration number is larger than one thousand, we also stop this program and this method is considered to be failed. For Algorithm 2.1, Tables 1(a) and 1(b) and Tables 2(a) and 2(b) show the performance of the method need to solve Problem 1 and Problem 2, respectively. For Algorithm 2.2, Tables 1(c) and 1(d) and Tables 2(c) and 2(d) show the performance of the normal trust region method need to solve Problem 1 and Problem 2, respectively. The columns of the tables have the following meaning:Dim: the dimension of the problem,NI: the total number of iterations,NG: the number of the function evaluations,EG: the norm of the function evaluations.Table 1
Test Results For Problem1.
(a)
(Small-scales). Test results for Algorithm2.1.
x0(1,…,1)(60,…,60)(600,…,600)(-1,…,-1)(-60,…,-60)(-600,…,-600)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=1013/24/2.406624e-0714/25/2.272840e-0717/30/3.104130e-0713/24/2.449361e-0714/25/2.398188e-0717/30/4.593832e-07n=5048/101/2.189696e-0749/102/4.009098e-0750/103/2.147571e-0748/101/2.181267e-0749/102/4.008911e-0750/103/2.120250e-07n=9982/171/6.794811e-0789/188/6.345939e-0791/190/7.804790e-0782/171/8.358725e-0789/188/6.367964e-0791/190/7.801889e-07x0(1,0,1,0,…)(60,0,60,0,…)(600,0,600,0,…)(-1,0,-1,0,…)(-60,0,-60,0,…)(-600,0,-600,0,…)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=1021/42/7.364467e-0722/43/3.922363e-0722/45/4.894966e-0721/44/3.463471e-0822/43/3.860638e-0722/45/4.895404e-07n=5072/153/9.350290e-0786/181/4.420131e-0788/185/7.620218e-0770/151/6.776281e-0786/181/4.420083e-0749/83/8.003368e-07n=9973/156/9.013346e-0788/185/7.631881e-0788/191/6.856481e-0774/161/9.918464e-0788/185/7.368909e-0788/191/6.856897e-07(b)
(Large-scales). Test results for Algorithm2.1.
x0(1,…,1)(60,…,60)(600,…,600)(-1,…,-1)(-60,…,-60)(-600,…,-600)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=20083/178/9.096568e-7106/225/9.483206e-7117/250/8.796828e-785/180/7.376219e-7106/225/9.263058e-7117/250/8.779599e-7n=50085/180/8.830573e-7103/218/9.825658e-7115/244/9.765194e-783/178/7.659650e-7103/218/9.796118e-7115/244/9.755827e-7n=100076/165/8.611337e-796/207/8.301215e-7105/224/9.957816e-776/165/8.587066e-796/207/8.291876e-7105/224/9.925005e-7x0(1,0,1,0,…)(60,0,60,0,…)(600,0,600,0,…)(-1,0,-1,0,…)(-60,0,-60,0,…)(-600,0,-600,0,…)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=20068/149/8.780047e-791/194/7.484521e-7101/216/9.790557e-769/150/9.770900e-791/194/7.275693e-7101/216/9.559911e-7n=50072/155/9.797645e-0796/205/9.993161e-7106/225/8.916405e-772/155/9.886969e-797/206/7.492841e-7106/225/8.921008e-7n=100069/152/9.919863e-793/200/6.930976e-7106/227/8.119328e-769/152/9.948500e-793/200/6.946308e-7106/227/8.123102e-7(c)
(Small-scales). Test results for Algorithm2.2.
x0(1,…,1)(60,…,60)(600,…,600)(-1,…,-1)(-60,…,-60)(-600,…,-600)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=1054/107/8.039519e-767/133/7.624248e-774/147/8.167466e-754/107/8.061366e-767/133/7.624560e-774/147/8.167469e-7n=5058/115/9.602663e-772/143/7.684310e-00779/157/8.876868e-758/115/9.603892e-772/143/7.684327e-00779/157/8.876870e-7n=9960/119/7.614838e-773/145/8.350445e-780/159/9.679851e-760/119/7.615091e-773/145/8.350450e-780/159/9.679851e-7x0(1,0,1,0,…)(60,0,60,0,…)(600,0,600,0,…)(-1,0,-1,0,…)(-60,0,-60,0,…)(-600,0,-600,0,…)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=1052/103/7.605486e-764/127/9.929883e-772/143/7.732628e-752/103/7.646868e-764/127/9.930747e-772/143/7.732660e-7n=5056/111/8.896898e-769/137/9.690007e-777/153/8.223484e-756/111/8.899175e-769/137/9.690048e-777/153/8.223488e-7n=9957/113/9.598124e-771/141/7.734909e-778/155/8.965851e-757/113/9.598763e-771/141/7.734918e-778/155/8.965852e-7(d)
(Large-scales). Test results for Algorithm2.2.
x0(1,…,1)(60,…,60)(600,…,600)(-1,…,-1)(-60,…,-60)(-600,…,-600)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=20061/121/8.110467e-774/147/8.917908e-782/163/7.610549e-761/121/8.110534e-774/147/8.917909e-782/163/7.610549e-7n=50062/123/9.526492e-776/151/7.712044e-783/165/8.958279e-762/123/9.526504e-776/151/7.712044e-783/165/8.958279e-7n=100063/125/9.938699e-777/153/8.049274e-784/167/9.351920e-763/125/9.938703e-777/153/8.049274e-784/167/9.351920e-7x0(1,0,1,0,…)(60,0,60,0,…)(600,0,600,0,…)(-1,0,-1,0,…)(-60,0,-60,0,…)(-600,0,-600,0,…)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=20059/117/7.503172e-772/143/8.249912e-779/157/9.576414e-759/117/7.503296e-772/143/8.249914e-779/157/9.576414e-7n=50060/119/8.811245e-773/145/9.701366e-781/161/8.285552e-760/119/8.811269e-773/145/9.701367e-781/161/8.285552e-7n=100061/121/9.191890e-775/149/7.444393e-782/163/8.649128e-761/121/9.191896e-775/149/7.444393e-782/163/8.649128e-7Table 2
Test Results For Problem2.
(a)
(Small-scales). Test results for Algorithm2.1.
x0(0.5,…,0.5)(1,…,1)(3,…,3)(-0.75,…,-0.75)(-2,…,-2)(-3,…,-3)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=1025/44/9.720971e-0721/32/4.889567e-0792/103/2.475812e-0821/32/8.691255e-0746/59/5.860956e-0786/105/6.348374e-08n=5037/56/9.950345e-0739/56/8.776379e-07113/139/9.587026e-0740/63/6.984106e-0769/96/9.523480e-07103/125/9.404211e-07n=9942/59/9.725361e-0741/60/7.374460e-07113/135/7.909796e-0740/55/8.380367e-07117/489/9.805302e-0797/129/7.975248e-07x0(0.5,0,0.5,0,…)(1,0,1,0,…)(3,0,3,0,…)(-0.75,0,-0.75,0,…)(-2,0,-2,0,…)(-3,0,-3,0,…)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=1024/35/4.711749e-0721/30/3.147507e-0744/65/3.529113e-0727/48/4.004367e-0739/76/8.503415e-0729/42/7.623619e-07n=5036/57/8.776354e-0736/57/8.287552e-0754/77/8.491652e-0741/64/9.492805e-0742/69/9.029472e-0758/77/9.752703e-07n=9936/61/8.265146e-0737/56/9.507706e-0760/93/5.373087e-0742/73/8.247653e-0750/79/9.217390e-0762/88/8.307004e-07(b)
(Large-scales). Test results for Algorithm2.1
x0(0.5,…,0.5)(1,…,1)(3,…,3)(-0.75,…,-0.75)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=20040/57/7.464372e-00741/58/4.921097e-007112/130/6.229759e-00740/65/7.785598e-007n=50036/57/7.887407e-00741/60/3.538433e-007113/135/8.871522e-00738/69/9.785814e-007n=100042/65/7.382939e-00740/59/7.463210e-007120/146/6.044161e-00740/69/4.563405e-007x0(0.5,0,0.5,0,…)(1,0,1,0,…)(3,0,3,0,…)(-0.75,0,-0.75,0,…)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=20041/64/6.671246e-00736/61/9.977774e-00763/94/8.153527e-00739/64/9.737674e-007n=50042/67/9.154342e-00737/58/8.340650e-00749/74/8.277585e-00737/60/6.328648e-007n=100043/62/7.874632e-00740/61/8.997602e-00755/76/8.830280e-00741/68/8.430165e-007(c)
(Small-scales). Test results for Algorithm2.2.
x0(0.5,…,0.5)(1,…,1)(3,…,3)(-0.75,…,-0.75)(-2,…,-2)(-3,…,-3)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=10NI>1000NI>1000NI>1000NI>1000NI>1000NI>1000n=50NI>1000NI>1000NI>1000NI>1000NI>1000NI>1000n=99NI>1000NI>1000NI>1000NI>1000NI>1000NI>1000x0(0.5,0,0.5,0,…)(1,0,1,0,…)(3,0,3,0,…)(-0.75,0,-0.75,0,…)(-2,0,-2,0,…)(-3,0,-3,0,…)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=10196/391/9.528159e-007204/407/9.939962e-007213/425/9.975163e-007NI>1000NI>1000NI>1000n=50199/397/9.791882e-007208/415/9.592104e-007217/433/9.634499e-007NI>1000NI>1000NI>1000n=99NI>1000NI>1000NI>1000NI>1000NI>1000NI>1000(d)
(Large-scales). Test results for Algorithm2.2.
x0(0.5,…,0.5)(1,…,1)(3,…,3)(-0.75,…,-0.75)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=200NI>1000NI>1000NI>1000NI>1000n=500NI>1000NI>1000NI>1000NI>1000n=1000NI>1000NI>1000NI>1000NI>1000x0(0.5,0,0.5,0,…)(1,0,1,0,…)(3,0,3,0,…)(-0.75,0,-0.75,0,…)DimNI/NG/EGNI/NG/EGNI/NG/EGNI/NG/EGn=200200/399/9.537272e-007208/415/9.804205e-007217/433/9.775482e-007NI>1000n=500201/401/9.425775e-007209/417/9.430954e-007217/433/9.908579e-007NI>1000n=1000202/403/9.503816e-007209/417/9.824140e-007218/435/9.470469e-007NI>1000From Tables1(a)–2(d), it is not difficult to see that the proposed method performs better than the normal method does. Furthermore, the performance of Algorithm 2.1 hardly changes with the dimension increasing. Overall, the given method is competitive to the normal trust region method.


## 6. Discussion

We give a trust-region-based BFGS method and establish its convergent results in this paper. The numerical results show that this method is promising. In fact, this problem (1.1) can come from unconstrained optimization problem and an equality constrained optimization problem (for details see [4]). There are some other practical problems, such as the saddle point problem, the discretized two-point boundary value problem, and the discretized elliptic boundary value problem, take the form of (1.1) with symmetric Jacobian (see, e.g., Chapter 1 in [50]). This presented method can also extend to solve the normal nonlinear equations.



---

*Source: 909753-2009-11-30.xml*