# Convergence Analysis of an Improved BFGS Method and Its Application in the Muskingum Model

Authors: Tianshan Yang; Pengyuan Li; Xiaoliang Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The BFGS method is one of the most effective quasi-Newton algorithms for minimization-optimization problems. In this paper, an improved BFGS method with a modified weak Wolfe–Powell line search technique is used to solve convex minimization problems and its convergence analysis is established. Seventy-four academic test problems and the Muskingum model are implemented in the numerical experiment. The numerical results show that our algorithm is comparable to the usual BFGS algorithm in terms of the number of iterations and the time consumed, which indicates our algorithm is effective and reliable.


---

## Body

## 1. Introduction

With the development of the economy and society, a large number of optimization problems have been emerged in the fields of economic management, aerospace, transportation, national defense and so on. It is very necessary and meaningful for us to discuss, analyse the problems, and find some effective methods to solve them. Let us consider the optimization model:(1)minfxx∈ℜn,where f:ℜn⟶ℜ, f∈C2. To solve (1), the following iterative formula is widely used. Given the starting point x0, the iterative scheme is(2)xk+1=xk+αkdk,k∈0,1,2,…,where xk is the current iteration point, xk+1 is the next iteration point, αk is the step length, and dk is the search direction that is obtained by solving the quasi-Newton equation:(3)Bkdk+gk=0,where gk is the gradient ∇fxk of fx at the point xk, Bk is the quasi-Newton updating matrix or its approximation, and the sequence Bk satisfies the standard secant equation Bk+1sk=yk. The updating matrix of Bk can be defined by(4)Bk+1=Bk−BkskskTBkskTBksk+ykykTskTyk,where yk=gk+1−gk, sk=xk+1−xk, and B0 is symmetric and positive definite.Formula (4) is the famous standard BFGS update formula, which is one of the most effective quasi-Newton methods. For a convex function, using exact line search or some special inexact line search, the global convergence (see [1, 2]) and superlinear convergence (see [3, 4]) of the BFGS method were obtained. For general functions, the BFGS method may fail under inexact line search techniques. This fact has been proven by Dai [5], and Mascarenhas [6] has also proven that the BFGS method is not convergent, even under the exact line search techniques. Although the convergence of the BFGS method under general nonconvex functions has some shortcomings, its high efficiency and great numerical stability have motivated many scholars [7–12] to study and improve the BFGS method. The improvements achieved by scholars are as follows.Formula 1.
(see [7]). The BFGS update formula is modified by(5)Bk+1=Bk−BkskskTBkskTBksk+δkTδkskTδk,where δk=yk+max0,−skTyk/sk2+ϕgksk and function ϕ:ℜ⟶ℜ satisfies (i) ϕt>0 for all t>0; (ii) ϕt=0 if and only if t=0; (iii) if t is in a bounded set, ϕt is bounded. Li and Fukushima discussed its global convergence without the convexity assumption on f.Formula 2.
(see [8]) The BFGS update formula is modified by(6)Bk+1=Bk−BkskskTBkskTBksk+ykm∗ykm∗TskTykm∗,where ykm∗=yk+ρk/sk2sk and ρk=2fxk−fxk+αkdk+gxk+αkdk+gxkTsk. Moreover, scholars [8, 13] have proven that this method is better than the original BFGS method.Formula 3.
(see [9]) The BFGS update formula is modified by(7)Bk+1=Bk−BkskskTBkskTBksk+ykl∗ykl∗TskTykl∗,where ykl∗=yk+A¯ksk and A¯k=6fxk−fxk+αkdk+3gxk+αkdk+gxkTsk/sk2. According to A¯k, it is clear that the method contains both gradient and function value information. In addition, the modulated quasi-Newton method with superlinear convergence constructed by formula 3 is studied in [9].Formula 4.
(see [14]) The BFGS update formula is modified by(8)B˜k+1=B˜k−B˜kskskTB˜kskTB˜ksk+yk∗yk∗TskTyk∗,where yk∗=yk+Ak∗sk and Ak∗=maxA¯k,0. The global convergence of the improved BFGS method (MBFGS) is discussed by Li et al. [14]. Meanwhile, they also compared the three methods in numerical experiments. The results show that the algorithm based on this method is superior to the other three methods.
In many optimization algorithms, scholars often use the weak Wolfe–Powell (WWP) line search technique to find the step lengthαk. The WWP line search technique is determined by(9)fxk+αkdk≤fk+jαkgkTdk,gxk+αkdkTdk≥ρgkTdk,where j∈0,1/2, αk>0, and ρ∈j,1.
In order to get more interesting properties of WWP line search, many scholars have improved the line search technique. Yuan et al. [15] improved the WWP line search technique and studied the new line search technique that has global convergence in the BFGS and PRP methods. Their improved line search technique (MWWP) is formulated as follows:(10)fxk+αkdk≤fxk+βαkgkTdk+αkmin−β1gkTdk,βαkdk22,(11)gxk+αkdkTdk≥θgkTdk+min−β1gkTdk,βαkdk2,where β∈0,1/2, αk>0, β1∈0,β, and θ∈β,1. The detailed line search is elaborated in [15]. Some research results based on this improved line search can be found in [16, 17]. The above discussion motivate us to seek an improved BFGS method which may obtain better numerical performance.
In this article, we will discuss our work in the following sections. In Section2, using (8) and the MWWP line search technique, algorithms are constructed to solve optimization problems. In Section 3, we study convergence of the modified BFGS method. In Section 4, the numerical results of the algorithm are reported. In the last section, the conclusion is presented.


