# Global Convergence of a Modified Two-Parameter Scaled BFGS Method with Yuan-Wei-Lu Line Search for Unconstrained Optimization

Authors: Pengyuan Li; Zhan Wang; Dan Luo; Hongtruong Pham
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The BFGS method is one of the most efficient quasi-Newton methods for solving small- and medium-size unconstrained optimization problems. For the sake of exploring its more interesting properties, a modified two-parameter scaled BFGS method is stated in this paper. The intention of the modified scaled BFGS method is to improve the eigenvalues structure of the BFGS update. In this method, the first two terms and the last term of the standard BFGS update formula are scaled with two different positive parameters, and the new value ofyk is given. Meanwhile, Yuan-Wei-Lu line search is also proposed. Under the mentioned line search, the modified two-parameter scaled BFGS method is globally convergent for nonconvex functions. The extensive numerical experiments show that this form of the scaled BFGS method outperforms the standard BFGS method or some similar scaled methods.


---

## Body

## 1. Introduction

Consider(1)minfx,where x∈ℜn, and f:ℜn⟶ℜ is a continuously differentiable function bounded from below. The quasi-Newton methods are currently used in countless optimization software for solving unconstrained optimization problems [1–8]. The BFGS method, one of the most efficient quasi-Newton methods, for solving (1) is an iterative method of the following form:(2)xk+1=xk+αkdk,where k=0,1,2,…,αk, obtained by some line search rule, is a step size, and dk is the BFGS search direction computed by the following equation:(3)Bkdk=−gk,where gk=gxk is the gradient of fx, and the matrix Bk is the BFGS approximation to the Hessian ∇2fxk, which has the following update formula:(4)Bk+1=Bk−BkskskTBkskTBksk+ykykTykTsk,where sk=xk+1−xk and yk=gk+1−gk. The problems related to the BFGS method have been analyzed and studied by many scholars, and satisfactory conclusions have been drawn [9–16]. In earlier year, Powell [17] first proved the global convergence of the standard BFGS method with inexact Wolfe line search for convex functions. Under the exact line search or some specific inexact line search, the BFGS method has the convergence property for convex minimization problems [18–21]. By contrast, for nonconvex problems, Mascaren [22] has presented an example to elaborate that the BFGS method and some Broyden-type methods may not be convergent under the exact line search. As such, with the Wolfe line searches, Dai [23] also proved that the BFGS method may fail to converge. To verify the global convergence of the BFGS method for general functions and to obtain a better Hessian approximation matrix of the objective function, Yuan and Wei [24] presented a modified quasi-Newton equation as follows:(5)Bk+1sk=y^k,where(6)y^k=yk+maxCk,0sk2sk,Ck=2fxk−fxk+αkdk+gxk+αkdk+gxkTsk,(7)Bk+1=Bk−BkskskTBkskTBksk+y^ky^kTskTy^k.In practice, the standard BFGS method has many qualities worth exploring and can effectively solve a class of unconstrained optimization problems.Here, two excellent properties of the BFGS method are introduced. One is the self-correcting quality, scilicet; if the current Hessian approximate inverse matrix estimates the curvature of the function incorrectly, then Hessian approximation matrixHk will correct itself within a few steps. The other interesting property is that small eigenvalues are better corrected than large ones [25]. Hence, one can see that, the efficiency of the BFGS algorithm is subject to the eigenvalues structure of the Hessian approximation matrix intensely. To improve the performances of the BFGS method, Oren and Luenberger [26] scaled the Hessian approximation matrix Bk, that is, they replaced Bk by τkBk, where τk is a self-scaling factor. Nocedal and Yuan [27] further studied the self-scaling BFGS method when τk=ykTsk/skTBksk. Based on the value of this τk, Al-Baali [28] introduced a simple modification: τk=min1,τk. The numerical experiments showed that the modified self-scaling BFGS method outperforms the unscaled BFGS method. Many other scaled BFGS methods with better properties will be enumerated.Formula 1. The general one-parameter scaled BFGS updating formula is(8)Bk+1=Bk−BkskskTBkskTBksk+γkykykTykTsk,where γk is a positive parameter, and it is diverse for the selection of the scaled factor γk, which is listed as follows.Choice A:(9)γk=2ykTskfxk−fxk+1+sTgk+1,where the value ofγk is given by Yuan [29], and with inexact line search, the global convergence of the scaled BFGS method with γk given by (9) is established for convex functions by Powell [30]. Ulteriorly, for general nonlinear functions, Yuan limited the value range of γk to [0.01, 100] to ensure the positivity of γk under the inexact line search and proved the global convergence of the scaled BFGS method in this form.Choice B:(10)γk=ykTskyk2,which is obtained as a solution of the problem:minsk−γkyk2. The scaled BFGS method based on this value of γk was introduced by Barzilai and Borwein [31] and was deemed the spectral scaled BFGS method. Cheng and Li [32] proved that the spectral scaled BFGS method is globally convergent under Wolfe line search with assuming the convexity of the minimizing function.Choice C:(11)γk=minykTskyk2+βk,1,whereβk>0 for k=0,1,…. Under the Wolfe line search (20) and (21), ykTsk>0 holds for k=0,1,…, which implies that γk computed by (11) is bounded away from zero, that is to say, 0<γk≤1. Therefore, in this instance, the large eigenvalues of Bk+1 given by (8) are shifted to the left [33].Formula 2. Proposed by Oren and Luenberger [26], this scaled BFGS method was the single parameter scaled of the first two items of the BFGS update and was defined as(12)Bk+1=δkBk−BkskskTBkskTBksk+ykykTykTsk,where δk is a positive parameter and is calculated as follows:(13)δk=ykTskskTBksk.The parameterδk assigned by (13) can make the structure of eigenvalue to inverse Hessian approximation more easily analyzed. Consequently, it is regarded as one of the best factors.Formula 3. In this method, the scaled parameters are selected to cluster the eigenvalues of the iteration matrixBk+1 and shift the large eigenvalues to the left. The update formula of the Hessian approximate matrix is computed as(14)Bk+1=δkBk−BkskskTBkskTBksk+γkykykTykTsk,where both δk and γk are positive parameters, and Andrei [34] preset them as the following values:(15)γk=minykTskyk2+sTgk+1,1,(16)δk=n−γkyk2/ykTskn−Bksk2/skTBksk.If the scaled parameters are bounded and line search is inexact, then this scaled BFGS algorithm is globally convergent for general functions. A large number of numerical experiments show that the double parameter scaled BFGS method withδk and γk given by (15) and (16) is more competitive than the standard BFGS method. In this paper, combining (7) and (14), we propose a new update formula of Bk+1 listed as follows:(17)Bk+1=δkBk−BkskskTBkskTBksk+γky^ky^kTy^kTsk,where y^k is determined by formula (6),(18)γk=y^kTsky^k2+sk2,(19)δk=n−γky^k2/y^kTskn−Bksk2/skTBksk.Some interesting properties of the BFGS-type method are inseparable from the weak Wolfe–Powell (WWP) line search:(20)fxk+αkdk≤fk+ξαkgkTdk,(21)gxk+αkdkTdk≥σgkTdk,where 0<ξ<σ<1. There are many research studies based on this line search [35–43]. To further develop the inexact line search, Yuan et al. present a new line search and call it Yuan-Wei-Lu (YWL) line search, which has the following form:(22)fxk+αkdk≤fk+ξαkgkTdk+αkmin−ξ1gkTdk,ξαk2dk2,(23)gxk+αkdkTdk≥σgkTdk+min−ξ1gkTdk,ξαkdk2,where ξ∈0,1/2, ξ1∈0,ξ, and σ∈ξ,1. The main work of this paper is to verify the global convergence of the modified scaled BFGS update (17) with γk and δk given by (18) and (19), respectively, under this line search. Abundant numerical results show that such a combination is appropriate for nonconvex functions.Our paper is organized as follows. The motivation and algorithm are introduced in the next section. In Section3, the convergence analysis of the modified two-parameter scaled BFGS method under Yuan-Wei-Lu line search is established. Section 4 is devoted to show the results of numerical experiments. Some conclusions are stated in the last section.


