Processing math: 100%
Research article

An accelerated adaptive two-step Levenberg–Marquardt method with the modified Metropolis criterion

  • Received: 11 June 2024 Revised: 11 August 2024 Accepted: 15 August 2024 Published: 22 August 2024
  • MSC : 65K05, 90C30

  • In this paper, aiming at the nonlinear equations, a new two-step Levenberg–Marquardt method was proposed. We presented a new Levenberg–Marquardt parameter to obtain the trial step. A new modified Metropolis criterion was used to adjust the upper bound of the approximate step. The convergence of the method was analyzed under the H¨olderian local error bound condition and the H¨olderian continuity of the Jacobian. Numerical experiments showed that the new algorithm is effective and competitive in the numbers of functions, Jacobian evaluations and iterations.

    Citation: Dingyu Zhu, Yueting Yang, Mingyuan Cao. An accelerated adaptive two-step Levenberg–Marquardt method with the modified Metropolis criterion[J]. AIMS Mathematics, 2024, 9(9): 24610-24635. doi: 10.3934/math.20241199

    Related Papers:

    [1] Luyao Zhao, Jingyong Tang . Convergence properties of a family of inexact Levenberg-Marquardt methods. AIMS Mathematics, 2023, 8(8): 18649-18664. doi: 10.3934/math.2023950
    [2] Lin Zheng, Liang Chen, Yanfang Ma . A variant of the Levenberg-Marquardt method with adaptive parameters for systems of nonlinear equations. AIMS Mathematics, 2022, 7(1): 1241-1256. doi: 10.3934/math.2022073
    [3] Xiaorui He, Jingyong Tang . A smooth Levenberg-Marquardt method without nonsingularity condition for wLCP. AIMS Mathematics, 2022, 7(5): 8914-8932. doi: 10.3934/math.2022497
    [4] Linsen Song, Gaoli Sheng . A two-step smoothing Levenberg-Marquardt algorithm for real-time pricing in smart grid. AIMS Mathematics, 2024, 9(2): 4762-4780. doi: 10.3934/math.2024230
    [5] Nenghui Kuang, Huantian Xie . Derivative of self-intersection local time for the sub-bifractional Brownian motion. AIMS Mathematics, 2022, 7(6): 10286-10302. doi: 10.3934/math.2022573
    [6] Alqahtani Bushra Abdulshakoor M, Weibin Liu . Li-Yorke chaotic property of cookie-cutter systems. AIMS Mathematics, 2022, 7(7): 13192-13207. doi: 10.3934/math.2022727
    [7] Xiangtuan Xiong, Wanxia Shi, Xuemin Xue . Determination of three parameters in a time-space fractional diffusion equation. AIMS Mathematics, 2021, 6(6): 5909-5923. doi: 10.3934/math.2021350
    [8] Yueting Yang, Hongbo Wang, Huijuan Wei, Ziwen Gao, Mingyuan Cao . An adaptive simple model trust region algorithm based on new weak secant equations. AIMS Mathematics, 2024, 9(4): 8497-8515. doi: 10.3934/math.2024413
    [9] Iftikhar Ahmad, Hira Ilyas, Muhammad Asif Zahoor Raja, Tahir Nawaz Cheema, Hasnain Sajid, Kottakkaran Sooppy Nisar, Muhammad Shoaib, Mohammed S. Alqahtani, C Ahamed Saleel, Mohamed Abbas . Intelligent computing based supervised learning for solving nonlinear system of malaria endemic model. AIMS Mathematics, 2022, 7(11): 20341-20369. doi: 10.3934/math.20221114
    [10] Panjie Tian, Zhensheng Yu, Yue Yuan . A smoothing Levenberg-Marquardt algorithm for linear weighted complementarity problem. AIMS Mathematics, 2023, 8(4): 9862-9876. doi: 10.3934/math.2023498
  • In this paper, aiming at the nonlinear equations, a new two-step Levenberg–Marquardt method was proposed. We presented a new Levenberg–Marquardt parameter to obtain the trial step. A new modified Metropolis criterion was used to adjust the upper bound of the approximate step. The convergence of the method was analyzed under the H¨olderian local error bound condition and the H¨olderian continuity of the Jacobian. Numerical experiments showed that the new algorithm is effective and competitive in the numbers of functions, Jacobian evaluations and iterations.



    The nonlinear equation is a popular topic in many research fields[1,2,3,4,5], including engineering design, physics, computational science, etc. However, with the increase in data scale and problem complexity, solving nonlinear equations has become incrementally challenging. Therefore, studying effective numerical methods to solve nonlinear equations has highly theoretical and practical significance.

    We consider solving nonlinear equations

    F(x)=0, (1.1)

    where F(x):RnRm is continuously differentiable and the solution set of (1.1) is nonempty denoted by X. There are many numerical methods[6,7,8,9,10,11,12] to solve nonlinear equations. Among them, the Levenberg–Marquardt (LM) method[13,14] has attracted much attention by introducing the LM regularizer into the Gauss–Newton method, which enables the algorithm to be well-defined when the Jacobian is singular or close to singular. It computes the LM step ˜dk as

    ˜dk=(JTkJk+λkI)1JTkFk, (1.2)

    where Fk=F(xk) and Jk=F(xk) is the Jacobian of F(x) at xk, λk>0 is an appropriate LM parameter updated with each iteration, and IRn×n is the identity matrix. Throughout the paper, denotes the Euclidean norm.

    The choice of the LM parameter is essential for the LM method. Yamashita and Fukushima[15] proved that the LM method had the quadratic convergence rate under the local error bound condition when λk=Fk2. Fan and Yuan[16] proposed λk=Fk, which overcame the shortcoming that the LM step was too small when the iteration xk was far away from the solution. Subsequently, Fan[17] chose λk as μkFk, in which μk was updated by a trust region technique. Amini[18] proposed the LM parameter μkFk1+Fk, and proved the convergence under the local error bound condition. On the other hand, Ma and Jiang[19] chose the LM parameter as θFk+(1θ)JTkFk with θ[0,1] and obtained the quadratic convergence rate under the local error bound condition. Fan and Pan[20] proposed the LM parameter

    λk=μk(θFk+(1θ)JTkFk), (1.3)

    and preserved the quadratic convergence. From this, we can find that the LM parameter is an important component of algorithm research and deserves further study.

    To improve the convergence rate and efficiency of the algorithm, Fan[21] proposed the modified LM algorithm with the LM step ˜dk in (1.2) and the approximate step

    ˆdk=(JTkJk+λkI)1JTkF(yk), (1.4)

    where yk=xk+˜dk and λk=μkFkδ with δ[1,2]. Using Jk instead of J(yk) could effectively save the calculations of the Jacobian. Under the local error bound condition, the modified LM method achieved a cubic convergence. Fan and Zeng [22] introduced a new correction step:

    ˆdk=(JTkJk+λkI)1λk˜dk,

    where λk=μkFkδ with δ(0,2] and the convergence rate was min{2,1+2δ} under the same conditions. Above all, the trial step of each iteration became

    ˉsk=˜dk+ˆdk,

    and the step size was a unit. Then, Fan[23] proposed the accelerated modified LM method, which introduced a line search along ˆdk of (1.4). The step size was the solution of

    maxα[1,ˆα]F(yk)2F(yk)+αJkˆdk2:=ϕ(α),whereˆα>1. (1.5)

    By a simple derivation,

    ˜αk:=argmaxϕ(α)=1+λkˆdTkˆdkˆdTkJTkJkˆdk>1,whenJkˆdk0. (1.6)

    If Jkˆdk was close to 0, ˜αk would be too large. An upper bound ˆα>1 for α in (1.5) was set and the step size was chosen as αk=min(˜αk,ˆα). Moreover, the trust region ratio was introduced by

    rk=AredkPredk=Fk2F(xk+˜dk+αkˆdk)2Fk2Fk+Jk˜dk2+F(yk)2F(yk)+αkJkˆdk2, (1.7)

    which was used to decide whether to accept the trial step and updated the parameter μk. However, the choice strategy of ˆα and its influence to the convergence of the algorithm is not mentioned. This inspires us to consider an adaptive updated strategy to the upper bound of the step size in each iteration, which enables the algorithm to preserve the cubic convergence and not increase the computational cost of the Jacobian evaluations. Note that the different choice strategy of λk also leads to the different LM method. We will propose a new LM parameter and construct a new two-step LM method with adaptive step size.

    When proving the convergence rate, some problems do not satisfy the local error bound condition, but practically satisfy the H¨olderian error bound condition. Zhu et al.[24], Wang et al.[25], Zeng et al.[26], and Chen et al.[27] studied the local convergence rate of the LM method under the H¨olderian local bound condition with different LM parameters, respectively. To expand the scope and practicality of the algorithm, we devote our research to giving the global and local convergence under the H¨olderian conditions.

    The aim of our research is to propose an effective accelerated adaptive two-step LM algorithm based on a modified criterion for solving nonlinear equations. The key innovations of this paper are as follows: First, we use the convex combination of Fk1+Fk and JTkFk1+JTkFk as a new LM parameter to update the trial step. Second, considering that different approximate steps may have different upper bounds, we introduce a new modified criterion to update the upper bound of the approximate step size, rather than changing at a constant. Third, the convergence of the new method is proved under the H¨olderian local error bound condition and the H¨olderian continuity of the Jacobian.

    The paper is organized as follows. In next section, a new two-step LM algorithm is described and the global convergence under the H¨olderian continuity of the Jacobian is presented. In Section 3, we derive the convergence rate of the new algorithm under the H¨olderian local error bound condition and the H¨olderian continuity of the Jacobian. In Section 4, numerical experiments show that the new algorithm reduces the numbers of function and Jacobian evaluations. We conclude the paper in Section 5.

    In this section, we propose a novel two-step LM method with a new parameter λk. The upper bound of the approximate step size is adjusted by the modified Metropolis criterion. The global convergence of the new method is proved under the H¨olderian continuity of the Jacobian which is weaker than the Lipschitz continuity.

    Since the LM step ˜dk in (1.2) and the approximate step ˆdk in (1.4) rely on the choice of λk, we construct a new LM parameter

    λk=μk(θFk1+Fk+(1θ)JTkFk1+JTkFk),whereθ[0,1]. (2.1)

    When xk is far from the optimal solution, Fk and JTkFk are large enough to make Fk1+Fk and JTkFk1+JTkFk close to 1. At this time, λk is close to μk. Conversely, when xk approaches the optimal solution, θFk1+Fk and (1θ)JTkFk1+JTkFk degenerate into θFk and (1θ)JTkFk, which indicates that λk is close to the LM parameter mentioned in (1.3). The new LM parameter in (2.1) provides flexibility with the iteration process and enhances the performance of the LM method.

    The trial step of the new method is

    sk=˜dk+αkˆdk,

    where αk is the step size along ˆdk. Unlike the reference [23], we will propose a new upper bound ˆαk of the step size in (1.5). Similar to the Metropolis criterion suggested by [28], we give a new modified Metropolis criterion

    ˉαk={1,if|rk11|τ,e|rk11|Tk,otherwise,withk1, (2.2)

    where 0<τ<1 represents a sufficiently small constant and Tk is the temperature decreasing to 0 as k by the cooling schedule. If |rk11|τ, rk1 is close enough to 1, and we set ˉαk as 1. Otherwise, |rk11|>τ, we set ˉαk=e|rk11|Tk, which can be regarded as a probability and also decreases to 0 as k. This is similar to the simulated annealing. We define the upper bound of the step size as ˆαk=1+ˉαk. In each iteration, ˆαk is self-adaptively updated by (2.2). Now, we set the step size along ˆdk as

    αk=min(˜αk,ˆαk), (2.3)

    where ˜αk is given by (1.6). Moreover, since ϕ(α) has the monotonically increasing property on [1,˜αk] and αk[1,˜αk], it is easy to find ϕ(αk)ϕ(1). This implies

    F(yk)2F(yk)+αkJkˆdk2F(yk)2F(yk)+Jkˆdk2. (2.4)

    Based on the above description, we present the accelerated adaptive two-step Levenberg–Marquardt (AATLM) algorithm.

    Algorithm 1 AATLM algorithm.
    Step 0. Set x0Rn, F0=F(x0), J0=J(x0), ε>0, μ0>m0>0, 1θ0, ˉα0>0, τ>0, T0=1, C=0.99, 1>q2>q1>q0>0, u>1, a1>1>a2>0. Let k:=0.
    Step 1. If JTkFkε, stop, else compute λk by (2.1).
    Step 2. Solve
    (JTkJk+λkI)d=JTkFk (2.5)
    to obtain ˜dk, and solve
    (JTkJk+λkI)d=JTkF(yk)withyk=xk+˜dk
    to obtain ˆdk. If ˆdkε, set sk=˜dk, else compute αk by (1.6), (2.2), (2.3), and set sk=˜dk+αkˆdk.
    Step 3. Compute rk=AredkPredk by (1.7). Set
    xk+1={xk+sk,ifrkq0,xk,otherwise.
    Compute Fk+1 and Jk+1.
    Step 4. Choose μk+1 as
    μk+1={a1μk,ifrkq1,μk,ifq1<rkq2,max{a2μk,m0},otherwise. (2.6)
    Set Tk+1=CTk and k:=k+1, and go to step 1.

    Remark 2.1. In Step 2, ˜αk is computed by (1.6), which is proposed in [23] with Jkˆdk0. In [23], when Jkˆdk was close to 0, ˆα was set as the upper bound of ˜αk. However, the case of Jkˆdk=0 was not mentioned. Note that, if ˆdk0, then Jkˆdk0. In fact, if Jkˆdk=0 holds, from the definition of ˆdk, we have

    JTkF(yk)=(JTkJk+λkI)ˆdk=JTkJkˆdk+λkˆdk=λkˆdk0.

    Due to ˆdk being the solution of

    mindRnF(yk)+Jkd2s.t.dΔk,2:=ˆdk, (2.7)

    it is easy to obtain

    F(yk)2F(yk)+Jkˆdk2JTkF(yk)min{ˆdk,JTkF(yk)JTkJk}.

    At this time, the left side of the above equation is 0, but the right side is larger than 0. This leads to a contradiction. Therefore, if ˆdk=0, we set sk=˜dk, and the algorithm degenerates into a general LM algorithm.

    To prove the global convergence of the algorithm, we give the following assumption.

    Assumption 2.1. (a) The Jacobian J(x) is H¨olderian continuous of order ν(0,1], i.e., there exists a positive constant κhj such that

    J(y)J(x)κhjyxν,x,yRn. (2.8)

    (b) The Jacobian J(x) is bounded above, i.e., there exists a positive constant κbj such that

    J(x)κbj,xRn. (2.9)

    By using (2.8), we have

    F(y)F(x)J(x)(yx)=10J(x+t(yx))(yx)dtJ(x)(yx)yx10J(x+t(yx))J(x)dtκhjyx1+ν10tνdt=κhj1+νyx1+ν. (2.10)

    Lemma 2.1. Under the conditions of Assumption 2.1, the sequence {xk} generated by the AATLM algorithm satisfies:

    PredkJTkFkmin{˜dk,JTkFkJTkJk}+JTkF(yk)min{ˆdk,JTkF(yk)JTkJk}

    for all k.

    Proof. Since ˜dk is the solution of the following trust region subproblem,

    mindRnFk+Jkd2s.t.dΔk,1:=˜dk,

    for any β[0,1], it follows:

    Fk2Fk+Jk˜dk2Fk2FkJkβΔk,1JTkFkJTkFk22βΔk,1JTkFkβ2Δ2k,1JTkJk.

    Then,

    Fk2Fk+Jk˜dk2max0β1{2βΔk,1JTkFkβ2Δ2k,1JTkJk}JTkFkmin{˜dk,JTkFkJTkJk}. (2.11)

    If ˆdk=0, (2.12) implies that the conclusion of Lemma 2.1 holds. Otherwise, ˆdk is the solution of (2.7), and it holds that

    F(yk)2F(yk)+Jkˆdk2F(yk)2F(yk)JkβΔk,2JTkF(yk)JTkF(yk)22βΔk,2JTkF(yk)β2Δ2k,2JTkJk.

    According to (2.4), we have

    F(yk)2F(yk)+αkJkˆdk2max0β1{2βΔk,2JTkF(yk)β2Δ2k,2JTkJk}JTkF(yk)min{ˆdk,JTkF(yk)JTkJk}. (2.12)

    The conclusion follows from adding (2.11) and (2.12).

    Now, we give the global convergence of the AATLM algorithm.

    Theorem 2.1. Under the conditions of Assumption 2.1, the sequence {xk} generated by the AATLM algorithm satisfies

    limkJTkFk=0. (2.13)

    Proof. We prove by contradiction. Suppose (2.13) is not true. There exist a positive constant δ and infinitely many k such that

    JTkFkδ,k. (2.14)

    Let the sets of the indices S1 and S2 be

    S1={k|JTkFkδ},
    S2={k|JTkFkδ2andxk+1xk},

    where S1 is an infinite set. Consider the following two cases.

    Case 1: S2 is finite. We have

    S3={k|JTkFkδandxk+1xk}

    is also finite. Let ˜k be the largest index of S3, which means xk+1=xk holds for all k{k>˜k|kS1}. Define the indicator set

    S4={k>˜k|JTkFkδandxk+1=xk}.

    We notice that JTk+1Fk+1δ and xk+2=xk+1 for all kS4. Otherwise, if xk+2xk+1, then k+1S3, which means that ˜k is not the largest index of S3. It is easy to get k+1S4. By induction, JTkFkδ and xk+1=xk hold for all k>˜k.

    According to Step 3 in the AATLM algorithm, rk<q0 means that xk+1=xk holds for all k>˜k, and from (2.1), (2.5), and (2.6), we obtain:

    μk+andλk+, (2.15)

    which implies that

    ˜dk0.

    From (2.9), (2.10), (2.7), (2.15), and the definition of ˆdk, we find

    ˆdk=(JTkJk+λkI)1JTkF(yk)(JTkJk+λkI)1JTkFk+(JTkJk+λkI)1JTkJk˜dk+κhj1+ν˜dk1+ν(JTkJk+λkI)1JTk˜dk+˜dk+κhjκbj(1+ν)λk˜dk1+νˉc˜dk (2.16)

    for all sufficiently large k, where ˉc is a positive constant. So, we conclude

    sk=˜dk+αkˆdk(1+ˉcαk)˜dk. (2.17)

    On the other hand, it is clear from (2.10) that

    {|F(yk)Fk+Jk˜dk|κhj1+ν˜dk1+ν,|F(xk+sk)F(yk)+αkJkˆdk|κhj1+νsk1+ν+κhj1+ν˜dk1+ν,

    and

    {|F(yk)+Fk+Jk˜dk|2Fk+Jk˜dk+κhj1+ν˜dk1+ν,|F(xk+sk)+F(yk)+αkJkˆdk|2Fk+Jksk+κhj1+νsk1+ν+κhj1+ν˜dk1+ν.

    From the above formulas and Lemma 2.1, (2.10), (2.14), and (2.17), we have

    |rk1|=|AredkPredkPredk||F(xk+sk)2Fk+Jk˜dk2+F(yk)2F(yk)+αkJkˆdk2JTkFkmin{˜dk,JTkFkJTkJk}+JTkF(yk)min{ˆdk,JTkF(yk)JTkJk}|Fk+Jk˜dkO(˜dk1+ν)+Fk+JkskO(˜dk1+ν+sk1+ν)˜dk+O(˜dk2+2ν+˜dk1+νsk1+ν+sk2+2ν)˜dk0, (2.18)

    which means that rk1. According to the updating rule of μk, we know that there exists a positive constant M>m0, such that μk<M holds for all sufficiently large k, which contradicts with (2.15). Now, we point out that the assumption (2.14) is not true.

    Case 2: S2 is infinite. From Lemma 2.1, (2.10), and the fact that sk is accepted by the AATLM algorithm, we have

    F12kS2(Fk2Fk+12)kS2q0PredkkS2q0{JTkFkmin{˜dk,JTkFkJTkJk}+q0JTkF(yk)min{ˆdk,JTkF(yk)JTkJk}}kS2q0δ2min{˜dk,δ2κ2bj}, (2.19)

    and xk+1xk=0 if kS2, which implies that

    ˜dk0,kS2, (2.20)

    and from the definition of ˜dk, we obtain:

    λk+,kS2. (2.21)

    Similarly to (2.16) and (2.17), there exists a constant ˜c>0, which makes it true for all sufficiently large kS2, so,

    sk=˜dk+αkˆdk(1+˜cαk)˜dk. (2.22)

    It follows from (2.19) that

    kS2sk=kS2˜dk+αk^dk<+.

    Moreover, combining with Assumption 2.1, we get

    kS2|JTkFkJTk+1Fk+1|<+.

    Since (2.14) holds for sufficiently large k, there exists a large ˆk, such thatJTˆkFˆkδ, and

    kS2,kˆk|JTkFkJTk+1Fk+1|<δ2.

    By induction, we find that JTkFkδ2 holds for all kˆk, and then, we can derive from (2.19)–(2.22) that

    limk˜dk=0andlimkˆdk=0,

    and thus,

    μk+.

    Similarly, to the analysis of (2.18), we have

    rk1.

    Therefore, there exists a positive constant M>m0 such that μk<M holds for sufficiently large k, which contradicts (2.14). Above all, we get the conclusion immediately.

    Theorem 2.1 indicates that there is xX such that the sequence {xk} generated by the AATLM algorithm converges to x. For the sufficient large k, if xk lies in a neighborhood of x, then xk+1 and yk also lie in the neighborhood.

    In this section, we give the properties of the trial step and the boundary of the LM parameter. In order to establish the convergence rate of the AATLM algorithm under the H¨olderian local error bound and H¨olderian continuity of the Jacobian, we use the following assumption.

    Assumption 3.1. (a) F(x) provides a H¨olderian local error bound of order γ(0,1] in some neighborhoods of xX, i.e., there exist constants c>0 and 0<b<1, such that

    cdist(x,X)F(x)γ,xN(x,b)={x|xxb}, (3.1)

    and when γ=1, F(x) provides the local error bound.

    (b) The Jacobian J(x) is H¨olderian continuous of order ν(0,1], i.e., there exists a constant κhj>0 such that

    J(y)J(x)κhjyxν,x,yN(x,b). (3.2)

    From (3.2), we immediately have

    F(y)F(x)J(x)(yx)κhj1+νyx1+ν,wherex,yN(x,b2), (3.3)

    and there is a constant κbf>0 such that

    F(y)F(x)κbfyx,wherex,yN(x,b2). (3.4)

    Moreover, we denote ˉxk as the closest point to xk in X, i.e., dist(xk,X)=ˉxkxk.

    Combining the results given by Behling and Iusem[29], we assume that rank(J(ˉx))=r for all ˉxN(x,b)X. Suppose the singular value decomposition (SVD) of J(ˉxk) is

    ˉJk=ˉUkˉΣkˉVTk=(ˉU1,ˉU2)(ˉΣ10)(ˉVT1ˉVT2)=ˉU1ˉΣ1ˉVT1,

    where ˉΣ1=diag(ˉσ1,...,ˉσr), and ˉσ1ˉσ2...ˉσr>0. Thus, we obtain:

    Jk=UkΣkVTk=(U1,U2,U3)(Σ1Σ20)(VT1VT2VT3)=U1Σ1VT1+U2Σ2VT2,

    where Σ1=diag(σ1,...,σr), σ1σ2...σr>0, and Σ2=diag(σr+1,...,σr+q), σrσr+1σr+2...σr+q>0. Following from the theory of matrix perturbation[30], and the H¨olderian continuity of Jk, we know

    diag(Σ1ˉΣ1,Σ2,0)JkˉJkκhjˉxkxkν,

    which yields

    Σ1ˉΣ1κhjˉxkxkνandΣ2κhjˉxkxkν. (3.5)

    Lemma 3.1. Under the conditions of Assumption 3.1, if xk,ykN(x,b4), and

    ν>max{2(1γ1),12γ},

    there exists a constant c1>0 such that

    skc1dist(xk,X). (3.6)

    Proof. Since xkN(x,b4)={x|xkxb4}, it follows from the definition of ˉxk that

    ˉxkxˉxkxk+xkx2xkxb2,

    which means ˉxkN(x,b2).

    From the definition of λk, we set λ1k=μkθFk1+Fk, and λ2k=μk(1θ)JTkFk1+JTkFk. Then, together with (3.1) and μk>m0, we have

    λ1k{μkθ2Fkm0θ2c1γˉxkxk1γ,ifFk1;μkθ2m0θ2,otherwise.

    As we know, Fk2=FTkFk=FTk[F(ˉxk)+Jk(ˉxkxk)]+FTkHk, in which Hk=FkF(ˉxk)Jk(ˉxkxk). So, we have FTkJk(ˉxkxk)=Fk2FTkHk. From the Assumption 3.1, and ν>2(1γ1), it is clear that

    JTkFkˆcˉxkxk2γ1

    holds for some ˆc>0. In the same way, we obtain:

    λ2k{μk(1θ)2JTkFkm0(1θ)2ˆcˉxkxk2γ1,ifJTkFk1;μk(1θ)2m0(1θ)2,otherwise.

    Thus, we find that the LM parameter λk satisfies:

    λk=μk(θFk1+Fk+(1θ)JTkFk1+JTkFk)max{m0θ2,m0θ2c1γˉxkxk1γ}+max{m0(1θ)2,m0(1θ)2(ˆcˉxkxk2γ1)}ˊcˉxkxk1γ, (3.7)

    where ˊc>0.

    In addition, the equivalence problem of (2.11) is

    mindRnFk+Jkd2+λkd2φk,1(d),

    which has the optimal solution ˜dk. Combining with (3.7), we have that

    ˜dk2φk,1(ˉxkxk)λk=Fk+Jk(ˉxkxk)2λk+ˉxkxk2k2hjˉxkxk2+2νˊc(1+ν)2ˉxkxk1γ+ˉxkxk2c1,1ˉxkxk2min{1,1+ν12γ}

    holds for some c1,1>0, which means that

    ˜dkc1,2ˉxkxkmin{1,1+ν12γ} (3.8)

    holds for some c1,2>0.

    By the definition of ˆdk and (3.3), we obtain

    ˆdk=(JTkJk+λkI)1JTkF(yk)(JTkJk+λkI)1JTkFk+(JTkJk+λkI)1JTkJk˜dk+κhj1+ν˜dk1+ν(JTkJk+λkI)1JTk2˜dk+κhj1+ν˜dk1+ν(JTkJk+λkI)1JTk. (3.9)

    By using the SVD of Jk, we have

    (JTkJk+λkI)1JTk=(V1,V2,V3)((Σ21+λkI)1Σ1(Σ22+λkI)1Σ20)(UT1UT2UT3)((Σ21+λkI)1Σ1(Σ22+λkI)1Σ20)(Σ11λ1kΣ2). (3.10)

    Due to the sequence {xk} converging to the nonempty solution set X, if κhjˉxkxkνˉσr2 for any sufficiently large k, from the lower bound of λk, we get

    Σ111ˉσrκhjˉxkxkν2ˉσr,

    and

    λ1kΣ2κhjˉxkxkνˊcˉxkxk1γ=ˊcˉxkxkν1γ,

    where ˊc>0 is a constant. Then, combining with (3.9), (3.10), the lower bound of λk, and the range of ν, we can deduce

    ˆdk2˜dk+κhj1+ν˜dk1+ν(JTkJk+λkI)1JTk2˜dk+2ˊcκhjˉσr(1+ν)˜dk1+νˉxkxkν1γ2˜dk+2ˊcκhjc1+ν1,2ˉσr(1+ν)ˉxkxkmin{1+2ν1γ,1+3ν+ν2ν2γ32γ}ˇcˉxkxkmin{1,τ},

    where ˇc>0 is a constant, and

    τ=min{1+ν12γ,1+2ν1γ,1+3ν+ν2ν2γ32γ}. (3.11)

    From assumption ν>max{2(1γ1),12γ} and the condition ν,γ(0,1], we know ν>1γ1, and γ(23,1]. It is easy to find ν(12,1]. As the exponent γ increases, smaller values on the exponent ν are allowed. We obtain:

    τ11=1+ν12γ1=ν12γ>0,
    τ21=1+2ν1γ1=2(ν12γ)>0,
    τ31=1+3ν+ν2ν2γ32γ1=3(ν12γ)+ν(ν12γ)>0,

    which implies

    ˜dkO(ˉxkxk),ˆdkO(ˉxkxk). (3.12)

    Due to the definition of sk, it is easy to know

    sk=˜dk+αkˆdkO(ˉxkxk).

    The proof is complete.

    Lemma 3.2. Under the conditions of Assumption 3.1, if xk,ykN(x,b4), and

    ν>max{2(1γ1),12γ},

    there exists a constant M>m0, such that

    μkM (3.13)

    holds for all large k.

    Proof. We consider the following two cases.

    Case 1: If ˉxkxk˜dk, it follows from (3.1), (3.3), and ν>2(1γ1) that

    FkFk+Jk˜dkFkFk+Jk(ˉxkxk)c1γˉxkxk1γ+O(ˉxkxk1+ν)c2,1ˉxkxk1γ, (3.14)

    where c2,1>0 is a constant.

    Case 2: If ˉxkxk>˜dk, it follows from the second and third inequalities of (3.14), that we have

    FkFk+Jk˜dkFkFk+˜dkˉxkxkJk(ˉxkxk)˜dkˉxkxk(FkFk+Jk(ˉxkxk))˜dkˉxkxkc2,1ˉxkxk1γc2,1˜dkˉxkxk1γ1. (3.15)

    Using the same analysis as (3.14) and (3.15), we deduce

    F(yk)F(yk)+JkˆdkF(yk)F(yk)+Jk(ˉykyk)F(yk)F(yk)+J(yk)(ˉykyk)(JkJ(yk))(ˉykyk)c1γˉykyk1γ+O(ˉykyk1+ν)+O(˜dkνˉykyk)c2,2ˉykyk1γ, (3.16)

    where c2,2>0 is a constant with ˉykykˆdk, and

    F(yk)F(yk)+JkˆdkF(yk)F(yk)+ˆdkˉykykJk(ˉykyk)ˆdkˉykyk(F(yk)F(yk)+Jk(ˉykyk))ˆdkˉykykc2,2ˉykyk1γc2,2ˆdkˉykyk1γ1 (3.17)

    holds for ˉykyk>ˆdk.

    Hence, it follows from (3.14)–(3.17), and the definition of Predk that

    PredkFk(FkFk+Jk˜dk)+F(yk)(F(yk)F(yk)+Jkˆdk)Ck,

    where

    Ck=c2,1Fkmin{ˉxkxk1γ,˜dkˉxkxk1γ1}+c2,2F(yk)min{ˉykyk1γ,ˆdkˉykyk1γ1}.

    From (JTkFk)T˜dk<0, we can derive that F(yk)<Fk. Combining (3.1) and (3.3) with (3.12) yields

    |rk1|=|AredkPredkPredk||F(xk+sk)2Fk+Jk˜dk2+F(yk)2F(yk)+αkJkˆdk2Ck|Fk+Jk˜dkO(˜dk1+ν)+Fk+JkskO(˜dk1+ν+sk1+ν)O(˜dkˉxkxk2γ1)+O(˜dk2+2ν+˜dk1+νsk1+ν+sk2+2ν)O(˜dkˉxkxk2γ1).

    Due to ν>max{2(1γ1),12γ}, it is clear that rk1. Therefore, we conclude that (3.13) is valid from Step 4 in the AATLM algorithm and Lemma 3.2 is proved.

    Lemma 3.3. Under the conditions of Assumption 3.1, if xk,ykN(x,b4) and ν>2(1γ1), we have

    ˊcˉxkxk1γλkMθκbfˉxkxk+M(1θ)κ2bfˉxkxk,

    where ˊc>0 is a constant.

    Proof. It follows from (3.7) that

    ˊcˉxkxk1γλk.

    By using Lemma 3, (3.2), (3.4), and the definition of λk, we conclude

    λk=μk(θFk1+Fk+(1θ)JkFk1+JkFk)μkθFk+μk(1θ)JkFkMθκbfˉxkxk+M(1θ)κ2bfˉxkxk, (3.18)

    which means that λk is bounded. Above all, we have the conclusion immediately.

    We use the SVD to calculate the convergence rate of the AATLM algorithm. By the SVD of Jk, we get

    ˜dk=V1(Σ21+λkI)1Σ1UT1FkV2(Σ22+λkI)1Σ2UT2Fk, (3.19)
    ˆdk=V1(Σ21+λkI)1Σ1UT1F(yk)V2(Σ22+λkI)1Σ2UT2F(yk), (3.20)
    Fk+Jk˜dk=FkU1Σ1(Σ21+λkI)1Σ1UT1FkU2Σ2(Σ22+λkI)1Σ2UT2Fk=λkU1(Σ21+λkI)1UT1Fk+λkU2(Σ22+λkI)1UT2Fk+U3UT3Fk, (3.21)
    F(yk)+Jkˆdk=F(yk)U1Σ1(Σ21+λkI)1Σ1UT1F(yk)U2Σ2(Σ22+λkI)1Σ2UT2F(yk)=λkU1(Σ21+λkI)1UT1F(yk)+λkU2(Σ22+λkI)1UT2F(yk)+U3UT3F(yk). (3.22)

    Lemma 3.4. Under the conditions of Assumption 3.1, if xk,ykN(x,b4), we have

    (a) U1UT1Fkκbfˉxkxk;

    (b) U2UT2Fk(κhj1+ν+κhj)ˉxkxk1+ν;

    (c) U3UT3Fkκhj1+νˉxkxk1+ν.

    Proof. We could obtain (a) directly from (3.4). Let ˉsk=J+kFk, where J+k is the pseudo-inverse of Jk and ˉsk is the least squares solution of minFk+Jks. Then, we obtain (c) from (3.3) that

    U3UT3Fk=Fk+JkˉskFk+Jk(ˉxkxk)κhj1+νˉxkxk1+ν.

    Let ˜Jk=U1Σ1VT1 and ˜sk=˜J+kFk, where ˜J+k is the pseudo-inverse of ˜Jk and ˜sk is the least squares solution of minFk+˜Jks. Together with (3.4) and (3.5) implies

    (U2UT2Fk+U3UT3Fk)=Fk+˜Jk˜skFk+˜Jk(ˉxkxk)Fk+Jk(ˉxkxk)+(˜JkJk)(ˉxkxk)κhj1+νˉxkxk1+ν+(U2Σ2VT2)(ˉxkxk)κhj1+νˉxkxk1+ν+κhjˉxkxkνˉxkxk(κhj1+ν+κhj)ˉxkxk1+ν,

    which means that we obtain (b) from the orthogonality of U2 and U3. The proof is complete.

    Lemma 3.5. Under the conditions of Assumption 3.1, if xk,ykN(x,b4) and ν>max{2(1γ1),12γ}, we have

    (a) U1UT1F(yk)O(ˉxkxk1+ν);

    (b) U2UT2F(yk)O(ˉxkxkν+γ(1+ν));

    (c) U3UT3F(yk)O(ˉxkxkν+γ(1+ν)).

    Proof. From (3.21), Lemmas 3.3 and 3.4, and the range of ν, we have

    Fk+Jk˜dkλkΣ211U1UT1Fk+U2UT2Fk+U3UT3FkO(ˉxkxk2)+O(ˉxkxk1+ν)O(ˉxkxk1+ν), (3.23)

    and from (3.3), (3.8), and (3.23), we have

    F(yk)=F(xk+˜dk)Fk+Jk˜dk+κhj1+ν˜dk1+νO(ˉxkxk1+ν)+O(ˉxkxk1+ν)=O(ˉxkxk1+ν).

    Thus, it is clear that

    U1UT1F(yk)F(yk)O(ˉxkxk1+ν),

    which indicates that the following condition of the H¨olderian local error bound,

    ˉykyk1cF(yk)γO(ˉxkxkγ(1+ν)), (3.24)

    is obtained.

    Then, we let ˉpk=J+kF(yk), and ˉpk is the least squares solution of minF(yk)+Jkp. From (3.2), (3.3), (3.9), (3.24), and the range of ν, we have

    U3UT3F(yk)=F(yk)+JkˉpkF(yk)+Jk(ˉykyk)F(yk)+J(yk)(ˉykyk)+(JkJ(yk))(ˉykyk)κhj1+νˉykyk1+ν+κhj˜dkνˉykykO(ˉxkxkmin{γ(1+ν)2,ν+γ(1+ν)})O(ˉxkxkν+γ(1+ν)).

    Let ˜Jk=U1Σ1VT1 and ˜pk=˜J+kF(yk), where ˜pk is the least squares solution of minF(yk)+˜Jkp. It follows from (3.2), (3.3), (3.6), (3.8), (3.24), and the range of ν that

    (U2UT2+U3UT3)F(yk)=F(yk)+˜JkpkF(yk)+˜Jk(ˉykyk)F(yk)+J(yk)(ˉykyk)+(˜JkJ(yk))(ˉykyk)κhj1+νˉykyk1+ν+(JkJ(yk))(ˉykyk)+U2Σ2VT2(ˉykyk)κhj1+νˉykyk1+ν+κhj˜dkνˉykyk+κhjˉxkxkνˉykykO(ˉxkxkmin{γ(1+ν)2,ν+γ(1+ν)})O(ˉxkxkν+γ(1+ν)),

    and then, together with the orthogonality of U2 and U3, we obtain (b) and Lemma 3.5 is proved.

    Theorem 3.1. Under the conditions of Assumption 3.1, if xk,ykN(x,b4), ν>2(1γ1), and ν>12γ, the sequence {xk} generated by the AATLM algorithm converges to the solution set of (1.1) with order νγ+γ2(1+ν).

    Proof. From (3.5), (3.20), Lemma 3.5, and the upper bound of λ1kΣ2, we have

    ˆdk=V1(Σ21+λkI)1Σ1UT1F(yk)V2(Σ22+λkI)1Σ2UT2F(yk)Σ11UT1F(yk)+λ1kΣ2UT2F(yk)O(ˉxkxk1+ν)+O(ˉxkxk2ν+γ(1+ν)1γ)O(ˉxkxkmin{1+ν,2ν+γ(1+ν)1γ}). (3.25)

    It follows from (3.18), (3.22), and Lemma 3.5 that

    F(yk)+αkJkˆdkF(yk)+Jkˆdk=λkU1(Σ21+λkI)1UT1F(yk)+λkU2(Σ22+λkI)1UT2F(yk)+U3UT3F(yk)λkΣ21U1UT1F(yk)+U2UT2F(yk)+U3UT3F(yk)O(ˉxkxk2+ν)+O(ˉxkxkν+γ(1+ν))O(ˉxkxkν+γ(1+ν)). (3.26)

    Hence, combining with (3.8), (3.25), (3.26), and Assumption 3.1, we know

    c1γˉxk+1xk+11γF(xk+1)=F(yk+αkˆdk)F(yk)+αkJ(yk)ˆdk+κhj1+να1+νkˆdk1+νF(yk)+αkJkˆdk+αk(J(yk)Jk)ˆdk+κhj1+να1+νkˆdk1+νF(yk)+αkJkˆdk+khjαk˜dkνˆdk+κhj1+να1+νkˆdk1+νO(ˉxkxkν+γ(1+ν))+O(ˉxkxkmin{1+2ν,3ν+γ(1+ν)1γ})+O(ˉxkxkmin{(1+ν)2,(1+ν)(2ν+γ(1+ν)1γ)})O(ˉxkxkξ), (3.27)

    where ξ=min{ν+γ(1+ν),1+2ν,3ν+γ(1+ν)1γ,(1+ν)2,(1+ν)(2ν+γ(1+ν)1γ)}. Consider γ(23,1] and ν(12,1], and we have

    1+2ν(ν+γ(1+ν))=(1γ)(1+ν)>0,

    and

    (1+ν)2(1+2ν)=ν2>0.

    By ν>12γ and γ(23,1], we derive

    3ν+γ(1+ν)1γ(ν+γ(1+ν))=2(ν12γ)>0,

    and

    (1+ν)(2ν+γ(1+ν)1γ)(3ν+γ(1+ν)1γ)=ν(2ν+γ+νγ1γ1)>ν(γ12)>0.

    These mean that ξ=ν+γ(1+ν) and {xk} converges to some solution of (1.1) with the rate of νγ+γ2(1+ν).

    Moreover, together with ˉxkxkˉxk+1xkˉxk+1xk+1+sk and (3.27), we have

    ˉxkxk2sk

    for all sufficiently large k. It is clear from Lemma 3.1 that

    sk+1O(skνγ+γ2(1+ν)).

    By the above explanation, along with the condition that ν>max{2(1γ1),12γ}, we can conclude that Theorem 3.1 is valid. The proof is complete.

    In addition, when the values of ν and γ are different, we have convergence rates as follows

    sk+1{O(skγ+2γ2),ifν=1;O(sk1+2ν),ifγ=1;O(sk3),ifν=1andγ=1.

    This section shows the numerical results of the AATLM algorithm. All experiments were performed on a PC with an Intel i7-13700UH CPU with 32.00 GB RAM and MATLAB R2022a (64-bit).

    We compare the AATLM algorithm with that of LM1 in [26], the MLM algorithm in [21], and the AMLM algorithm in [23]. Their parameters are chosen as follows:

    LM1:q0=104,q1=0.25,q2=0.75,μ0=1,m0=108;MLM:q0=104,q1=0.25,q2=0.75,μ0=1,m0=108,δ=1;AMLM:q0=104,q1=0.25,q2=0.75,μ0=1,m0=108,δ=1,ˆα=4;AATLM:q0=104,q1=0.25,q2=0.75,θ=0.6,ˉα0=1,μ0=1,m0=108,τ=0.1,a1=4,a2=14.

    The termination condition of the algorithm is JTkFk106 or k1000. In the listed numerical results, "NF", "NJ", "NT=NF+NJ×n", "NK", and "Time" represent the numbers of functions, Jacobian evaluations, total evaluations, iterations, and CPU time, respectively. Examples 1 and 2 are two singular problems from [26]. These problems do not satisfy the local error bound condition, but satisfy the H¨olderian local error bound condition. J(x) of these problems are not Lipschitz continuous, but are H¨olderian continuous.

    Example 4.1. [26] Consider the following Function 1:

    F1(x)=x1+10x2,F2(x)=x3x4,F3(x)=(x22x3)32,F4(x)=(x1x4)32.

    The initial point is x0=(3,1,0,1)T, and the optimal solution is x=(0,0,0,0)T. The results are listed in Table 1.

    Table 1.  Numerical results of Example 4.1.
    LM1 MLM AMLM AATLM
    (n,m) x0 NF/NJ/NT/NK/Time/F NF/NJ/NT/NK/Time/F NF/NJ/NT/NK/Time/F NF/NJ/NT/NK/Time/F
    (4,4) 10x0 11/11/55/10/0.00/7.99e6 19/10/59/9/0.00/7.98e6 17/9/53/8/0.00/4.62e6 17/9/53/8/0.00/2.23e6
    x0 10/10/50/9/0.00/4.14e6 15/8/47/7/0.00/2.76e6 13/7/41/6/0.00/8.90e6 13/7/41/6/0.02/2.77e6
    x0 10/10/50/9/0.00/4.14e6 15/8/47/7/0.00/2.76e6 13/7/41/6/0.00/8.90e6 13/7/41/6/0.00/2.77e6
    10x0 11/11/55/10/0.00/7.99e6 19/10/59/9/0.00/3.15e6 17/9/53/8/0.00/4.62e6 17/9/53/8/0.00/1.63e6
    100x0 13/13/65/12/0.00/7.90e6 23/12/71/11/0.00/6.77e6 21/11/65/10/0.02/1.14e5 17/9/53/8/0.00/1.59e5

     | Show Table
    DownLoad: CSV

    Example 4.2. [26] Consider the following Function 2:

    F1(x)=x1+10x2,F2(x)=x3x4,F3(x)=(x22x3)43,F4(x)=(x1x4)43.

    The initial point is x0=(3,1,0,1)T, and the optimal solution is x=(0,0,0,0)T. The results are listed in Table 2.

    Table 2.  Numerical results of Example 4.2.
    LM1 MLM AMLM AATLM
    (n,m) x0 NF/NJ/NT/NK/Time/F NF/NJ/NT/NK/Time/F NF/NJ/NT/NK/Time/F NF/NJ/NT/NK/Time/F
    (4,4) 10x0 11/11/55/10/0.00/1.47e6 19/10/59/9/0.00/7.46e7 19/10/59/9/0.00/1.26e6 15/8/47/7/0.00/1.75e6
    x0 9/9/45/8/0.00/4.88e6 15/8/47/7/0.00/7.98e7 13/7/41/6/0.00/7.14e6 13/7/41/6/0.00/2.44e6
    x0 9/9/45/8/0.00/4.88e6 13/7/41/6/0.02/8.13e6 13/7/41/6/0.02/2.30e6 13/7/41/6/0.00/1.58e6
    10x0 11/11/55/10/0.00/1.47e6 19/10/59/9/0.00/6.73e7 17/9/53/8/0.00/1.27e6 15/8/47/7/0.00/9.30e7
    100x0 12/12/60/11/0.00/2.67e6 23/12/71/11/0.00/1.43e6 21/11/65/10/0.00/2.31e6 17/9/53/8/0.00/8.23e7

     | Show Table
    DownLoad: CSV

    Tables 1 and 2 show that the numbers of iterations and the function and Jacobian evaluations of the AATLM algorithm are less than that of the LM1, MLM, and AMLM algorithms. Due to the dimension of the problems being small, there is almost no difference in the CPU time.

    Similar to [21,23], we also consider the following singular problem[31]

    ˆF(x)=F(x)J(x)A(ATA)1AT(xx), (4.1)

    where F(x) is a nonsingular test function given by Morˊe, Garbow, and Hillstrom in [32], x is the root of F(x), and ARn×k has full column rank with 1kn. There exists

    ˆJ(x)=J(x)(IA(ATA)1AT),

    with rank nk. In this paper, we define

    ARn×1,A=(1,1,,1)T,

    which means that the rank of ˆJ(x) is n1.

    Example 4.3. [32] Consider the extended Rosenbrock function

    F2i1(x)=10(x2ix2i1),F2i(x)=1x2i1.

    The initial point is x0=(1.2,1,1.2,1,...)T, and the optimal solution is x=(1,1,...,1)T. The results are listed in Table 3.

    Table 3.  Numerical results of the extended Rosenbrock function.
    LM1 MLM AMLM AATLM
    (n,m) x0 NF/NJ/NT/NK/Time/F NF/NJ/NT/NK/Time/F NF/NJ/NT/NK/Time/F NF/NJ/NT/NK/Time/F
    (500,500) 10x0 18/18/9018/17/1.56/2.50e3 259/130/65259/129/18.61/2.23e2 339/170/85339/169/53.36/2.73e2 31/16/8031/15/4.38/1.59e3
    x0 141/141/70641/140/16.06/3.56e2 171/86/43171/85/7.77/2.02e2 313/157/78813/156/27.23/2.84e2 31/16/8031/15/4.67/1.38e3
    x0 55/55/27555/54/4.27/1.38e2 223/112/56223/111/11.09/2.00e2 337/169/84837/168/28.22/2.78e2 101/51/25601/50/13.80/3.60e1
    10x0 21/21/10521/20/1.53/2.76e3 187/94/47187/93/9.14/2.17e2 339/170/85339/169/39.33/2.65e2 31/16/8031/15/1.31/2.03e3
    100x0 24/24/12024/23/4.72/2.40e3 63/32/16063/31/3.36/2.12e3 379/190/95379/189/49.78/2.66e2 35/18/9035/17/2.53/1.23e3
    (1000,1000) 10x0 19/19/19019/18/11.58/1.89e3 323/162/162323/161/224.11/3.48e2 411/206/206411/205/245.09/4.56e2 31/16/16031/15/28.98/2.37e3
    x0 172/172/172172/171/88.95/5.66e2 307/154/154307/153/152.39/3.46e2 421/211/211421/210/333.70/4.51e2 31/16/16031/15/36.92/2.10e3
    x0 62/62/62062/61/70.03/2.00e2 321/161/161321/160/236.45/3.28e2 447/224/224447/223/306.64/4.52e2 181/91/91181/90/199.53/6.03e2
    10x0 22/22/22022/21/33.22/1.91e3 305/153/153305/152/246.50/3.19e2 455/228/228455/227/218.16/4.53e2 31/16/16031/15/10.45/3.00e3
    100x0 25/25/25025/24/12.39/1.65e3 61/31/31061/30/51.36/2.04e3 55/28/28055/27/41.64/1.75e3 35/18/18035/17/15.00/1.71e3

     | Show Table
    DownLoad: CSV

    Example 4.4. [32] Consider the extended Powell singular function

    F4i3(x)=x4i3+10x4i2,F4i2(x)=51/2(x4i1x4i),F4i1(x)=(x4i22x4i1)2,F4i(x)=101/2(x4i3x4i)2.

    The initial point is x0=(3,1,0,1,...)T, and the optimal solution is x=(0,0,...,0)T. The results are listed in Table 4.

    Table 4.  Numerical results of the extended Powell singular function.
    LM1 MLM AMLM AATLM
    (n,m) x0 NF/NJ/NT/NK/Time/F NF/NJ/NT/NK/Time/F NF/NJ/NT/NK/Time/F NF/NJ/NT/NK/Time/F
    (500,500) 10x0 15/15/7515/14/0.95/5.29e5 35/18/9035/17/1.09/1.77e5 27/14/7027/13/0.11/1.51e5 21/11/5521/10/0.14/4.31e5
    x0 12/12/6012/11/0.25/3.80e5 21/11/5521/10/0.48/5.28e5 19/10/5019/9/0.09/3.35e5 17/9/4517/8/0.11/2.45e5
    x0 12/12/6012/11/0.11/3.80e5 21/11/5521/10/0.42/5.28e5 19/10/5019/9/0.03/3.35e5 17/9/4517/8/0.06/2.45e5
    10x0 15/15/7515/14/0.485.29e5 35/18/9035/17/0.39/1.77e5 27/14/7027/13/0.13/1.51e5 21/11/5521/10/0.13/4.31e5
    100x0 19/19/9519/18/0.48/2.06e5 29/15/7529/14/1.17/3.96e5 45/23/11545/22/0.14/5.18e5 27/14/7027/13/0.13/1.19e5
    (1000,1000) 10x0 15/15/15015/14/0.59/2.37e1 25/13/13025/12/0.89/4.42e1 25/13/13025/12/1.53/1.94e1 21/11/11021/10/0.81/2.52e1
    x0 12/12/12012/11/0.58/3.80e1 21/11/11021/10/0.45/3.60e1 19/10/10019/9/1.19/3.80e1 17/9/9017/8/0.75/3.73e1
    x0 12/12/12012/11/0.61/3.80e1 21/11/11021/10/0.75/3.60e1 19/10/10019/9/1.14/3.80e1 17/9/9017/8/0.34/3.73e1
    10x0 15/15/15015/14/0.69/2.37e1 25/13/13025/12/0.56/4.42e1 25/13/13025/12/1.18/1.94e1 21/11/11021/10/0.50/2.52e1
    100x0 19/19/19019/18/0.58/1.40e1 31/16/16031/15/1.00/2.10e1 31/16/16031/15/1.58/2.85e1 27/14/14027/13/1.11/1.08e1

     | Show Table
    DownLoad: CSV

    Tables 3 and 4 show that the AATLM algorithm performs better than the LM1, MLM, and AMLM algorithms on the numbers of iterations and the function and Jacobian evaluations. For most problems, the AATLM algorithm has less CPU time than the other algorithms.

    We tested 100 experiments and all functions are listed in Table 5. Problems 1 and 2 are Examples 1 and 2 from [26], Problems 3 and 4 are Examples 3 and 4, Problems 3–12 are from [32] and have the same form as (4.1), and Problems 13–16 are transformed from the CUTEr library in [33]. All of the test problems satisfy the assumptions required in this paper.

    Table 5.  Test functions.
    Prob. Function (n,m) x0 Prob. Function (n,m) x0
    1 Function 1 (4,4) 10x0,x0,x0,10x0,100x0 2 Function 2 (4,4) 10x0,x0,x0,10x0,100x0
    3 Extended Rosenbrock (500,500) 10x0,x0,x0,10x0,100x0 4 Extended Powell singular (500,500) 10x0,x0,x0,10x0,100x0
    (1000,1000) 10x0,x0,x0,10x0,100x0 (1000,1000) 10x0,x0,x0,10x0,100x0
    5 Freudenstein and Roth (2,2) 10x0,x0,x0,10x0,100x0 6 Powell badly scaled (2,2) 10x0,x0,x0,10x0,100x0
    7 Beale (2,3) 10x0,x0,x0,10x0,100x0 8 Helical valley (3,3) 10x0,x0,x0,10x0,100x0
    9 Wood (4,6) 10x0,x0,x0,10x0,100x0 10 Extended Wood (500,750) 10x0,x0,x0,10x0,100x0
    11 Trigonometric (500,500) 10x0,x0,x0,10x0,100x0 12 Brown almost-linear (500,500) 10x0,x0,x0,10x0,100x0
    (1000,1000) 10x0,x0,x0,10x0,100x0 (1000,1000) 10x0,x0,x0,10x0,100x0
    13 EG2 (500,500) x0,x0 14 ARWHEAD (500,500) 10x0,10x0
    (1000,1000) x0,x0 (1000,1000) 10x0,10x0
    15 LIARWHD (500,500) 10x0,x0,10x0 16 TRIDIA (500,500) 10x0,x0,10x0
    (1000,1000) 10x0,x0,10x0 (1000,1000) 10x0,x0,10x0

     | Show Table
    DownLoad: CSV

    According to Dolan's [34] evaluation criteria, we show the performance profiles for the numbers of function evaluations, Jacobian evaluations, iterations, and CPU time of the algorithm in Figure 1. The parameter τ represents the performance ratio. When τ is close to 1 and Ψ remains constant, the numbers of Jacobian evaluations or iterations of the current algorithm are closer to the minimum value than the other algorithms. When τ is a constant and Ψ is close to 1, this means that the current algorithm can solve more problems.

    Figure 1.  Performance profiles of the numerical results.

    It can be seen from Figure 1 that the AATLM algorithm performs better than other algorithms in the numbers of Jacobian evaluations and iterations. From Figure 1(a), the AATLM algorithm performs better than the MLM and AMLM algorithms in the number of function evaluations. Since the LM1 algorithm calculates Fk only once in each iteration, the LM1 algorithm has a higher curve in Figure 1(a) when τ[1,2.38]. In Figure 1(b), the AATLM algorithm can solve more testing problems with less Jacobian evaluations. When τ(1.49,5], the LM1 algorithm performs better than the MLM and AMLM algorithms. According to Figure 1(c), the AATLM can solve 86% of the problems with the least number of iterations, while the LM1, MLM, and AMLM can solve 12%, 32%, and 34% of the problems, respectively, which means that the AATLM algorithm could solve more problems with fewer iterations. In Figure 1(d), the LM1, MLM, AMLM, and AATLM algorithms can solve 60%, 54%, 42%, and 68% of the problems with the least CPU time, respectively. In summary, the results indicate that the AATLM algorithm is a promising method for solving nonlinear equations.

    In addition, we also consider the influence of different θ on the AATLM algorithm. We show the performance profiles for the numbers of Jacobian evaluations and the iterations of the AATLM algorithm in Figure 2, where θ is chosen from the set {0.2,0.4,0.6,0.8}. We find that when θ in the AATLM algorithm is 0.6, the curve is higher than the others. This means that the new algorithm with θ=0.6 can solve more problems with fewer Jacobian evaluations and iterations.

    Figure 2.  Performance profiles of the numerical results with different θ.

    In this paper, we constructed a new LM parameter in the form of a convex combination to obtain the LM step and the approximate step. A new modified Metropolis criterion was introduced to update the upper bound of the approximate step size, so as to obtain an adaptive acceleration two-step LM algorithm. The global and local convergence of the new algorithm were studied under the H¨olderian local error bound condition and the H¨olderian continuity of the Jacobian, which are more general than the local error bound condition and the Lipschitz continuity of the Jacobian. The numerical results showed the efficiency of the AATLM algorithm. In the course of research, we noticed that different LM parameters could be considered at different stages of the algorithm. In future work, we will explore a new LM parameter and introduce a nonmonotone technique into the two-step LM algorithm to solve nonlinear equations.

    Dingyu Zhu: conceptualization, writing–original draft, software, methodology, writing–review and editing; Yueting Yang: writing–original draft, supervision, funding acquisition, methodology, project administration, writing–review and editing; Mingyuan Cao: writing–original draft, supervision, funding acquisition, methodology, project administration, writing–review and editing. All authors have read and approved the final version of the manuscript for publication.

    The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

    The authors would like to thank the Science and Technology Development Planning Grant Program of Jilin Province (YDZJ202101ZYTS167, 20200403193SF) and the Graduate Innovation Project of Beihua University (2023005, 2023035).

    The authors declare no conflicts of interest.



    [1] G. D. A. Moura, S. D. T. M. Bezerra, H. P. Gomes, S. A. D. Silva, Neural network using the Levenberg–Marquardt algorithm for optimal real-time operation of water distribution systems, Urban Water J., 15 (2018), 692–699. https://doi.org/10.1080/1573062X.2018.1539503 doi: 10.1080/1573062X.2018.1539503
    [2] Y. J. Sun, P. P. Wang, T. T. Zhang, K. Li, F. Peng, C. G. Zhu, Principle and performance analysis of the Levenberg–Marquardt algorithm in WMS spectral line fitting, Photonics, 9 (2022), 999. https://doi.org/10.3390/photonics9120999 doi: 10.3390/photonics9120999
    [3] A. Alloqmani, O. Alsaedi, N. Bahatheg, R. Alnanih, L. Elrefaei, Design principles-based interactive learning tool for solving nonlinear equations, Comput. Syst. Sci. Eng., 40 (2022), 1023–1042. https://doi.org/10.32604/csse.2022.019704 doi: 10.32604/csse.2022.019704
    [4] Z. W. Liao, F. Y. Zhu, W. Y. Gong, S. J. Li, X. Y. Mi, AGSDE: Archive guided speciation-based differential evolution for nonlinear equations, Appl. Soft Comput., 122 (2022), 108818. https://doi.org/10.1016/j.asoc.2022.108818 doi: 10.1016/j.asoc.2022.108818
    [5] Z. Seifi, A. Ghorbani, A. Abdipour, Time-domain analysis and experimental investigation of electromagnetic wave coupling to RF/microwave nonlinear circuits, J. Electromagnet Wave., 35 (2021), 51–70. https://doi.org/10.1080/09205071.2020.1825994 doi: 10.1080/09205071.2020.1825994
    [6] A. Rothwell, Numerical methods for unconstrained optimization, In: Optimization methods in structural design, Cham: Springer, 2017, 83–106. https://doi.org/10.1007/978-3-319-55197-5
    [7] G. L. Yuan, M. J. Zhang, A three-terms Polak-Ribière-Polyak conjugate gradient algorithm for large-scale nonlinear equations, J. Comput. Appl. Math., 286 (2015), 186–195. https://doi.org/10.1016/j.cam.2015.03.014 doi: 10.1016/j.cam.2015.03.014
    [8] G. L. Yuan, Z. X. Wei, X. W. Lu, A BFGS trust-region method for nonlinear equations, Computing, 92 (2011), 317–333. https://doi.org/10.1007/s00607-011-0146-z doi: 10.1007/s00607-011-0146-z
    [9] J. H. Zhang, Y. Q. Wang, J. Zhao, On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations, J. Comput. Appl. Math., 425 (2023), 115065. https://doi.org/10.1016/j.cam.2023.115065 doi: 10.1016/j.cam.2023.115065
    [10] J. N. Wang, X. Wang, L. W. Zhang, Stochastic regularized Newton methods for nonlinear equations, J. Sci. Comput., 94 (2023), 51. https://doi.org/10.1007/s10915-023-02099-4 doi: 10.1007/s10915-023-02099-4
    [11] R. Behling, D. S. Gonçalves, S. A. Santos, Local convergence analysis of the Levenberg–Marquardt framework for Nonzero–Residue nonlinear least-squares problems under an error bound condition, J. Optim. Theory Appl., 183 (2019), 1099–1122. https://doi.org/10.1007/s10957-019-01586-9 doi: 10.1007/s10957-019-01586-9
    [12] E. H. Bergou, Y. Diouane, V. Kungurtsev, Convergence and complexity analysis of a Levenberg–Marquardt algorithm for inverse problems, J. Optim. Theory Appl., 185 (2020), 927–944. https://doi.org/10.1007/s10957-020-01666-1 doi: 10.1007/s10957-020-01666-1
    [13] K. Levenberg, A method for the solution of certain non-linear problems in least squares, Quart. Appl. Math., 2 (1944), 164–168. https://doi.org/10.1090/qam/10666 doi: 10.1090/qam/10666
    [14] D. W. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, J. Soc. Ind. Appl. Math., 11 (1963), 431–441. https://doi.org/10.1137/0111030 doi: 10.1137/0111030
    [15] N. Yamashita, M. Fukushima, On the rate of convergence of the Levenberg–Marquardt method, In: Topics in numerical analysis, computing supplementa, Vienna: Springer, 2001,239–249. https://doi.org/10.1007/978-3-7091-6217-0_18
    [16] J. Y. Fan, Y. X. Yuan, On the convergence of a new Levenberg–Marquardt method, Report, Institute of Computational Mathematics and Scientific/Engineering Computing, Beijing: Chinese Academy of Science, 2001.
    [17] J. Y. Fan, A Modified Levenberg–Marquardt algorithm for singular system of nonlinear equations, J. Comput. Math., 21 (2003), 625–636.
    [18] K. Amini, F. Rostami, G. Caristi, An efficient Levenberg–Marquardt method with a new LM parameter for systems of nonlinear equations, Optimization, 67 (2018), 637–650. https://doi.org/10.1080/02331934.2018.1435655 doi: 10.1080/02331934.2018.1435655
    [19] C. F. Ma, L. H. Jiang, Some research on Levenberg–Marquardt method for the nonlinear equations, Appl. Math. Comput., 184 (2007), 1032–1040. https://doi.org/10.1016/j.amc.2006.07.004 doi: 10.1016/j.amc.2006.07.004
    [20] J. Y. Fan, J. Y. Pan, A note on the Levenberg–Marquardt parameter, Appl. Math. Comput., 207 (2009), 351–359. https://doi.org/10.1016/j.amc.2008.10.056 doi: 10.1016/j.amc.2008.10.056
    [21] J. Y. Fan, The modified Levenberg–Marquardt method for nonlinear equations with cubic convergence, Math. Comp., 81 (2012), 447–466. https://doi.org/10.1090/S0025-5718-2011-02496-8 doi: 10.1090/S0025-5718-2011-02496-8
    [22] J. Y. Fan, J. L. Zeng, A Levenberg–Marquardt algorithm with correction for singular system of nonlinear equations, Appl. Math. Comput., 219 (2013), 9438–9446. https://doi.org/10.1016/j.amc.2013.03.026 doi: 10.1016/j.amc.2013.03.026
    [23] J. Y. Fan, Accelerating the modified Levenberg–Marquardt method for nonlinear equations, Math. Comp., 83 (2014), 1173–1187. https://doi.org/10.1090/S0025-5718-2013-02752-4 doi: 10.1090/S0025-5718-2013-02752-4
    [24] X. D. Zhu, G. H. Lin, Improved convergence results for a modified Levenberg–Marquardt method for nonlinear equations and applications in MPCC, Optim. Method. Softw., 31 (2016), 791–804. https://doi.org/10.1080/10556788.2016.1171863 doi: 10.1080/10556788.2016.1171863
    [25] H. Y. Wang, J. Y. Fan, Convergence rate of the Levenberg–Marquardt method under Hölderian local error bound, Optim. Method. Softw., 35 (2020), 767–786. https://doi.org/10.1080/10556788.2019.1694927 doi: 10.1080/10556788.2019.1694927
    [26] M. L. Zeng, G. H. Zhou, Improved convergence results of an efficient Levenberg–Marquardt method for nonlinear equations, J. Appl. Math. Comput., 68 (2022), 3655–3671. https://doi.org/10.1007/s12190-021-01599-6 doi: 10.1007/s12190-021-01599-6
    [27] L. Chen, Y. F. Ma, A modified Levenberg–Marquardt method for solving system of nonlinear equations, J. Appl. Math. Comput., 69 (2023), 2019–2040. https://doi.org/10.1007/s12190-022-01823-x doi: 10.1007/s12190-022-01823-x
    [28] N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, E. Teller, Equation of state calculations by fast computing machines, J. Chem. Phys., 21 (1953), 1087–1092. https://doi.org/10.1063/1.1699114 doi: 10.1063/1.1699114
    [29] R. Behling, A. Iusem, The effect of calmness on the solution set of systems of nonlinear equations, Math. Program., 137 (2013), 155–165. https://doi.org/10.1007/s10107-011-0486-7 doi: 10.1007/s10107-011-0486-7
    [30] G. W. Stewart, J. G. Sun, Matrix perturbation theory, New York: Academic Press, 1990.
    [31] R. B. Schnabel, P. D. Frank, Tensor methods for nonlinear equations, SIAM J. Numer. Anal., 21 (1984), 815–843. https://doi.org/10.1137/0721054 doi: 10.1137/0721054
    [32] J. J. Moré, B. S. Garbow, K. E. Hillstrom, Testing unconstrained optimization software, ACM T. Math. Software, 7 (1981), 17–41. https://doi.org/10.1145/355934.355936 doi: 10.1145/355934.355936
    [33] N. I. M. Gould, D. Orban, P. L. Toint. CUTEr and SifDec: A constrained and unconstrained testing environment, revisited, ACM T. Math. Software, 29 (2003), 373–394. https://doi.org/10.1145/962437.962439 doi: 10.1145/962437.962439
    [34] E. D. Dolan, J. J. Moré, Benchmarking optimization software with performance profiles, Math. Program., 91 (2002), 201–213. https://doi.org/10.1007/s101070100263 doi: 10.1007/s101070100263
  • Reader Comments
  • © 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1112) PDF downloads(53) Cited by(0)

Figures and Tables

Figures(2)  /  Tables(5)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog