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

1.   Introduction

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

where $F\left (x \right) :\mathbb{R}^{n} \to \mathbb{R}^{m}$ 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 $(\rm 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 $\tilde{d}_k$ as

where $F_{k} = F\left (x_{k} \right)$ and $J_{k} = {F}'(x_k)$ is the Jacobian of $F(x)$ at $x_{k}$, $\lambda_k > 0$ is an appropriate LM parameter updated with each iteration, and $I\in \mathbb{R}^{n\times n}$ is the identity matrix. Throughout the paper, $\left \| \cdot \right \|$ 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 $\lambda_k = \|F_k\|^2$. Fan and Yuan^[16] proposed $\lambda_k = \|F_k\|$, which overcame the shortcoming that the LM step was too small when the iteration $x_k$ was far away from the solution. Subsequently, Fan^[17] chose $\lambda_k$ as $\mu_k\|F_k\|$, in which $\mu_k$ was updated by a trust region technique. Amini^[18] proposed the LM parameter $\frac{\mu_k\|F_k\|}{1+\|F_k\|}$, and proved the convergence under the local error bound condition. On the other hand, Ma and Jiang^[19] chose the LM parameter as $\theta\|F_k\|+(1-\theta)\|J_k^T F_k\|$ with $\theta\in[0, 1]$ and obtained the quadratic convergence rate under the local error bound condition. Fan and Pan^[20] proposed the LM parameter

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 $\tilde{d}_k$ in (1.2) and the approximate step

where $y_{k} = x_{k}+\tilde{d}_{k}$ and $\lambda_k = \mu_k\|F_k\|^\delta$ with $\delta\in[1,2]$. Using $J_k$ instead of $J(y_k)$ 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:

where $\lambda_k = \mu_k\|F_k\|^\delta$ with $\delta\in(0, 2]$ and the convergence rate was $\min\left\{2, 1+2\delta\right\}$ under the same conditions. Above all, the trial step of each iteration became

and the step size was a unit. Then, Fan^[23] proposed the accelerated modified LM method, which introduced a line search along $\hat{d}_k$ of (1.4). The step size was the solution of

By a simple derivation,

If $J_k\hat{d}_k$ was close to $\mathbf{0}$, $\tilde{\alpha}_k$ would be too large. An upper bound $\hat{\alpha} > 1$ for ${\alpha}$ in (1.5) was set and the step size was chosen as $\alpha_k = \min(\tilde{\alpha}_k, \hat{\alpha})$. Moreover, the trust region ratio was introduced by

which was used to decide whether to accept the trial step and updated the parameter $\mu_k$. However, the choice strategy of $\hat{\alpha}$ 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 $\lambda_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$\ddot{\rm o}$lderian 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$\ddot{\rm o}$lderian 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$\ddot{\rm o}$lderian 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 $\frac{\|F_k\|}{1+\|F_k\|}$ and $\frac{\|J_k^T F_k\|}{1+\|J_k^T F_k\|}$ 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$\ddot{\rm o}$lderian local error bound condition and the H$\ddot{\rm o}$lderian 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$\ddot{\rm o}$lderian continuity of the Jacobian is presented. In Section 3, we derive the convergence rate of the new algorithm under the H$\ddot{\rm o}$lderian local error bound condition and the H$\ddot{\rm o}$lderian 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.

2.   Algorithm and global convergence

In this section, we propose a novel two-step LM method with a new parameter $\lambda_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$\ddot{\rm o}$lderian continuity of the Jacobian which is weaker than the Lipschitz continuity.

Since the LM step $\tilde{d}_k$ in (1.2) and the approximate step $\hat{d}_k$ in (1.4) rely on the choice of $\lambda_k$, we construct a new LM parameter

When $x_k$ is far from the optimal solution, $\|F_k\|$ and $\|J_k^T F_k\|$ are large enough to make $\frac{\|F_k\|}{1+\|F_k\|}$ and $\frac{\|J_k^T F_k\|}{1+\|J_k^T F_k\|}$ close to 1. At this time, $\lambda_k$ is close to $\mu_k$. Conversely, when $x_k$ approaches the optimal solution, $\theta\frac{\|F_k\|}{1+\|F_k\|}$ and $\left(1-\theta\right)\frac{\|J_k^T F_k\|}{1+\|J_k^T F_k\|}$ degenerate into $\theta\|F_k\|$ and $\left(1-\theta\right)\|J_k^T F_k\|$, which indicates that $\lambda_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

where $\alpha_k$ is the step size along $\hat{d}_k$. Unlike the reference ^[23], we will propose a new upper bound $\hat{\alpha}_k$ of the step size in (1.5). Similar to the Metropolis criterion suggested by ^[28], we give a new modified Metropolis criterion

where $0 < \tau < 1$ represents a sufficiently small constant and $T_k$ is the temperature decreasing to 0 as $k\to\infty$ by the cooling schedule. If $|r_{k-1}-1|\leq \tau$, $r_{k-1}$ is close enough to $1$, and we set $\bar{\alpha}_k$ as 1. Otherwise, $|r_{k-1}-1| > \tau$, we set $\bar{\alpha}_k = e^{-\frac{|r_{k-1}-1|}{T_{k}}}$, which can be regarded as a probability and also decreases to 0 as $k\to \infty$. This is similar to the simulated annealing. We define the upper bound of the step size as $\hat{\alpha}_{k} = 1+\bar{\alpha}_k$. In each iteration, $\hat{\alpha}_{k}$ is self-adaptively updated by (2.2). Now, we set the step size along $\hat{d}_k$ as

where $\tilde{\alpha}_k$ is given by (1.6). Moreover, since $\phi(\alpha)$ has the monotonically increasing property on $[1, \tilde{\alpha}_k]$ and $\alpha_k\in [1, \tilde{\alpha}_k]$, it is easy to find $\phi(\alpha_k)\geq \phi(1)$. This implies

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

Remark 2.1. In Step 2, $\tilde{\alpha}_k$ is computed by (1.6), which is proposed in ^[23] with $J_k \hat{d}_k\ne \mathbf{0}$. In ^[23], when $J_k \hat{d}_k$ was close to $\mathbf{0}$, $\hat{\alpha}$ was set as the upper bound of $\tilde{\alpha}_k$. However, the case of $J_k \hat{d}_k = \mathbf{0}$ was not mentioned. Note that, if $\hat{d}_k\ne \mathbf{0}$, then $J_k \hat{d}_k\ne \mathbf{0}$. In fact, if $J_k\hat{d}_k = \mathbf{0}$ holds, from the definition of $\hat{d}_k$, we have

Due to $\hat{d}_k$ being the solution of

it is easy to obtain

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 $\hat{d}_k = \mathbf{0}$, we set $s_k = \tilde{d}_k$, 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$\ddot{\rm o}$lderian continuous of order $\nu\in(0, 1]$, i.e., there exists a positive constant $\kappa_{hj}$ such that

(b) The Jacobian $J(x)$ is bounded above, i.e., there exists a positive constant $\kappa_{bj}$ such that

By using (2.8), we have

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

for all $k$.

Proof. Since $\tilde{d}_k$ is the solution of the following trust region subproblem,

for any $\beta\in[0, 1]$, it follows:

Then,

If $\hat{d}_k = \mathbf{0}$, (2.12) implies that the conclusion of Lemma 2.1 holds. Otherwise, $\hat{d}_k$ is the solution of (2.7), and it holds that

According to (2.4), we have

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 $\{x_k\}$ generated by the AATLM algorithm satisfies

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

Let the sets of the indices $S_1$ and $S_2$ be

where $S_1$ is an infinite set. Consider the following two cases.

Case 1: $S_2$ is finite. We have

is also finite. Let $\tilde{k}$ be the largest index of $S_3$, which means $x_{k+1} = x_k$ holds for all $k\in \{k > \tilde{k}|k\in S_1\}$. Define the indicator set

We notice that $\|J_{k+1}^T F_{k+1}\|\geq\delta$ and $x_{k+2} = x_{k+1}$ for all $k\in S_4$. Otherwise, if $x_{k+2}\neq x_{k+1}$, then $k+1\in S_3$, which means that $\tilde{k}$ is not the largest index of $S_3$. It is easy to get $k+1\in S_4$. By induction, $\|J_k^T F_k\|\geq\delta$ and $x_{k+1} = x_k$ hold for all $k > \tilde{k}$.

According to Step 3 in the AATLM algorithm, $r_k < q_0$ means that $x_{k+1} = x_k$ holds for all $k > \tilde{k}$, and from (2.1), (2.5), and (2.6), we obtain:

which implies that

From (2.9), (2.10), (2.7), (2.15), and the definition of $\hat{d}_k$, we find

for all sufficiently large $k$, where $\bar{c}$ is a positive constant. So, we conclude

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

and

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

which means that $r_k\rightarrow 1$. According to the updating rule of $\mu_k$, we know that there exists a positive constant $M > m_0$, such that $\mu_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: $S_2$ is infinite. From Lemma 2.1, (2.10), and the fact that $s_k$ is accepted by the AATLM algorithm, we have

and $x_{k+1}-x_k = 0$ if $k\notin S_2$, which implies that

and from the definition of $\tilde{d}_k$, we obtain:

Similarly to (2.16) and (2.17), there exists a constant $\tilde{c} > 0$, which makes it true for all sufficiently large $k\in S_2$, so,

It follows from (2.19) that

Moreover, combining with Assumption 2.1, we get

Since (2.14) holds for sufficiently large $k$, there exists a large $\hat{k}$, such that$\|J_{\hat k}^T F_{\hat k}\|\geq\delta$, and

By induction, we find that $\|J_k^T F_k\|\geq \frac{\delta}{2}$ holds for all $k\geq\hat{k}$, and then, we can derive from (2.19)–(2.22) that

and thus,

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

Therefore, there exists a positive constant $M > m_0$ such that $\mu_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 $x^* \in X^*$ such that the sequence $\{x_k\}$ generated by the AATLM algorithm converges to $x^*$. For the sufficient large $k$, if $x_k$ lies in a neighborhood of $x^*$, then $x_{k+1}$ and $y_k$ also lie in the neighborhood.

3.   Convergence rate of the AATLM algorithm

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$\ddot{\rm o}$lderian local error bound and H$\ddot{\rm o}$lderian continuity of the Jacobian, we use the following assumption.

Assumption 3.1. (a) $F(x)$ provides a H$\ddot{\rm o}$lderian local error bound of order $\gamma\in(0, 1]$ in some neighborhoods of $x^{*}\in X^{*}$, i.e., there exist constants $c > 0$ and $0 < b < 1$, such that

and when $\gamma = 1$, $F(x)$ provides the local error bound.

(b) The Jacobian $J(x)$ is H$\ddot{\rm o}$lderian continuous of order $\nu\in(0, 1]$, i.e., there exists a constant $\kappa_{hj} > 0$ such that

From (3.2), we immediately have

and there is a constant $\kappa_{bf} > 0$ such that

Moreover, we denote $\bar{x}_k$ as the closest point to $x_k$ in $X^{*}$, i.e., ${\rm dist}\left(x_k, X^{*}\right) = \|\bar{x}_k-x_k\|$.

Combining the results given by Behling and Iusem^[29], we assume that ${\rm rank}(J(\bar x)) = r$ for all $\bar{x}\in N(x^{*}, b)\cap X^{*}$. Suppose the singular value decomposition (SVD) of $J(\bar{x}_k)$ is

where $\bar{\Sigma}_{1} = {\rm diag}(\bar{\sigma}_{1}, ..., \bar{\sigma}_{r})$, and $\bar{\sigma}_{1}\geq \bar{\sigma}_{2}\geq...\geq \bar{\sigma}_{r} > 0$. Thus, we obtain:

where $\Sigma_{1} = {\rm diag}(\sigma_{1}, ..., \sigma_{r})$, $\sigma_{1}\geq \sigma_{2} \geq...\geq \sigma_{r} > 0$, and $\Sigma_{2} = {\rm diag}(\sigma_{r+1}, ..., \sigma_{r+q})$, $\sigma_{r}\geq \sigma_{r+1}\geq \sigma_{r+2}\geq...\geq\sigma_{r+q} > 0.$ Following from the theory of matrix perturbation^[30], and the H$\ddot{\rm o}$lderian continuity of $J_k$, we know

which yields

Lemma 3.1. Under the conditions of Assumption 3.1, if $x_k, y_k\in N\left(x^{*}, \frac{b}{4}\right)$, and

there exists a constant $c_1 > 0$ such that

Proof. Since $x_k\in N\left(x^{*}, \frac{b}{4}\right) = \left\{x|\|x_k-x^{*}\|\leq \frac{b}{4}\right\}$, it follows from the definition of $\bar{x}_k$ that

which means $\bar{x}_k \in N\left(x^{*}, \frac{b}{2}\right)$.

From the definition of $\lambda_k$, we set $\lambda_{1k} = \frac{\mu_k \theta\|F_k\|}{1+\|F_k\|}$, and $\lambda_{2k} = \frac{\mu_k (1-\theta)\|J_k^T F_k\|}{1+\|J_k^T F_k\|}$. Then, together with (3.1) and $\mu_k > m_0$, we have

As we know, $\|F_k\|^2 = F_k^T F_k = F_k^T [F(\bar{x}_k)+J_k(\bar{x}_k -x_k)]+F_k^T H_k$, in which $H_k = F_k-F(\bar{x}_k)-J_k(\bar{x}_k -x_k)$. So, we have $F_k^T J_k(\bar{x}_k -x_k) = \|F_k\|^2-F_k^T H_k$. From the Assumption 3.1, and $\nu > 2\left(\frac{1}{\gamma}-1\right)$, it is clear that

holds for some $\hat{c} > 0$. In the same way, we obtain:

Thus, we find that the LM parameter $\lambda_k$ satisfies:

where $\grave{c} > 0$.

In addition, the equivalence problem of (2.11) is

which has the optimal solution $\tilde{d}_k$. Combining with (3.7), we have that

holds for some $c_{1, 1} > 0$, which means that

holds for some $c_{1, 2} > 0$.

By the definition of $\hat{d}_k$ and (3.3), we obtain

By using the SVD of $J_k$, we have

Due to the sequence $\{x_k\}$ converging to the nonempty solution set $X^{*}$, if $\kappa_{hj}\|\bar{x}_k-x_k\|^\nu\leq\frac{\bar{\sigma}_r}{2}$ for any sufficiently large $k$, from the lower bound of $\lambda_k$, we get

and

where $\acute{c} > 0$ is a constant. Then, combining with (3.9), (3.10), the lower bound of $\lambda_k$, and the range of $\nu$, we can deduce

where $\check{c} > 0$ is a constant, and

From assumption $\nu > \max\left\{2\left(\frac{1}{\gamma}-1\right), \frac{1}{2\gamma}\right\}$ and the condition $\nu, \gamma\in(0, 1]$, we know $\nu > \frac{1}{\gamma}-1$, and $\gamma\in(\frac{2}{3}, 1]$. It is easy to find $\nu\in(\frac{1}{2}, 1]$. As the exponent $\gamma$ increases, smaller values on the exponent $\nu$ are allowed. We obtain:

which implies

Due to the definition of $s_k$, it is easy to know

The proof is complete. □

Lemma 3.2. Under the conditions of Assumption 3.1, if $x_k, y_k\in N\left(x^{*}, \frac{b}{4}\right)$, and

there exists a constant $M > m_0$, such that

holds for all large $k$.

Proof. We consider the following two cases.

Case 1: If $\|\bar{x}_k-x_k\|\leq \|\tilde{d}_k\|$, it follows from (3.1), (3.3), and $\nu > 2\left(\frac{1}{\gamma}-1\right)$ that

where $c_{2, 1} > 0$ is a constant.

Case 2: If $\|\bar{x}_k-x_k\| > \|\tilde{d}_k\|$, it follows from the second and third inequalities of (3.14), that we have

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

where $c_{2, 2} > 0$ is a constant with $\|\bar{y}_k-y_k\|\leq \|\hat{d}_k\|$, and

holds for $\|\bar{y}_k-y_k\| > \|\hat{d}_k\|$.

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

where

From $(J_k^T F_k)^T \tilde{d}_k < 0$, we can derive that $\|F(y_k)\| < \|F_k\|$. Combining (3.1) and (3.3) with (3.12) yields

Due to $\nu > \max\left\{2\left(\frac{1}{\gamma}-1\right), \frac{1}{2\gamma}\right\}$, it is clear that $r_k\rightarrow 1$. 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 $x_k, y_k\in N\left(x^{*}, \frac{b}{4}\right)$ and $\nu > 2\left(\frac{1}{\gamma}-1\right)$, we have

where $\grave{c} > 0$ is a constant.

Proof. It follows from (3.7) that

By using Lemma 3, (3.2), (3.4), and the definition of $\lambda_k$, we conclude

which means that $\lambda_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 $J_k$, we get

Lemma 3.4. Under the conditions of Assumption 3.1, if $x_k, y_k\in N\left(x^{*}, \frac{b}{4}\right)$, we have

(a) $\|U_1U_1^T F_k\|\leq \kappa_{bf}\|\bar{x}_k-x_k\|;$

(b) $\|U_2U_2^T F_k\|\leq (\frac{\kappa_{hj}}{1+\nu}+\kappa_{hj})\|\bar{x}_k-x_k\|^{1+\nu};$

(c) $\|U_3U_3^T F_k\|\leq \frac{\kappa_{hj}}{1+\nu}\|\bar{x}_k-x_k\|^{1+\nu}.$

Proof. We could obtain (a) directly from (3.4). Let $\bar{s}_k = -J_k^{+}F_k$, where $J_k^{+}$ is the pseudo-inverse of $J_k$ and $\bar{s}_k$ is the least squares solution of ${\rm min}\|F_k+J_ks\|$. Then, we obtain (c) from (3.3) that

Let $\tilde{J}_k = U_1\Sigma_1V_1^T$ and $\tilde{s}_k = -\tilde{J}_k^{+}F_k$, where $\tilde{J}_k^{+}$ is the pseudo-inverse of $\tilde{J}_k$ and $\tilde{s}_k$ is the least squares solution of ${\rm min}\|F_k+\tilde{J}_ks\|$. Together with (3.4) and (3.5) implies

which means that we obtain (b) from the orthogonality of $U_2$ and $U_3$. The proof is complete. □

Lemma 3.5. Under the conditions of Assumption 3.1, if $x_k, y_k\in N\left(x^{*}, \frac{b}{4}\right)$ and $\nu > \max\left\{2\left(\frac{1}{\gamma}-1\right), \frac{1}{2\gamma}\right\}$, we have

(a) $\|U_1U_1^T F(y_k)\|\leq O\left(\|\bar{x}_k-x_k\|^{1+\nu}\right);$

(b) $\|U_2U_2^T F(y_k)\|\leq O\left(\|\bar{x}_k-x_k\|^{\nu+\gamma(1+\nu)}\right);$

(c) $\|U_3U_3^T F(y_k)\|\leq O\left(\|\bar{x}_k-x_k\|^{\nu+\gamma(1+\nu)}\right).$

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

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

Thus, it is clear that

which indicates that the following condition of the H$\ddot{\rm o}$lderian local error bound,

is obtained.

Then, we let $\bar{p}_k = -J_k^{+}F(y_k)$, and $\bar{p}_k$ is the least squares solution of ${\rm min}\|F(y_k)+J_kp\|$. From (3.2), (3.3), (3.9), (3.24), and the range of $\nu$, we have

Let $\tilde{J}_k = U_1\Sigma_1V_1^T$ and $\tilde{p}_k = -\tilde{J}_k^{+}F(y_k)$, where $\tilde{p}_k$ is the least squares solution of ${\rm min}\|F(y_k)+\tilde{J}_kp\|$. It follows from (3.2), (3.3), (3.6), (3.8), (3.24), and the range of $\nu$ that

and then, together with the orthogonality of $U_2$ and $U_3$, we obtain (b) and Lemma 3.5 is proved. □

Theorem 3.1. Under the conditions of Assumption 3.1, if $x_k, y_k\in N\left(x^{*}, \frac{b}{4}\right)$, $\nu > 2\left(\frac{1}{\gamma}-1\right)$, and $\nu > \frac{1}{2\gamma}$, the sequence $\{x_k\}$ generated by the AATLM algorithm converges to the solution set of (1.1) with order $\nu\gamma+\gamma^{2}(1+\nu)$.

Proof. From (3.5), (3.20), Lemma 3.5, and the upper bound of $\|\lambda_k^{-1}\Sigma_2\|$, we have

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

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

where $\xi = \min\left\{\nu+\gamma(1+\nu), 1+2\nu, 3\nu+\gamma(1+\nu)-\frac{1}{\gamma}, (1+\nu)^2, (1+\nu)(2\nu+\gamma(1+\nu)-\frac{1}{\gamma})\right\}$. Consider $\gamma\in(\frac{2}{3}, 1]$ and $\nu\in(\frac{1}{2}, 1]$, and we have

and

By $\nu > \frac{1}{2\gamma}$ and $\gamma\in(\frac{2}{3}, 1]$, we derive

and

These mean that $\xi = \nu+\gamma(1+\nu)$ and $\{x_k\}$ converges to some solution of (1.1) with the rate of $\nu\gamma+\gamma^2(1+\nu)$.

Moreover, together with $\|\bar{x}_k-x_k\|\leq \|\bar{x}_{k+1}-x_{k}\| \leq\|\bar{x}_{k+1}-x_{k+1}\|+\|s_k\|$ and (3.27), we have

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

By the above explanation, along with the condition that $\nu > {\rm max}\left\{2\left(\frac{1}{\gamma}-1\right), \frac{1}{2\gamma}\right\}$, we can conclude that Theorem 3.1 is valid. The proof is complete. □

In addition, when the values of $\nu$ and $\gamma$ are different, we have convergence rates as follows

4.   Numerical experiments

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:

The termination condition of the algorithm is $\|J_{k}^T F_{k}\|\leq 10^{-6}$ or $k\geq1000$. In the listed numerical results, "NF", "NJ", $"{\rm NT = NF+NJ}\times n"$, "NK", and $"{\rm 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$\ddot{\rm o}$lderian local error bound condition. $J(x)$ of these problems are not Lipschitz continuous, but are H$\ddot{\rm o}$lderian continuous.

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

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

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

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

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]