## 2. Algorithm

The corresponding modified BFGS algorithm is called Algorithm1 and can be presented as follows.Algorithm 1.
(i)
Step 1: choose an initial pointx0∈ℜn, ε∈0,1, β∈0,1/2, β__1∈0,β, and θ∈β,1. Given an initial n×n symmetric and positive definite matrix B˜0, set k=0.(ii)
Step 2: whengk≤ε, stop. Otherwise, take the next step.(iii)
Step 3: solveB˜kdk+gk=0 to obtain dk.(iv)
Step 4: the step lengthαk is determined by (10) and (11).(v)
Step 5: set a new iteration point ofxk+1=xk+αkdk. Update B˜k by (8).(vi)
Step 6: letk=k+1 and return to Step 2.Remark 1.
The step lengthαk, generated by the proposed new line search technique, has a great numerical performance. And the rationality proof of the MWWP line search has been given in [15].


## 3. Convergence Analysis

The global convergence analysis of the improved BFGS method will be introduced in this section, and the following assumptions are needed.Assumption 1.
(i)
The level set ofF0=xfx≤fx0 is bounded.(ii)
The objective functionfx is convex on F0.(iii)
fx is twice continuously differentiable and bounded below, with a Lipschitz continuous gradient function gx. It means that there exists a positive constant M, such that(12)gx−gy≤Mx−y,x,y∈Rn.
Next, we will give the global convergence. The positive definite ofB˜k is presented in the following lemma.Lemma 1.
Let the sequenceB˜k be generated by (8); then, the matrix B˜k is positive definite for all k.Proof.
Induction is used to prove the positive definiteness ofB˜k. For k=0, it is obvious that the matrix B˜0 is positive definite. For k>0, by B˜kdk+gk=0 and (11), we have(13)skTyk∗=skTyk+skTAk∗sk≥θgkTsk+αkmin−β1gkTdk,βαkdk2−skTgk+skTAk∗sk≥−1−θgkTsk>0,where the last inequality holds by −gkTdk=dkTB˜kdk>0 and min−β1gkTdk,βαkdk2≥0. Therefore, the matrix B˜k+1 is positive definite. The proof is completed.Lemma 2.
Let Assumption1 hold, and the sequence xk,αk,dk,gk is generated in the Algorithm 1. Then,(14)∑k=0∞gkTdk2dk2<∞.Proof.
By MWWP line search (8) and formula (12), we obtain(15)Mαkdk2≥gk+1−gkTdk≥θgkTdk+min−β1gkTdk,βαkdk2−gkTdk≥−1−θgkTdk.
Therefore, the following bound holds:(16)αk≥−1−θgkTdkMdk2.
By (10) and Assumption 1 (iii), we have(17)fxk−fxk+αkdk≥−βαkgkTdk−αkmin−β1gkTdk,βαkdk22≥−β−β1αkgkTdk.
Adding these inequalities fromk=0 to ∞, we obtain(18)∑k=0∞−αkgkTdk<∞.
Combining the above inequality with (16), we obtain (14). Therefore, Lemma 2 has been proven.Remark 2.
It is obvious that there are two values of themin−β1gkTdk,βαkdk2. Therefore, the MWWP line search has two situations. In this paper, we discuss the situation of min−β1gkTdk,βαkdk2=βαkdk2.Lemma 3.
Letmin−β1gkTdk,βαkdk2=βαkdk2 and Assumption 1 hold. Then, there exists a positive constant l1≥l2 such that(19)B˜ksk≤l1sk,(20)skTB˜ksk≥l2sk2,hold for at least t/2 values of k∈1,2,…,t with any positive integer t.Proof.
By theAk∗=maxA¯k,0, if A¯k≤0, then yk∗=yk. Lemma 3 holds (see [15]).
IfA¯k>0, then yk∗=yk+A¯ksk. It is similar to the result of Yuan and Wei [18]. According to the convexity of objective function fx, we obtain(21)fk−fk+1≥−gk+1Tsk,fk+1−fk≥gkTsk.
The above two inequalities and the definition ofA¯k indicate that(22)A¯k≤3skTyksk2.
Then, we obtain(23)yk∗=yk+A¯ksk≤yk+A¯ksk≤4yk.
Therefore, by the above analysis, it follows(24)yk∗2≤16yk2=16gk+1−gk2≤16M2sk2.
By the definition ofyk∗, it follows that(25)skTyk∗=skTyk+Ak∗sk≥−1−θgkTsk+αkmin−β1gkTdk,βαkdk2+skTAk∗sk≥βsk2.
Then, we have that(26)skTyk∗sk2≥β,yk∗2skTyk∗≤16M2β.
The proof of Theorem 2.1 of [2] implies that Lemma 3 holds.
Based on the above conclusions, the global convergence is analysed in the following theorem.Theorem 1.
If the conditions of Lemma3 hold, then we obtain(27)limk⟶∞infgk=0.Proof.
By Lemma2, we obtain(28)limk⟶∞gkTdk2dk2=0.
SinceB˜kdk+gk=0, we have(29)limk⟶∞dkTB˜kdk2dk2=0.
Combining (19) with (20), we obtain(30)0≤l22dk2≤dkTB˜kdk2dk2.
Thus,k⟶+∞, dk⟶0, and gk=−B˜kdk, and we obtain(31)l2dk≤gk≤l1dk.
Therefore, (27) holds. The proof is complete.


## 4. Numerical Results

In this section, we will study the numerical performance of the MBFGS-MWWP algorithm established in Section2. To verify the algorithm’s effectiveness, we divide the experiments into two parts: we first compare our algorithm with the standard BFGS method with the weak Wolfe–Powell line search technique (BFGS-WWP) in 74 academic problems listed in Table 1 with the dimension varying from 300 to 2700 and then apply our algorithm to the Muskingum engineering model.Table 1
The test problems.
N0Test 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 function


### 4.1. Unconstrained Optimisation Problems

In this section, we compare Algorithm1 with the BFGS-WWP algorithms for the 74 academic problems listed in Table 1. The codes are written with MATLAB R2014a and run on a PC with an Inter (R) Core (TM) i5-4210U CPU @ 1.70 GHz, 8.00 GB of RAM and the Windows 10 operating system, and the parameters are chosen as β=0.2, β1=0.15, θ=0.75, and ε=10−5. The numerical results and comparison are shown in Tables 2–6. The columns in Tables 2–6 have the following meaning:(i)
N0: the index of the tested problems(ii)
Dim: the dimension of the tested problem(iii)
NI: the iteration number consumed(iv)
NFG: the total number both of the gradient and the function value(v)
CPU time: the time consumed in corresponding algorithms in secondsTable 2
The numerical results for problems 1–17.
N0DimMBFGS-MWWPBFGS-WWPNINFGCPU timeNINFGCPU time13009260.12519261.062519007192.40637192.43751270072134.656172134.013123002795984.65632545474.005229006601381186.23127001489203.39422270071630.469171630.5030330062814718.734467614729.2969390010002429286.140610002598275.765632700100030865405.7969100029995390.2344430073316369.9219733161010.9375490010002371278.406310002421285.828142700100021105408.3906100021165375.0313530013390.187515450.2031590015464.031315463.812552700154674.1875154673.218863008330.09388330.1406690013493.484413493.06256270041710.500141710.390673001984012.56251984012.57817900409823112.9531409823111.65637270088317684735.796988317684768.6094830022480.406322480.3281890031668.359431668.51568270057118294.218857118292.781293006160.062513280.156399006161.406313283.26569270061624.7813143063.656310300290.031329010900290.0469290.0469102700290.1563290.15631130046940.609446940.5781119006713618.03126613419.002111270082200422.890697196533.46881230038780.531338780.546912900469412.7031469412.625312270066134340.437566134343.14061330014340.156214340.20311390015423.968815424.015613270049153257.421949151250.40631430011250.281311250.34381490010232.859410232.562514270061525.109461523.53131530013320.328113320.39061590014343.812514343.9219152700153772.0156153775.4844163007180.06257180.0938169006161.32816161.252116270061824.453161623.890617300981991.2656981991.3281179008818223.98488718023.328117270082170415.312582171405.2813Table 3
The numerical results for problems 18–34.
N0DimMBFGS-MWWPBFGS-WWPNINFGCPU timeNINFGCPU time183003100.03123100.0312189003100.54683100.48441827003109.34383109.003219300390.03123100.031219900390.54683100.53121927003910.17183109.62542030011320.18758270.06252090013552.468710291.8281202700164865.7812134045.453121300471220.5781501140.7187219005814116.21015012513.256721270058149295.171842108207.6562223006210.09377300.1093229006211.39067301.593722270062125.156273029.0781233001143931.85931133781.59372390015252342.890619062852.04682327002458541304.25212096931105.562524300943381.1562311610.2813249009336122.9531171271.93752427002412974.76562513679.43752530068618238.781273419089.70312590010003200280.968710002465272.875125270096928675167.4062100027915395.4062263004150.03124150.0312269004150.60934150.640626270041510.468141510.1093273007180.09377180.15632790013303.312513303.70312727002860139.20312860149.859328300882551.3593842451.48432890010328828.218710229527.3125282700131328694.8125128330669.3593293004150.03124150.0312299004150.65624150.421829270041510.39064156.2968303002074192.75212074192.828130900444893122.4375444893120.468730270086317284608.984386317284734.10933130011310.140611310.15623190013493.359313493.8281312700165879.8751165891.45313230013440.156213450.20313290012333.046812333.252132270072223367.953183235435.4687333004110.03124110.0312339004110.71874110.656233270041112.515641112.781234300390390.031234900390.5625390.512134270041014.718741014.2031Table 4
The numerical results for problems 35–51.
N0DimMBFGS-MWWPBFGS-WWPNINFGCPU timeNINFGCPU time353005130.06255130.0625359005131.09375131.078135270051319.593751318.109336300451180.8751451160.9375369004712213.59375514515.437536270064171324.656264167316.7968373002515073.56252515073.7031379005771159160.87515771159176.625137270086917414684.328186917414743.0937383005150.06255150.0625389005151.04685151.171838270051519.734351518.92183930019720.252219670.32813990023876.265621815.252139270034118173.112335120181.78124030048511627.218752010557.4375409005061162143.34377311468198.062540270052812702713.421882916644167.67184130012340.171812340.17184190012342.906212343.0468412700123456.5231123453.79684230018600.218716550.1875429004210.07814210.04684227004210.29684210.31254330015380.265615380.23434390018445.406218444.6875432700194694.0312204892.65624430029710.437527700.3752449004712013.09378320422.359344270087203443.703199224494.093745300561310.7812631460.9531459007517820.82819020925.484345270081190414.4218124265615.406246300701570.9375901961.671874690012127634.671811725832.5468462700174401916.87521994161049.3437473001102252.29681102252.37524790021944673.843721944668.98434727003467021940.34373467021948.343748300901831.6252901831.7031489007515720.56257515720.0468482700144291741.3751144291716.9375493001973992.67181973993.078149900422849117.1562422849116.656249270088217664726.187588217664725.7031503001853754.17181853754.031250900395795116.1562395795112.390650270085917204628.046885917204585.62515130024580.312524580.31255190021565.703130788.25235127003380163.78122772127.3593Table 5
The numerical results for problems 52–68.
N0DimMBFGS-MWWPBFGS-WWPNINFGCPU timeNINFGCPU time5230031303130.0468529003130.34373130.29685227003135.64063135.4062533003146344.10934048125.4063539009271860261.953110002004270.2188532700100020045316.6406100020025250.64065430025780.328124740.29695490028887.328128857.140654270033107166.218137116183.06255530010240.140620420.28125590011262.906221445.2187552700112650.96872348105.5123563003116263.78123547104.6252569009211846252.859310002002271.5312562700100020025193.1251100020004871.124157300771991.2187962321.4531579007291.64064014011.078157270073030.4531157565.859458300671440.8751731541.26565890010321429.843110321428.18755827002888124.14061964071044.9688593003150.03123150.03135990011582.812511583.265659270024111107.312524108109.109360300711660.9687791731.18756090013329542.203118238450.20316027001904331024.2812182388947.906261300681720.937526870.4375619007291.75219451.765661270073031.2812199082.3906623003598775.71813919086.3125629006251452182.96876181415168.562562270062214733372.6406156520809.6251633001573712.51561663912.65626390023657167.640626759274.890663270054112162961.687549311142569.2656643001984823.21312024853.21876490027662982.1562211125.42186427003129.93753129.140665300511141.0312481080.9062659005112215.42184210911.656265270055126290.484477179379.078166300527118710.2968534121110.18756690010002415294.625110002442285.8281662700100024945153.8281100025444975.5468673006210.031262106790010040821.328112330.156267270010290.906213590.98436830011260.187511260.20316890011263.218712283.5156682700122860.4375122852.7656Table 6
The numerical results for problems 69–74.
N0DimMBFGS-MWWPBFGS-WWPNINFGCPU timeNINFGCPU time69300431420.687526810.3752699006520017.890628897.593869270073222399.734334107170.4375703003588479.2031501510.9218709004415913.81257125019.28127027002637641469.703145152207.3438713001633322.03121633342.093871900483975147.3593488986130.2656712700100020005118.8751100020004951.73437230035800.828143940.7968729005812818.26565712618.187572270096208535.140698210531.1562733001332712.28121332711.70317390022545563.859322545560.25217327004719472572.96814438912325.015674300431120.7187431120.56257490018437357.359318437350.57817427002625291460.04682625291372.9375For intuitive effect, we adopt the performance technique in [19] to show the performance of different algorithms. From the strategy in [19], the higher the line in the figure is, the better the numerical results are. Figures 1–3 show the NI, NFG, and CPU time performances, respectively, of the new algorithm and the standard BFGS method. From the results shown in the figures, the NI, NFG, and CPU time of the algorithm constructed in this paper are generally better than those of the standard BFGS algorithm. Therefore, our algorithm is interesting and reliable from this perspective.Figure 1
Performance profiles of these methods (NI).Figure 2
Performance profiles of these methods (NFG).Figure 3
Performance profiles of these methods (CPU time).


### 4.2. Muskingum Model

In this section, the main work is to use Algorithm1 to numerically estimate the Muskingum model [20], whose definition is as follows:(32)minfx1,x2,x3=∑i=1n−11−Δt6x1x2Ii+1+1−x2Qi+1x3−1−Δt6x1x2Ii+1−x2Qix3−Δt2Ii−Qi+Δt21−Δt3Ii+1−Qi+12,where n is the total time, Ii is the observed inflow discharge, Qi is the observed outflow discharge, x1 denotes the storage time constant, x2 denotes the weight coefficient, x3 denotes an extra parameter, and Δt is the time step at time ti (i=1,2,…,n). The observation data in the experiment are from the process of flood runoff from Chenggouwan and Linqing of Nanyunhe in the Haihe Basin, Tianjin, China, and the initial point x=0,1,1T. In addition, the time step t=12h are selected, and the detailed values of Ii and Qi for the years 1960, 1961, and 1964 are given in [21].Figures4–6 and Table 7 imply the following conclusions: (1) Similar to the BFGS method and the HIWO method, the MBFGS method, combined with the Muskingum model, has interesting experimental results. (2) The final points (x1, x2, and x3) of the MBFGS method are more competitive than other similar methods. (3) Due to the difference in the final points of these three methods, the Muskingum model may have more approximate optimal points.Figure 4
Performance of Algorithm1 in 1960.Figure 5
Performance of Algorithm1 in 1961.Figure 6
Performance of Algorithm1 in 1964.Table 7
Results of the three algorithms.
Algorithmx1x2x3BFGS [22]10.81560.98261.0219HIWO [20]13.28130.80010.9933MBFGS11.18320.99990.9996