## 2. Motivation and Algorithm

Two crucial tools for analyzing properties of the BFGS method are the trace and the determinant of theBk+1 given by (4). Thus, the corresponding relations are enumerated as follows:(24)detBk+1=detBkI−skskTBkskTBksk+Bk−1ykykTykTsk,(25)trBk+1=trBk−Bksk2skTBksk+yk2skTyk.Applying the following existing relation in the study of Sun and Yuan [44],(26)detI+v1v2T+v3v4T=1+v1Tv21+v3Tv4−v1Tv4v2Tv3,where v1=−sk, v2=Bksk/sTBksk, v3=Bk−1yk, and v4=yk/ykTsk; we obtain(27)detBk+1=detBkykTskskTBksk.Obviously, the efficiency of the BFGS method depends on the eigenvalues structure of the Hessian approximation matrix, and the BFGS method is actually more affected by large eigenvalues than by small eigenvalues [25, 45, 46]. It can be seen that the second item on the right side of the formula (25) is negative. Therefore, it produces a shift of the eigenvalues of Bk+1 to the left. Thus, the BFGS method can modify large eigenvalues. Moreover, the third term on the right hand side of (25) being positive produces a shift of the eigenvalues of Bk+1 to the right. If this term is large, Bk+1 may have large eigenvalues too. Therefore, the eigenvalues of the Bk+1 can be corrected by scaling the corresponding items in (25), which is the main motivation for us to use the scaling BFGS method. In this paper, we scale the first two terms and the last term of the standard BFGS update formula with two different positive parameters and propose a new yk. In subsequent proof, we will propose some lemmas based on these two important tools to analyze the convergence of the modified scaled BFGS method. Then, an algorithm framework for solving the problem (1) will be built in Algorithm 1, which can be designed asAlgorithm 1: A modified two parameter scaled BFGS algorithm—MTPSBFGS.
Step 1: given an initial pointx0∈ℜn, an n×n symmetric positive definite matrix B0, ε>0 is sufficiently small and choose constants ξ∈0,1/2, ξ1∈0,ξ, and σ∈ξ,1. Set k=0.Step 2: ifgk≤ε, stop.Step 3: obtain a search directiondk by solving Bkdk+gk=0.Step 4: computeαk by Yuan-Wei-Lu line search conditions (22) and (23).Step 5: find the scaling factorsγk and δk by (18) and (19).Step 6: letxk+1=xk+αkdk. Update Bk+1 by (17).Step 7: letk=k+1, and go to Step 2.


## 3. Convergence Analysis