where $F(x)$ is a nonsingular test function given by Mor$\acute{e}$, Garbow, and Hillstrom in ^[32], $x^{*}$ is the root of $F(x)$, and $A\in \mathbb{R}^{n\times k}$ has full column rank with $1\leq k\leq n$. There exists

with rank $n-k$. In this paper, we define

which means that the rank of $\hat{J}(x^{*})$ is $n-1$.

Example 4.3. ^[32] Consider the extended Rosenbrock function

The initial point is $x_0 = (-1.2, 1, -1.2, 1, ...)^T$, and the optimal solution is $x^{*} = (1, 1, ..., 1)^T$. The results are listed in Table 3.

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

The initial point is $x_0 = (3, -1, 0, 1, ...)^T$, and the optimal solution is $x^{*} = (0, 0, ..., 0)^T$. The results are listed in Table 4.

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.

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 $\tau$ represents the performance ratio. When $\tau$ is close to $1$ and ${\it\Psi}$ remains constant, the numbers of Jacobian evaluations or iterations of the current algorithm are closer to the minimum value than the other algorithms. When $\tau$ is a constant and ${\it\Psi}$ is close to 1, this means that the current algorithm can solve more problems.

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 $F_k$ only once in each iteration, the LM1 algorithm has a higher curve in Figure 1(a) when $\tau\in[1, 2.38]$. In Figure 1(b), the AATLM algorithm can solve more testing problems with less Jacobian evaluations. When $\tau\in(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 $\theta$ 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 $\theta$ is chosen from the set $\{0.2, 0.4, 0.6, 0.8\}$. We find that when $\theta$ in the AATLM algorithm is $0.6$, the curve is higher than the others. This means that the new algorithm with $\theta = 0.6$ can solve more problems with fewer Jacobian evaluations and iterations.

5.   Conclusions

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$\ddot{\rm o}$lderian local error bound condition and the H$\ddot{\rm o}$lderian 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.

Author contributions

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.

Use of AI tools declaration

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

Acknowledgments

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).

Conflict of interest

The authors declare no conflicts of interest.