## 4.1. Unconstrained Optimisation Problems

In this section, we compare Algorithm1 with the BFGS-WWP algorithms for the 74 academic problems listed in Table 1. The codes are written with MATLAB R2014a and run on a PC with an Inter (R) Core (TM) i5-4210U CPU @ 1.70 GHz, 8.00 GB of RAM and the Windows 10 operating system, and the parameters are chosen as β=0.2, β1=0.15, θ=0.75, and ε=10−5. The numerical results and comparison are shown in Tables 2–6. The columns in Tables 2–6 have the following meaning:(i)
N0: the index of the tested problems(ii)
Dim: the dimension of the tested problem(iii)
NI: the iteration number consumed(iv)
NFG: the total number both of the gradient and the function value(v)
CPU time: the time consumed in corresponding algorithms in secondsTable 2
The numerical results for problems 1–17.
N0DimMBFGS-MWWPBFGS-WWPNINFGCPU timeNINFGCPU time13009260.12519261.062519007192.40637192.43751270072134.656172134.013123002795984.65632545474.005229006601381186.23127001489203.39422270071630.469171630.5030330062814718.734467614729.2969390010002429286.140610002598275.765632700100030865405.7969100029995390.2344430073316369.9219733161010.9375490010002371278.406310002421285.828142700100021105408.3906100021165375.0313530013390.187515450.2031590015464.031315463.812552700154674.1875154673.218863008330.09388330.1406690013493.484413493.06256270041710.500141710.390673001984012.56251984012.57817900409823112.9531409823111.65637270088317684735.796988317684768.6094830022480.406322480.3281890031668.359431668.51568270057118294.218857118292.781293006160.062513280.156399006161.406313283.26569270061624.7813143063.656310300290.031329010900290.0469290.0469102700290.1563290.15631130046940.609446940.5781119006713618.03126613419.002111270082200422.890697196533.46881230038780.531338780.546912900469412.7031469412.625312270066134340.437566134343.14061330014340.156214340.20311390015423.968815424.015613270049153257.421949151250.40631430011250.281311250.34381490010232.859410232.562514270061525.109461523.53131530013320.328113320.39061590014343.812514343.9219152700153772.0156153775.4844163007180.06257180.0938169006161.32816161.252116270061824.453161623.890617300981991.2656981991.3281179008818223.98488718023.328117270082170415.312582171405.2813Table 3
The numerical results for problems 18–34.
N0DimMBFGS-MWWPBFGS-WWPNINFGCPU timeNINFGCPU time183003100.03123100.0312189003100.54683100.48441827003109.34383109.003219300390.03123100.031219900390.54683100.53121927003910.17183109.62542030011320.18758270.06252090013552.468710291.8281202700164865.7812134045.453121300471220.5781501140.7187219005814116.21015012513.256721270058149295.171842108207.6562223006210.09377300.1093229006211.39067301.593722270062125.156273029.0781233001143931.85931133781.59372390015252342.890619062852.04682327002458541304.25212096931105.562524300943381.1562311610.2813249009336122.9531171271.93752427002412974.76562513679.43752530068618238.781273419089.70312590010003200280.968710002465272.875125270096928675167.4062100027915395.4062263004150.03124150.0312269004150.60934150.640626270041510.468141510.1093273007180.09377180.15632790013303.312513303.70312727002860139.20312860149.859328300882551.3593842451.48432890010328828.218710229527.3125282700131328694.8125128330669.3593293004150.03124150.0312299004150.65624150.421829270041510.39064156.2968303002074192.75212074192.828130900444893122.4375444893120.468730270086317284608.984386317284734.10933130011310.140611310.15623190013493.359313493.8281312700165879.8751165891.45313230013440.156213450.20313290012333.046812333.252132270072223367.953183235435.4687333004110.03124110.0312339004110.71874110.656233270041112.515641112.781234300390390.031234900390.5625390.512134270041014.718741014.2031Table 4
The numerical results for problems 35–51.
N0DimMBFGS-MWWPBFGS-WWPNINFGCPU timeNINFGCPU time353005130.06255130.0625359005131.09375131.078135270051319.593751318.109336300451180.8751451160.9375369004712213.59375514515.437536270064171324.656264167316.7968373002515073.56252515073.7031379005771159160.87515771159176.625137270086917414684.328186917414743.0937383005150.06255150.0625389005151.04685151.171838270051519.734351518.92183930019720.252219670.32813990023876.265621815.252139270034118173.112335120181.78124030048511627.218752010557.4375409005061162143.34377311468198.062540270052812702713.421882916644167.67184130012340.171812340.17184190012342.906212343.0468412700123456.5231123453.79684230018600.218716550.1875429004210.07814210.04684227004210.29684210.31254330015380.265615380.23434390018445.406218444.6875432700194694.0312204892.65624430029710.437527700.3752449004712013.09378320422.359344270087203443.703199224494.093745300561310.7812631460.9531459007517820.82819020925.484345270081190414.4218124265615.406246300701570.9375901961.671874690012127634.671811725832.5468462700174401916.87521994161049.3437473001102252.29681102252.37524790021944673.843721944668.98434727003467021940.34373467021948.343748300901831.6252901831.7031489007515720.56257515720.0468482700144291741.3751144291716.9375493001973992.67181973993.078149900422849117.1562422849116.656249270088217664726.187588217664725.7031503001853754.17181853754.031250900395795116.1562395795112.390650270085917204628.046885917204585.62515130024580.312524580.31255190021565.703130788.25235127003380163.78122772127.3593Table 5
The numerical results for problems 52–68.
N0DimMBFGS-MWWPBFGS-WWPNINFGCPU timeNINFGCPU time5230031303130.0468529003130.34373130.29685227003135.64063135.4062533003146344.10934048125.4063539009271860261.953110002004270.2188532700100020045316.6406100020025250.64065430025780.328124740.29695490028887.328128857.140654270033107166.218137116183.06255530010240.140620420.28125590011262.906221445.2187552700112650.96872348105.5123563003116263.78123547104.6252569009211846252.859310002002271.5312562700100020025193.1251100020004871.124157300771991.2187962321.4531579007291.64064014011.078157270073030.4531157565.859458300671440.8751731541.26565890010321429.843110321428.18755827002888124.14061964071044.9688593003150.03123150.03135990011582.812511583.265659270024111107.312524108109.109360300711660.9687791731.18756090013329542.203118238450.20316027001904331024.2812182388947.906261300681720.937526870.4375619007291.75219451.765661270073031.2812199082.3906623003598775.71813919086.3125629006251452182.96876181415168.562562270062214733372.6406156520809.6251633001573712.51561663912.65626390023657167.640626759274.890663270054112162961.687549311142569.2656643001984823.21312024853.21876490027662982.1562211125.42186427003129.93753129.140665300511141.0312481080.9062659005112215.42184210911.656265270055126290.484477179379.078166300527118710.2968534121110.18756690010002415294.625110002442285.8281662700100024945153.8281100025444975.5468673006210.031262106790010040821.328112330.156267270010290.906213590.98436830011260.187511260.20316890011263.218712283.5156682700122860.4375122852.7656Table 6
The numerical results for problems 69–74.
N0DimMBFGS-MWWPBFGS-WWPNINFGCPU timeNINFGCPU time69300431420.687526810.3752699006520017.890628897.593869270073222399.734334107170.4375703003588479.2031501510.9218709004415913.81257125019.28127027002637641469.703145152207.3438713001633322.03121633342.093871900483975147.3593488986130.2656712700100020005118.8751100020004951.73437230035800.828143940.7968729005812818.26565712618.187572270096208535.140698210531.1562733001332712.28121332711.70317390022545563.859322545560.25217327004719472572.96814438912325.015674300431120.7187431120.56257490018437357.359318437350.57817427002625291460.04682625291372.9375For intuitive effect, we adopt the performance technique in [19] to show the performance of different algorithms. From the strategy in [19], the higher the line in the figure is, the better the numerical results are. Figures 1–3 show the NI, NFG, and CPU time performances, respectively, of the new algorithm and the standard BFGS method. From the results shown in the figures, the NI, NFG, and CPU time of the algorithm constructed in this paper are generally better than those of the standard BFGS algorithm. Therefore, our algorithm is interesting and reliable from this perspective.Figure 1
Performance profiles of these methods (NI).Figure 2
Performance profiles of these methods (NFG).Figure 3
Performance profiles of these methods (CPU time).