In Section3, the global convergence of Algorithm 1 will be established, and the following assumptions are useful in convergence analysis.Assumption 1.
(i)
The level setϒ=x∈ℜnfx≤fx0 is bounded(ii)
The functionfx is twice continuously differentiable and bounded from belowLemma 1.
IfBk is the positive definite, γk>0, and if αk is computed by (22) and (23), then Bk+1 given by (17) is an equally positive definite for all k.Proof.
The inequality (22) and (23) indicates that ykTsk>0. Using the definition of y^k, we obtain(28)y^kTsk=ykTsk+maxCk,0≥ykTsk>0.
For anyc≠0,(29)cTBk+1c=δkcTBkc−δkcTBkskskTBkcskTBksk+γkcTy^ky^kTcy^kTsk=δkcTBkc−δkcTBksk2skTBksk+γkcTy^k2y^kTsk≥γkcTy^k2y^kTsk>0,where the penultimate inequality follows, and(30)skTBkc2≤skTBkskcTBkc,forz≠0,which is obtained by the Cauchy–Schwarz inequality.Lemma 2.
Letδk be generated by (16) for k=0,1,…, then δk>0 and inclines to 1.Proof.
Observe the formula (19); after substituting δk, we can find that y^k2/y^k+sk is close to 1. Owing to the symmetry, positive definiteness, and nonsingularity of Bk+1, its eigenvalues λ1,…,λn is real and positive, and trBk=n. Hence, for i=1,…,n, λi>0 and ∑i=1nλi=n. Since B0s02=s0TB0s0, 0<Bksk2<1, and 0<skTBksk<1 for sufficiently large k, Bksk2, and skTBksk are roughly of the same order of magnitude, which shows that Bksk2/skTBksk≪n. To sum up, the relations γky^k2/y^kTsk≪n and Bksk2/skTBksk≪n are valid, namely for k=0,1,…, δk>0 and inclines to 1. The proof is completed.Remark 1.
Based on the conclusion of lemma, we can infer that for any integerj∈0,k, there exist two positive constants 0<δ<Λ satisfying δ<δkδk−1,…,δj<Λ.Lemma 3.
IfBk+1 is updated by (14), where γk and δk are determined by (18) and (16), then(31)trBk+1≤ΛtrB0+Λk+12,(32)∑i=0kBisi2siTBisi≤ΛδtrB0+k+12δ.Proof.
Considering (25), we have(33)trBk+1=δktrBk−δkBksk2skTBksk+γky^k2y^kTsk=δkδk−1trBk−1−δk−1Bk−1sk−12sk−1TBk−1sk−1+γk−1y^k−12y^k−1Tsk−1−δkBksk2skTBksk+γky^k2y^kTsk=⋯=δkδk−1,…,δ0trB0−δkδk−1,…,δ0B0s02sT0B0s0+δkδk−1,…,δ1γ0y^02y^0Ts0−δkδk−1,…,δ1B1s12s1TB1s1+δkδk−1,…,δ2γ1y^12y^1Ts1−⋯−δkδk−1Bk−1sk−12sk−1TBk−1sk−1+δkγk−1y^k−12y^k−1Tsk−1−δkBksk2skTBksk+γky^k2y^kTsk.
In addition,(34)γiy^i2y^iTsi=y^i2y^i2+si2≤12.
Therefore, by Remark1 and the above inequality, the formula (33) is transformed into(35)trBk+1≤ΛtrB0−∑i=0kδBisi2siTBisi+∑j=1kΛ+12≤ΛtrB0+Λk+12,which implies (31). From the positive definiteness of Bk+1, (32) also holds. The proof is completed.Lemma 4.
Considerγk≥s and δk≥q for all k, where s and t are constants. Then, there exists a positive constant h such that(36)∏i=0kαi≥hk,for all k sufficiently large.Proof.
Utilizing the identity (26) and taking the determinant on both sides of the formula (14) with γk and δk computed as in (18) and (16), we have(37)detBk+1=detδkBkI−skskTBkskTBksk+γkδkBk−1y^ky^kTy^kTsk=detδkBkdetI−skBkskTskTBksk+γkδkBk−1y^ky^kTy^kTsk=δkndetBkγkδky^kTsksTBksk=δkn−1γky^kTskskTBkskδk−1n−1γk−1y^k−1Tsk−1sk−1TBk−1sk−1detBk−1=δkn−1γky^kTskskTBkskδk−1n−1γk−1y^k−1Tsk−1sk−1TBk−1sk−1,…,δ0n−1γ0y^0Ts0s0TB0s0detB0=∏i=0kδin−1γiy^iTsisiTBisidetB0≥detB0∏i=0kqn−1s1−σαi=detB0qn−1k+1sk+11−σk+1∏i=0k1αi,where the penultimate inequality follows siTBisi=−αisiTgi, y^iTsi≥−1−σsiTgi, γi≥s, and δi≥q for all i. Furthermore, by detBk+1≤1/ntrBk+1n and Lemma 4, we obtain(38)detBk+1≤1nΛtrB0+Λk+12n.
Therefore,(39)∏i=0kαi≥detB0qn−1k+1sk+11−σk+1detBk+1≥detB0qn−1k+1sk+11−σk+11/nΛtrB0+Λk+1/2n.
Supposek is sufficiently large, (39) implies (36). The proof is completed.Theorem 1.
If the sequencexk is obtained by Algorithm 1, then(40)liminfk⟶∞gk=0.Proof.
The proof by contradiction is used to prove (40) holds. Suppose that gk>F>0. By Yuan-Wei-Lu line search (22) and fx bounded below, we obtain(41)fk−fxk+αkdk≥−ξαkgkTdk−αkmin−ξ1gkTdk,ξαk2dk2≥−ξ−ξ1αkgkTdk.
Adding the abovementioned inequalities fromk=0 to ∞ and utilizing Assumption 1 (ii), we have(42)∑k=0∞−skTgk<∞.
From Assumption1 (ii) and (42), we have(43)∞>∑k=0∞−skTgk=∑k=0∞1αkskTBksk=∑k=0∞gkBkskskTBksk=∑k=0∞skTBkskBkskgkαkgkBksk=∑k=0∞gk2αkskTBkskBksk2≥F2∑k=0∞αkskTBkskBksk2.
Based on this, given a constantΦ>0, there is a positive integer k0>0 satisfying(44)c∏k=k0+1k0+cαkskTBkskBksk21/c≤∏k=k0+1k0+cαkskTBkskBksk2≤Φ,where c is any positive integer, and the first inequality follows the geometric inequality. Moreover, by Lemma 4, we obtain(45)∏k=k0+1k0+cαk1/c≤Φc∏k=k0+1k0+cBksk2skTBksk1/c≤Φc2∑k=0k0+cBksk2skTBksk≤Φc2δΛtrB0+Λk0+c+12.
Consideringc⟶∞, the above formula and formula (39) are contradictory. Thus, (40) is valid. The proof is completed.


## 4. Numerical Results

In this section, numerical results of Algorithm1 are reported, and the following methods were compared: (i) MTPSBFGS method (Bk+1 is updated by (17) with γk and δk given by (18) and (19)). (ii) SBFGS method (Bk+1 is updated by (14) with γk and δk given by (11) and (16)).


### 4.1. General Unconstrained Optimisation Problems

Tested problems: a total of 74 test questions, listed in Table1 and derived from the studies by Bongartz et al. and More et al. [47, 48].Parameters: Algorithm1 runs with δ=0.2, δ1=0.15, σ=0.85, βk=10−17, and B0=I.Dimensionality: the algorithm is tested in the following three dimensions: 300, 900, and 2700.Himmelblau stop rule [49]: if fxk>e1, then set S1=fxk−fxk+1 or fxk−fxk+1/fxk. The iterations are stopped if gx<ε or S1<e2 holds, where e1=e2=10−5 and ϵ=10−6.Experiment environment: all programs are written in MATLAB R2014a and run on a PC with an Inter(R) Core(TM) i5-4210U CPU at 1.70 GHz, 8.00 GB of RAM, and the Windows 10 operating system.Symbol representation: No.: the test problem number. CPU time: the CPU time in seconds.NI: the number of iterations.  NFG: the total number of function and gradient evaluations.Image description: Figures1–3 show the profiles for CPU time, NI, and NFG, and Tables 2–6 provide the detail numerical results. From these figures and tables, it is obvious that the MTPSBFGS method possesses better numerical performance between these two methods, that is, the proposed modified scaled BFGS method is reasonable and feasible. The specific reasons for good performance are stated as follows. The parameter scaling the first two terms of the standard BFGS update is determined to cluster the eigenvalues of this matrix, and the parameter scaling the third term is determined to reduce its large eigenvalues, thus obtaining a better distribution of them.Table 1
The test problems.
No.Test problem1Extended Freudenstein and Roth function2Extended trigonometric function3Extended Rosenbrock function4Extended White and Holst function5Extended Beale function6Extended penalty function7Perturbed quadratic function8Raydan 1 function9Raydan 2 function10Diagonal 1 function11Diagonal 2 function12Diagonal 3 function13Hager function14Generalized tridiagonal 1 function15Extended tridiagonal 1 function16Extended three exponential terms function17Generalized tridiagonal 2 function18Diagonal 4 function19Diagonal 5 function20Extended Himmelblau function21Generalized PSC1 function22Extended PSC1 function23Extended Powell function24Extended block diagonal BD1 function25Extended Maratos function26Extended Cliff function27Quadratic diagonal perturbed function28Extended Wood function29Extended Hiebert function30Quadratic function QF1 function31Extended quadratic penalty QP1 function32Extended quadratic penalty QP2 function33A quadratic function QF2 function34Extended EP1 function35Extended tridiagonal 2 function36BDQRTIC function (CUTE)37TRIDIA function (CUTE)38ARWHEAD function (CUTE)39NONDIA function (CUTE)40NONDQUAR function (CUTE)41DQDRTIC function (CUTE)42EG2 function (CUTE)43DIXMAANA function (CUTE)44DIXMAANB function (CUTE)45DIXMAANC function (CUTE)46DIXMAANE function (CUTE)47Partial perturbed quadratic function48Broyden tridiagonal function49Almost perturbed quadratic function50Tridiagonal perturbed quadratic function51EDENSCH function (CUTE)52VARDIM function (CUTE)53STAIRCASE S1 function54LIARWHD function (CUTE)55DIAGONAL 6 function56DIXON3DQ function (CUTE)57DIXMAANF function (CUTE)58DIXMAANG function (CUTE)59DIXMAANH function (CUTE)60DIXMAANI function (CUTE)61DIXMAANJ function (CUTE)62DIXMAANK function (CUTE)63DIXMAANL function (CUTE)64DIXMAAND function (CUTE)65ENGVAL1 function (CUTE)66FLETCHCR function (CUTE)67COSINE function (CUTE)68Extended DENSCHNB function (CUTE)69Extended DENSCHNF function (CUTE)70SINQUAD function (CUTE)71BIGGSB1 function (CUTE)72Partial perturbed quadratic PPQ2 function73Scaled quadratic SQ1 function74Scaled quadratic SQ2 functionFigure 1
Performance profiles of these methods (CPU time).Figure 2
Performance profiles of these methods (NI).Figure 3
Performance profiles of these methods (NFG).Table 2
The numerical results for problems 1–17.
MTPSBFGS-YWLSBFGS-WWPNo.DimNINFGCPU timeNINFGCPU time130029630.312525570.3125190024565.85937523545.9687512700224886.93752967135.68752300501140.59375461020.529005111412.8906255011213.5156252270053120217.9062553122254.753300501370.515625471200.539007521517.593756316716.753270043135184.562560166280.48437543001043701.25621760.7549008725822.453125381099.18754270067179308.312550149236.984375530018480.2187522580.296875590018454.562520465.17187552700204590.252358106.9843756300681520.828125681520.79687569006915818.3756915818.406256270085192405.8437585192410.7656257300761540.8125761540.875790013326836.687513326836.84375727002324661158.7343752314641151.625830022490.20312526540.265625890025556.51562525556.421875827002555118.6406252555116.85937593007160.062512260.10937599007161.54687512262.843759270081831.96875122649.0468751030029029010900290.0625290.0625102700290.25290.2511300751940.92187546940.59375119009527226.3593756613418.48437511270062019.87597196472.3906251230011240.12511240.1093751290013283.45312513283.296875122700132860.34375132858.406251330011250.12510230.125139008231.92187510262.46875132700199488.65625199688.71875143008200.1258200.15625149007181.7031257181.70312514270071827.687571827.4218751530019430.35937522490.406251590025577.125398211.0781251527002555119.406254186198.203125163009210.10937510230.0625169008181.9218759212.15625162700112449.359375102243.0468751730033730.42187532750.3906251790023495.98437523495.81251727002553115.8906252553112.984375Table 3
The numerical results for problems 18–34.
MTPSBFGS-YWLSBFGS-WWPNo.DimNINFGCPU timeNINFGCPU time1830031003100189003100.531253100.51827003109.093753108.751930031003100.0625199003100.531253100.4843751927003108.5781253108.4218752030033710.3437532690.3593752090012312.23437512312.171875202700123544.5468754393191.31252130025560.2812534740.3906252190025566.70312535769.2656252127002658124.4843753678170.34375223008300.1093758310.125229008311.90625831222270083133.51562583133.3593752330034850.359375521090.562523900398910.656255111713.687523270047111233.6562547112223.7187524300331620.296875291450.23437524900141111.03125371716.8906252427001411115.343751511424.23437525300902621.06251273481.52590012334633.7656258825723.70312525270056139270.70312597284463.60937526300561340.640625561340.609375269006515217.3593756515217.29687526270061146292.54687561146287.25273006160.062561602790011312.7511312.65625272700164575.3125174479.6718752830028630.312527610.2968752890028637.3437527626.9218752827002561119.52561117.265625293004170.06254150.046875299004170.68754170.8281252927004179.4843754179.5312530300931881.203125931881.0468753090016433045.9687516633446.8906253027002955921476.906252945901474.968753130023520.2187523520.218753190027626.82812527626.843753127002864126.7343752864126.4218753230022460.2812522460.253290020445.17187520445.031253227004798219.5156254798218.78125333005110.06255110.062533900490.625490.59375332700377.421875377.3437534300370.062537034900370.53125370.53427004813.2031254813.234375Table 4
The numerical results for problems 35–51.
MTPSBFGS-YWLSBFGS-WWPNo.DimNINFGCPU timeNINFGCPU time35300480480359007141.593757141.59375352700112246.875112246.406253630024590.35937526640.468753690023666.35937520585.59375362700184982.359375194685.5625373001362751.656251362751.68753790023547367.4062523547367.3593753727004418862240.0156254428882234.093753830012270.12512270.06253890012262.812512262.921875382700153364.90625153364.656253930037800.4062537800.4687539900438910.890625439111.2656253927002652116.7031252652116.0781254030053213297.40625958192512.96875409005461364150.92187510002008274.562540270064416053124.65625100020144810.2968754130018410.187520450.18754190019434.82812519434.734375412700194385.0625194384.8754230019650.1562516570.078125429004210.0468754210.0468754227004210.5781254210.5156254330022480.26562525540.2343754390023505.8437527586.9843754327002554114.3281252962133.781254430038800.45312539820.5468754490036769.703125439011.54427003982180.4531254696212.1254530017400.17187518420.281254590017404.26562518424.65625452700184280.171875194485.09375463001042551.5625601260.8754690014135441.2031258718024.796875462700164418829.3125116238586.2968754730037800.73437536780.7187547900449514.640625449514.78125472700133164.21875133163.93754830026520.29687526520.312548900489612.890625489612.890625482700224799.546875224799.9687549300761540.953125761540.8593754990013326837.20312513427037.593754927002324661161.1093752344701176.92187550300761541.234375751521.3281255090013226638.85937513226638.531255027002314641165.187523246611705130023480.29687523480.31255190023485.89062523485.8593755127002348102.4843752348103.453125Table 5
The numerical results for problems 52–68.
MTPSBFGS-YWLSBFGS-WWPNo.DimNINFGCPU timeNINFGCPU time52300872000.875872001.06255290010323627.687510323627.875522700118270566.65625118270567.82812553300938237512.093753887784.6718755390010002537282.37510002002280.203125532700100025395006.875100020025001.9843755430031720.32812535880.390625549004210710.812524656.093755427002367102.752769121.75553009200.12518380.2656255590010222.23437520424.921875552700112446.3125214492.390625563001000260713.031253757504.56255690010002540268.312510002000277.515625562700100025394518.96875100020004637.546875573001072601.578125591240.796875579009923628.1406258517624.1562557270063149313.140625105216522.73437558300972331.3125691440.8906255890012029233.843759920427.828125582700144344717.328125117240583.0781255930024730.25761690.8906255990027727.29687527717.2968755927003178148.62579173389.4375603001092601.484375601260.7968756090013233837.4843758718024.359375602700176434882.109375116238581.953125613001042461.53125591240.796875619009622526.6093758517624.187561270066154324.140625105216521.9375623001042591.390625611460.8125629008923225.2656259922027.625622700126314623.578125105226521.1875633001433622.0468751473082.046875639009725927.5937517336549.28125632700186465933.51994221005.093756430040880.5312545980.5781256490028627.07812532708.2968756427003066135.656253372150.0156256530022480.35937522480.43756590019455.04687519455.1875652700184079.125184080.76562566300611123311.171875618123811.68756690010002003284.812510002002286.65625662700100020034583.015625100020024587.29687567300621062106790012330.2512330.2187567270010291.20312513591.4218756830024500.23437529600.3281256890025526.45312531648.3756827002756126.43753368156.328125Table 6
The numerical results for problems 69–74.
MTPSBFGS-YWLSBFGS-WWPNo.DimNINFGCPU timeNINFGCPU time6930026560.26562525540.218756990028607.54687525546.7343756927002962136.4218752554119.257030031840.530900.437570900401031132888.468757027003391146.76562553122245.71875713003428944.1718751903812.2031257190010002572617.343755341069145.265625712700100025917501.1875100020014617.703125723001243132.531251092842.2656257290028376294.0625311781107.89062572270084321284629.2587121634782.062573300951921.0625951921.1257390016833846.98437516934046.7656257327002965941477.0468752925861462.718757430037760.37536740.34375749005010213.406255010213.48437574270081164396.39062581164399.5625


### 4.2. Muskingum Model in Engineering Problems

In this subsection, we present the Muskingum model, and it has the following form:Muskingum model [50]:(46)minfx1,x2,x3=∑i=1n−11−Δt6x1x2Ii+1+1−x2Qi+1x3−1−Δt6x1x2Ii+1−x2Qix3−Δt2Ii−Qi+Δt21−Δt3Ii+1−Qi+12,whose symbolic representation is as follows: x1 is the storage time constant, x2 is the weight coefficient, x3 is an extra parameter, Ii is the observed inflow discharge, Qi is the observed outflow discharge, n is the total time, and Δt is the time step at time tii=1,2,…,n.The observed data of the experiment are obtained from the process of flood runoff from Chenggouwan and Linqing of Nanyunhe in the Haihe Basin, Tianjin, China. Select the initial pointx=0,1,1T and the time step Δt=12h. The concrete values of Ii and Qi for the years 1960, 1961, and 1964 are listed in [51]. The test results are presented in Table 7.Table 7
Results of the three algorithms.
Algorithmx1x2x3BFGS [52]10.81560.98261.0219HIWO [50]13.28130.80010.9933MTPSBFGS11.18491.00000.9996Figures4–6 and Table 7 imply the following three conclusions: (i) based on the Muskingum model, the efficiency of the MTPSBFGS method is wonderful, and numerical performance of these three algorithms is fantastic. (ii) Compared to other similar methods, the final points (x1, x2, and x3) of the MTPSBFGS method are competitive. (iii) Due to the endpoints of these three methods being different, the Muskingum model may have more approximation optimum points.Figure 4
Performance of Algorithm1 in 1960.Figure 5
Performance of Algorithm1 in 1961.Figure 6
Performance of Algorithm1 in 1964.


## 4.1. General Unconstrained Optimisation Problems

Tested problems: a total of 74 test questions, listed in Table1 and derived from the studies by Bongartz et al. and More et al. [47, 48].Parameters: Algorithm1 runs with δ=0.2, δ1=0.15, σ=0.85, βk=10−17, and B0=I.Dimensionality: the algorithm is tested in the following three dimensions: 300, 900, and 2700.Himmelblau stop rule [49]: if fxk>e1, then set S1=fxk−fxk+1 or fxk−fxk+1/fxk. The iterations are stopped if gx<ε or S1<e2 holds, where e1=e2=10−5 and ϵ=10−6.Experiment environment: all programs are written in MATLAB R2014a and run on a PC with an Inter(R) Core(TM) i5-4210U CPU at 1.70 GHz, 8.00 GB of RAM, and the Windows 10 operating system.Symbol representation: No.: the test problem number. CPU time: the CPU time in seconds.NI: the number of iterations.  NFG: the total number of function and gradient evaluations.Image description: Figures1–3 show the profiles for CPU time, NI, and NFG, and Tables 2–6 provide the detail numerical results. From these figures and tables, it is obvious that the MTPSBFGS method possesses better numerical performance between these two methods, that is, the proposed modified scaled BFGS method is reasonable and feasible. The specific reasons for good performance are stated as follows. The parameter scaling the first two terms of the standard BFGS update is determined to cluster the eigenvalues of this matrix, and the parameter scaling the third term is determined to reduce its large eigenvalues, thus obtaining a better distribution of them.Table 1
The test problems.
No.Test problem1Extended Freudenstein and Roth function2Extended trigonometric function3Extended Rosenbrock function4Extended White and Holst function5Extended Beale function6Extended penalty function7Perturbed quadratic function8Raydan 1 function9Raydan 2 function10Diagonal 1 function11Diagonal 2 function12Diagonal 3 function13Hager function14Generalized tridiagonal 1 function15Extended tridiagonal 1 function16Extended three exponential terms function17Generalized tridiagonal 2 function18Diagonal 4 function19Diagonal 5 function20Extended Himmelblau function21Generalized PSC1 function22Extended PSC1 function23Extended Powell function24Extended block diagonal BD1 function25Extended Maratos function26Extended Cliff function27Quadratic diagonal perturbed function28Extended Wood function29Extended Hiebert function30Quadratic function QF1 function31Extended quadratic penalty QP1 function32Extended quadratic penalty QP2 function33A quadratic function QF2 function34Extended EP1 function35Extended tridiagonal 2 function36BDQRTIC function (CUTE)37TRIDIA function (CUTE)38ARWHEAD function (CUTE)39NONDIA function (CUTE)40NONDQUAR function (CUTE)41DQDRTIC function (CUTE)42EG2 function (CUTE)43DIXMAANA function (CUTE)44DIXMAANB function (CUTE)45DIXMAANC function (CUTE)46DIXMAANE function (CUTE)47Partial perturbed quadratic function48Broyden tridiagonal function49Almost perturbed quadratic function50Tridiagonal perturbed quadratic function51EDENSCH function (CUTE)52VARDIM function (CUTE)53STAIRCASE S1 function54LIARWHD function (CUTE)55DIAGONAL 6 function56DIXON3DQ function (CUTE)57DIXMAANF function (CUTE)58DIXMAANG function (CUTE)59DIXMAANH function (CUTE)60DIXMAANI function (CUTE)61DIXMAANJ function (CUTE)62DIXMAANK function (CUTE)63DIXMAANL function (CUTE)64DIXMAAND function (CUTE)65ENGVAL1 function (CUTE)66FLETCHCR function (CUTE)67COSINE function (CUTE)68Extended DENSCHNB function (CUTE)69Extended DENSCHNF function (CUTE)70SINQUAD function (CUTE)71BIGGSB1 function (CUTE)72Partial perturbed quadratic PPQ2 function73Scaled quadratic SQ1 function74Scaled quadratic SQ2 functionFigure 1
Performance profiles of these methods (CPU time).Figure 2
Performance profiles of these methods (NI).Figure 3
Performance profiles of these methods (NFG).Table 2
The numerical results for problems 1–17.
MTPSBFGS-YWLSBFGS-WWPNo.DimNINFGCPU timeNINFGCPU time130029630.312525570.3125190024565.85937523545.9687512700224886.93752967135.68752300501140.59375461020.529005111412.8906255011213.5156252270053120217.9062553122254.753300501370.515625471200.539007521517.593756316716.753270043135184.562560166280.48437543001043701.25621760.7549008725822.453125381099.18754270067179308.312550149236.984375530018480.2187522580.296875590018454.562520465.17187552700204590.252358106.9843756300681520.828125681520.79687569006915818.3756915818.406256270085192405.8437585192410.7656257300761540.8125761540.875790013326836.687513326836.84375727002324661158.7343752314641151.625830022490.20312526540.265625890025556.51562525556.421875827002555118.6406252555116.85937593007160.062512260.10937599007161.54687512262.843759270081831.96875122649.0468751030029029010900290.0625290.0625102700290.25290.2511300751940.92187546940.59375119009527226.3593756613418.48437511270062019.87597196472.3906251230011240.12511240.1093751290013283.45312513283.296875122700132860.34375132858.406251330011250.12510230.125139008231.92187510262.46875132700199488.65625199688.71875143008200.1258200.15625149007181.7031257181.70312514270071827.687571827.4218751530019430.35937522490.406251590025577.125398211.0781251527002555119.406254186198.203125163009210.10937510230.0625169008181.9218759212.15625162700112449.359375102243.0468751730033730.42187532750.3906251790023495.98437523495.81251727002553115.8906252553112.984375Table 3
The numerical results for problems 18–34.
MTPSBFGS-YWLSBFGS-WWPNo.DimNINFGCPU timeNINFGCPU time1830031003100189003100.531253100.51827003109.093753108.751930031003100.0625199003100.531253100.4843751927003108.5781253108.4218752030033710.3437532690.3593752090012312.23437512312.171875202700123544.5468754393191.31252130025560.2812534740.3906252190025566.70312535769.2656252127002658124.4843753678170.34375223008300.1093758310.125229008311.90625831222270083133.51562583133.3593752330034850.359375521090.562523900398910.656255111713.687523270047111233.6562547112223.7187524300331620.296875291450.23437524900141111.03125371716.8906252427001411115.343751511424.23437525300902621.06251273481.52590012334633.7656258825723.70312525270056139270.70312597284463.60937526300561340.640625561340.609375269006515217.3593756515217.29687526270061146292.54687561146287.25273006160.062561602790011312.7511312.65625272700164575.3125174479.6718752830028630.312527610.2968752890028637.3437527626.9218752827002561119.52561117.265625293004170.06254150.046875299004170.68754170.8281252927004179.4843754179.5312530300931881.203125931881.0468753090016433045.9687516633446.8906253027002955921476.906252945901474.968753130023520.2187523520.218753190027626.82812527626.843753127002864126.7343752864126.4218753230022460.2812522460.253290020445.17187520445.031253227004798219.5156254798218.78125333005110.06255110.062533900490.625490.59375332700377.421875377.3437534300370.062537034900370.53125370.53427004813.2031254813.234375Table 4
The numerical results for problems 35–51.
MTPSBFGS-YWLSBFGS-WWPNo.DimNINFGCPU timeNINFGCPU time35300480480359007141.593757141.59375352700112246.875112246.406253630024590.35937526640.468753690023666.35937520585.59375362700184982.359375194685.5625373001362751.656251362751.68753790023547367.4062523547367.3593753727004418862240.0156254428882234.093753830012270.12512270.06253890012262.812512262.921875382700153364.90625153364.656253930037800.4062537800.4687539900438910.890625439111.2656253927002652116.7031252652116.0781254030053213297.40625958192512.96875409005461364150.92187510002008274.562540270064416053124.65625100020144810.2968754130018410.187520450.18754190019434.82812519434.734375412700194385.0625194384.8754230019650.1562516570.078125429004210.0468754210.0468754227004210.5781254210.5156254330022480.26562525540.2343754390023505.8437527586.9843754327002554114.3281252962133.781254430038800.45312539820.5468754490036769.703125439011.54427003982180.4531254696212.1254530017400.17187518420.281254590017404.26562518424.65625452700184280.171875194485.09375463001042551.5625601260.8754690014135441.2031258718024.796875462700164418829.3125116238586.2968754730037800.73437536780.7187547900449514.640625449514.78125472700133164.21875133163.93754830026520.29687526520.312548900489612.890625489612.890625482700224799.546875224799.9687549300761540.953125761540.8593754990013326837.20312513427037.593754927002324661161.1093752344701176.92187550300761541.234375751521.3281255090013226638.85937513226638.531255027002314641165.187523246611705130023480.29687523480.31255190023485.89062523485.8593755127002348102.4843752348103.453125Table 5
The numerical results for problems 52–68.
MTPSBFGS-YWLSBFGS-WWPNo.DimNINFGCPU timeNINFGCPU time52300872000.875872001.06255290010323627.687510323627.875522700118270566.65625118270567.82812553300938237512.093753887784.6718755390010002537282.37510002002280.203125532700100025395006.875100020025001.9843755430031720.32812535880.390625549004210710.812524656.093755427002367102.752769121.75553009200.12518380.2656255590010222.23437520424.921875552700112446.3125214492.390625563001000260713.031253757504.56255690010002540268.312510002000277.515625562700100025394518.96875100020004637.546875573001072601.578125591240.796875579009923628.1406258517624.1562557270063149313.140625105216522.73437558300972331.3125691440.8906255890012029233.843759920427.828125582700144344717.328125117240583.0781255930024730.25761690.8906255990027727.29687527717.2968755927003178148.62579173389.4375603001092601.484375601260.7968756090013233837.4843758718024.359375602700176434882.109375116238581.953125613001042461.53125591240.796875619009622526.6093758517624.187561270066154324.140625105216521.9375623001042591.390625611460.8125629008923225.2656259922027.625622700126314623.578125105226521.1875633001433622.0468751473082.046875639009725927.5937517336549.28125632700186465933.51994221005.093756430040880.5312545980.5781256490028627.07812532708.2968756427003066135.656253372150.0156256530022480.35937522480.43756590019455.04687519455.1875652700184079.125184080.76562566300611123311.171875618123811.68756690010002003284.812510002002286.65625662700100020034583.015625100020024587.29687567300621062106790012330.2512330.2187567270010291.20312513591.4218756830024500.23437529600.3281256890025526.45312531648.3756827002756126.43753368156.328125Table 6
The numerical results for problems 69–74.
MTPSBFGS-YWLSBFGS-WWPNo.DimNINFGCPU timeNINFGCPU time6930026560.26562525540.218756990028607.54687525546.7343756927002962136.4218752554119.257030031840.530900.437570900401031132888.468757027003391146.76562553122245.71875713003428944.1718751903812.2031257190010002572617.343755341069145.265625712700100025917501.1875100020014617.703125723001243132.531251092842.2656257290028376294.0625311781107.89062572270084321284629.2587121634782.062573300951921.0625951921.1257390016833846.98437516934046.7656257327002965941477.0468752925861462.718757430037760.37536740.34375749005010213.406255010213.48437574270081164396.39062581164399.5625