## 4.2. Muskingum Model

In this section, the main work is to use Algorithm1 to numerically estimate the Muskingum model [20], whose definition is as follows:(32)minfx1,x2,x3=∑i=1n−11−Δt6x1x2Ii+1+1−x2Qi+1x3−1−Δt6x1x2Ii+1−x2Qix3−Δt2Ii−Qi+Δt21−Δt3Ii+1−Qi+12,where n is the total time, Ii is the observed inflow discharge, Qi is the observed outflow discharge, x1 denotes the storage time constant, x2 denotes the weight coefficient, x3 denotes an extra parameter, and Δt is the time step at time ti (i=1,2,…,n). The observation data in the experiment are from the process of flood runoff from Chenggouwan and Linqing of Nanyunhe in the Haihe Basin, Tianjin, China, and the initial point x=0,1,1T. In addition, the time step t=12h are selected, and the detailed values of Ii and Qi for the years 1960, 1961, and 1964 are given in [21].Figures4–6 and Table 7 imply the following conclusions: (1) Similar to the BFGS method and the HIWO method, the MBFGS method, combined with the Muskingum model, has interesting experimental results. (2) The final points (x1, x2, and x3) of the MBFGS method are more competitive than other similar methods. (3) Due to the difference in the final points of these three methods, the Muskingum model may have more approximate optimal points.Figure 4
Performance of Algorithm1 in 1960.Figure 5
Performance of Algorithm1 in 1961.Figure 6
Performance of Algorithm1 in 1964.Table 7
Results of the three algorithms.
Algorithmx1x2x3BFGS [22]10.81560.98261.0219HIWO [20]13.28130.80010.9933MBFGS11.18320.99990.9996


## 5. Conclusion

In this paper, we study the improved BFGS method with the line search technique [14, 15] and mainly discuss its convergence on a convex function. The numerical results show that the proposed algorithm has a better problem-solving capability than that of the standard BFGS algorithm based on WWP line search. As for the further work, we have several points to consider: (i) That whether the improved BFGS method, based on other line search, also has convergence property. (ii) The combination of line search techniques (10) and (11) with other quasi-Newton methods is worth studying. (iii) Similar applications of nonlinear conjugate gradient algorithm, especially the PRP method, are also worthy of attention.



---

*Source: 4519274-2020-08-18.xml*