## 4.2. Muskingum Model in Engineering Problems

In this subsection, we present the Muskingum model, and it has the following form:Muskingum model [50]:(46)minfx1,x2,x3=∑i=1n−11−Δt6x1x2Ii+1+1−x2Qi+1x3−1−Δt6x1x2Ii+1−x2Qix3−Δt2Ii−Qi+Δt21−Δt3Ii+1−Qi+12,whose symbolic representation is as follows: x1 is the storage time constant, x2 is the weight coefficient, x3 is an extra parameter, Ii is the observed inflow discharge, Qi is the observed outflow discharge, n is the total time, and Δt is the time step at time tii=1,2,…,n.The observed data of the experiment are obtained from the process of flood runoff from Chenggouwan and Linqing of Nanyunhe in the Haihe Basin, Tianjin, China. Select the initial pointx=0,1,1T and the time step Δt=12h. The concrete values of Ii and Qi for the years 1960, 1961, and 1964 are listed in [51]. The test results are presented in Table 7.Table 7
Results of the three algorithms.
Algorithmx1x2x3BFGS [52]10.81560.98261.0219HIWO [50]13.28130.80010.9933MTPSBFGS11.18491.00000.9996Figures4–6 and Table 7 imply the following three conclusions: (i) based on the Muskingum model, the efficiency of the MTPSBFGS method is wonderful, and numerical performance of these three algorithms is fantastic. (ii) Compared to other similar methods, the final points (x1, x2, and x3) of the MTPSBFGS method are competitive. (iii) Due to the endpoints of these three methods being different, the Muskingum model may have more approximation optimum points.Figure 4
Performance of Algorithm1 in 1960.Figure 5
Performance of Algorithm1 in 1961.Figure 6
Performance of Algorithm1 in 1964.


## 5. Conclusion

A modified two parameter scaled BFGS method and the Yuan-Wei-Lu line search technology are introduced in this paper. By scaling the first two terms and the third term of the standard BFGS method with different positive parameters, a new two parameter scaled BFGS method is proposed. In this method, the new value ofyk is given to guarantee better properties of the new scaled BFGS method. With Yuan-Wei-Lu line search, the proposed BFGS method is globally convergent. Numerical results indicate that the modified two parameter scaled BFGS method outperforms the standard BFGS method and even the same type of the BFGS method. As for the longer-term work, there are several points to consider: (1) are there some new values of γk, δk, and yk that make the BFGS method based on the update formula (17) perform better? (2) Whether the new scaled method combined with other line search have also great theoretical results. (3) Some new engineering problems based on the BFGS-type method are worth studying.



---

*Source: 9280495-2020-08-26.xml*