Convergence properties of a family of inexact Levenberg-Marquardt methods

1.   Introduction

Consider the system of nonlinear equations

where $F(x):\mathbb{R}^n\rightarrow \mathbb{R}^n$ is a continuously differentiable function. In the paper, we assume that the solution set of (1.1) is nonempty and denote it by ${X}^*$. Moreover, we denote the Jacobian $F'(x)$ as ${J}(x)$ and use the notations $F_k = F(x_k), J_k = J(x_k)$ for simplification.

The Levenberg-Marquardt (LM) method is one of the most important algorithms for solving (1.1). At every iteration, the LM method computes the trial step ${d}_k$ by solving the following linear system

where $\mu_k$ is the LM parameter which plays an important role in analyzing the convergence rate of the LM method. For example, Yamashita and Fukushima ^[13] proved that the LM method taking $\mu_k = \|F_k\|^2$ has quadratic convergence under the local error bound condition which is weaker than the nonsingularity. Fan and Yuan ^[6] proved that the LM method taking $\mu_k = \|F_k\|^\delta$ with $\delta\in[1, 2]$ still achieves the quadratic convergence under the local error bound condition. More researches on the LM method can be found in ^{[1,11,14,15,16]} and references therein.

The LM method solves the linear system (1.2) exactly at every iteration which may be very expensive when solving a large-scale nonlinear equation. The inexact approach is one way to overcome this difficulty. In the inexact LM method, the direction ${d}_k$ is given by the solution of the system

where $p_k\in \mathbb{R}^n$ is a perturbation vector which measures how inexactly the linear system (1.2) is solved. Under the nonsingularity, Facchinei and Kanzow ^[3] proved that if $\mu_k\rightarrow0$ and $\|p_k\|\le o(\|J_k^TF_k\|)$, then the inexact LM method has superlinear convergence rate and if $\mu_k = O(\|J_k^TF_k\|)$ and $\|p_k\| = O(\|J_k^TF_k\|^2)$, then its convergence rate is quadratic. Suppose

where $\alpha > 0$ and $\theta > 0$ are constants. Under the local error bound condition, many researchers (e.g., ^[2,4,5,7]) investigated the convergence rate of the inexact LM method for different values of $\alpha$ and $\theta$ respectively. Lately, Wang and Fan ^[12] studied the convergence rate of the inexact LM method taking $\mu_k = \|F_k\|^\alpha$ with $\|p_k\| = \|F_k\|^{\alpha+\theta}$ and $\mu_k = \|J_k^TF_k\|^\alpha$ with $\|p_k\| = \|J_k^TF_k\|^{\alpha+\theta}$ respectively under the H$\mathrm{\ddot{o}}$derian local error bound condition and the H$\mathrm{\ddot{o}}$derian continuity of the Jacobian, which are more general than the local error bound condition and the Lipschitz continuity of the Jacobian used in ^[1,2,4,5,7].

In this paper, we study the convergence rate of a family of inexact LM methods with more general LM parameters and perturbation vectors. We consider

where $\sigma, \tau\in[0, 1]$ and $\alpha, \theta > 0$. We derive an explicit formula of the convergence order under the H$\mathrm{\ddot{o}}$derian local error bound condition and the H$\mathrm{\ddot{o}}$derian continuity of the Jacobian. Moreover, we develop a family of inexact LM methods with a nonmonotone line search and prove its global convergence. We also investigate the numerical performances of these inexact LM methods by solving the nonlinear equations arising in the linear complementarity problem.

The organization of this paper is as follows. In the next section, we investigate the convergence order under the H$\mathrm{\ddot{o}}$derian local error bound condition and the H$\mathrm{\ddot{o}}$derian continuity of the Jacobian. In Section 3, we present a family of inexact LM methods with a nonmonotone line search and prove that it is globally convergent. In Section 4, we apply these inexact LM methods to solve the nonlinear equations arising from the linear complementarity problem and report some numerical results.

2.   Convergence rate of the inexact LM methods

In this section, we study the convergence rate of the inexact LM methods with the iteration

where $d_{k}$ is obtained by (1.3) with $\mu_k, p_k$ satisfying (1.4) and (1.5). We suppose that the generated sequence $\{x_k\}$ converges to the solution set $X^*$ and lies in some neighbourhoods of $x^*\in X^*.$

Assumption 2.1. $\textrm{(a)}$ $F(x)$ provides a H$\mathrm{\ddot{o}}$derian local error bound of order $\gamma\in(0, 1]$ in some neighbourhoods of $x^{*}\in X^{*}$, i.e., there exist constants $\kappa > 0$ and $0 < r < 1$ such that

$\textrm{(b)}$ $J(x)$ is H$\mathrm{\ddot{o}}$derian continuous of order $\upsilon\in(0, 1]$, i.e., there exists a constant $L > 0$ such that

It is worth pointing out that if $\gamma = \upsilon = 1$, then Assumption 2.1 (a) is the local error bound condition and Assumption 2.1 (b) is the Lipschitz continuity of the Jacobian. Moreover, by (2.3), we have (see ^[12])

Furthermore, there exists a constant $M > 0$ such that

In the following, we denote by $\overline{x}_{k}$ the vector in $X^{*}$ that is closest to $x_{k}$, i.e.,

Now we suppose the singular value decomposition (SVD) of $J(\bar{x}_k)$ is

where $\bar{\Sigma}_{k, 1} = \mathrm{diag}(\bar{\sigma}_{k, 1}, ..., \bar{\sigma}_{k, r})$ with $\bar{\sigma}_{k, 1}\ge\cdots\ge\bar{\sigma}_{k, r} > 0$. The corresponding SVD of $J_k$ is

where ${\Sigma}_{k, 1} = \mathrm{diag}({\sigma}_{k, 1}, ..., {\sigma}_{k, r})$ with ${\sigma}_{k, 1}\ge\cdots\ge{\sigma}_{k, r} > 0$ and ${\Sigma}_{k, 2} = \mathrm{diag}({\sigma}_{k, r+1}, ..., {\sigma}_{k, n})$ with ${\sigma}_{k, r+1}\ge\cdots\ge{\sigma}_{k, n}\ge0$. For simplicity, we neglect the subscript $k$ in $U_{k, i}, \Sigma_{k, i}, V_{k, i} (i = 1, 2)$ and write $J(\bar{x}_k)$ and $J_k$ as

By the matrix perturbation theory ^[8] and (2.3), we have

which gives

Moreover, by (1.3) we have

and

In the following, we suppose without loss of generality that $x_k$ lies in $N(x^{*}, \frac{r}{2})$.

Lemma 2.1. Under the conditions of Assumption 2.1, if $\upsilon > \frac{2}{\gamma}-2$, then there exist positive constants $a_1, a_2, b_1, b_2$ such that

Proof. Since $\|\overline{x}_{k}-x^{*}\|\leq \|\overline{x}_{k}-x_{k}\|+\|x_{k}-x^{*}\|\leq2\|x_{k}-x^{*}\|\leq{r},$ we have $\overline{x}_{k}\in N(x^{*}, r)$. Hence, by (2.2) and (2.5),

By (2.5), we have

Let $T_k: = F_{k}-F(\overline{x}_{k})-J_{k}(x_{k}-\overline{x}_{k})$. Then,

It follows from (2.4), (2.12) and (2.14) that

which together with $\upsilon > \frac{2}{\gamma}-2$ gives

where $\tilde{c} > 0$ is some constant. By (2.13) and (2.15), we have

Since $\mu_{k} = \sigma\|F_{k}\|^{\alpha}+(1-\sigma)\|J_{k}^{ {T}}F_{k}\|^{\alpha}$, by (2.12) and (2.16), we have

where $a_1: = \sigma \kappa^{\frac{\alpha}{\gamma}}+(1-\sigma)\tilde{c}^{\alpha}$ and $a_2: = \sigma M^{\alpha} +(1-\sigma) M^{2 \alpha}$, which together with ${\frac{2}{\gamma}-1}\ge\frac{1}{\gamma}$ gives

This proves (2.10). Moreover, since $\|p_{k}\| = \tau\|F_{k}\|^{\alpha+\theta}+(1-\tau)\|J_{k}^{ {T}}F_{k}\|^{\alpha+\theta}$, according to (2.12) and (2.16), we have

where $b_1: = \tau \kappa^{\frac{\alpha+\theta}{\gamma}}+(1-\tau) \tilde{c}^{\alpha+\theta}$ and $b_2: = \tau M^{\alpha+\theta} +(1-\tau) M^{2(\alpha+\theta)},$ which together with ${\frac{2}{\gamma}-1}\ge\frac{1}{\gamma}$ gives

This proves (2.11). □ □

Lemma 2.2. Under the conditions of Assumption 2.1, if $\upsilon > \frac{2}{\gamma}-2$, $0 < \alpha < \frac{2\gamma(1+\upsilon)}{2-\gamma}$ and $\theta > \frac{(2-2\gamma)\alpha}{\gamma}$, there exists a constant $c > 0$ such that

Proof. Let

Then ${\bar{d}}_k$ is the LM step computed by solving (1.2). Moreover, by (1.3) we have

Now we define

Then, the LM step $\overline{d}_{k}$ defined by (2.18) is the minimizer of $\varphi_{k}(d)$. By (2.4) and the left inequality in (2.10), we have

where $c_1: = (({L}/(1+\upsilon))^2 a_1^{-1}+1)$. Thus, by (2.19), (2.21) and the left inequality in (2.10) and the right inequality in (2.11), we have

where $c = \sqrt{c_1}+{b_2}/{a_1}$.□ □

Lemma 2.3. [12, Lemma 2.3] Under the conditions of Assumption 2.1, we have

$\textrm{(i)}\|U_{1}U_{1}^{ {T}}F_{k}\|\leq M\|\overline{x}_{k}-x_{k}\|;$ $\textrm{(ii)}\|U_{2}U_{2}^{ {T}}F_{k}\|\leq 2L\|\overline{x}_{k}-x_{k}\|^{1+\upsilon}$.

Theorem 2.1. Under the conditions of Assumption 2.1, if $\upsilon > \frac{2}{\gamma}-2$, $0 < \alpha < \frac{2\gamma(1+\upsilon)}{2-\gamma}$ and $\theta > \frac{(2-2\gamma)\alpha}{\gamma}$, then the sequence $\{x_{k}\}$ converges to the solution set $X^*$ with the order ${{h}(\alpha, \theta, \gamma, \upsilon)}$ where

Proof. Since ${x_{k}}$ converges to $X^{*}$, we assume that $L\|\overline{x}_{k}-x_{k}\|^v\leq\frac{\bar{\sigma}}{2}$ holds for all sufficiently large $k$. Then, it follows from (2.7) that

On the other hand, by (2.7) and the left inequality in (2.10), for all sufficiently large $k$,

Hence, it follows from (2.9)–(2.11), (2.24), (2.25), $\|(\Sigma_{2}^{2}+\mu_{k}I)^{-1}\|\leq\mu_{k}^{-1}$ and Lemma 2.3 that

where $\bar{c} = {4 Ma_2}/ {\bar{\sigma}^{2}}+2 L+\frac{2}{\bar{\sigma}}b_2 +La_1^{-1}b_2$. Therefore, by (2.2), (2.4), (2.26) and Lemma 2.2, we have

where ${h}(\alpha, \theta, \gamma, \upsilon)$ is given in (2.23). □ □

Corollary 2.1. Under the conditions of Assumption 2.1 and $\gamma = \upsilon = 1$, if $0 < \alpha < 4,$ then the sequence $\{x_{k}\}$ converges to the solution set $X^*$ with the order ${{h}(\alpha, \theta)}$ where

More precisely,

and

As we know from ^[5] that for any $\alpha\in(0, 2]$ and $\theta\ge 1$, the sequence generated by the inexact LM method (1.3) converges to some solution of (1.1), which is a stronger result than the convergence to the solution set. We show that this convergence result also holds true for the inexact LM methods studied in this paper.

Theorem 2.2. Under the conditions of Assumption 2.1 and $\gamma = \upsilon = 1$, if $\alpha\in(0, 2]$ and $\theta\ge 1$, then the sequence $\{x_{k}\}$ converges to a solution of (1.1) with the order $g(\alpha)$ where

Proof. By Corollary 2.1, when $\alpha\in(0, 2]$ and $\theta\ge 1$, it holds that

where $g(\alpha)$ is defined by (2.27). Then, for all sufficiently large $k$,

which together with ${g}(\alpha) > 1$ gives

Hence, we deduce from (2.17), (2.28) and (2.29) that

This implies that the sequence $\{x_k\}$ converges to some solution of (1.1) with the order $g(\alpha)$. □ □

3.   Globally convergent inexact LM methods

In this section, we study a family of globally convergent inexact LM methods. We define the merit function $\psi: \mathbb{R}^n\rightarrow \mathbb{R}$ as

Obviously, $\psi(x)$ is continuously differentiable at any $x\in \mathbb{R}^n$ with $\nabla\psi(x) = {J}(x)^T{F}(x).$ Our method is described as follows.

Algorithm 3.1. Choose parameters $\sigma, \tau \in[0, 1]$, $\alpha\in(0, 4]$, $\theta > 0$, $\rho, \xi, \chi, \delta, \zeta \in(0, 1)$ and $x_0\in \mathbb{R}^n$. Let $\Theta_{0}: = \psi(x_{0})$. Set $k: = 0.$

Step 1: If $\|\nabla \psi(x_k)\| = 0$, then stop.

Step 2: Set

Find a search direction $d_k\in {\mathbb{R}}^n$ which satisfies

where

If $d_k$ satisfies

then set $\lambda_k: = 1$ and go to Step 4.

Step 3: If the descent condition

is not satisfied, then set $d_k: = -\nabla\psi(x_k)$. Let $l_k$ be the smallest nonnegative integer $l$ satisfying

Set $\lambda_k : = \delta^{l_k}$ and go to Step 4.

Step 4: Set $x_{k+1}: = x_k+\lambda_k d_k$ and

Set $k: = k+1$ and go to Step 1.

Algorithm 3.1 is designed based on the inexact LM method ^[2] and the nonmonotone smoothing Newton method ^[10]. The main feature of Algorithm 3.1 is that it takes more general LM parameter $\mu_k$ and perturbation vector $p_k$ and adopts a nonmonotone line search technique to ensure the global convergence.

Theorem 3.1. Algorithm 3.1 generates an infinite sequence $\{x_k\}$ which satisfies $\psi(x_k)\leq \Theta_k$ for all $k\geq0$.

Proof. For some $k$, we assume that $\psi(x_k)\leq \Theta_k$. If $\nabla \psi(x_k)\neq0$, then ${F}(x_k)\neq0$ and hence $\mu_k > 0$. So, the matrix $J_{k}^TJ_{k}+\mu_kI$ is positive definite and the search direction $d_k$ in Step 2 is always obtained. Notice that the obtained $d_k\neq0$. In fact, if $d_k = 0$, then by (3.4) we have $\|p_k-\nabla \psi(x_k)\| = 0$. Since $\|p_k\|\leq \rho\|\nabla \psi(x_k)\|$, it follows that $\|\nabla \psi(x_k)\| = \|p_k\| = 0$ which contradicts $\nabla \psi(x_k)\neq0$. So, in Step 3, if the descent condition (3.7) holds, then $\nabla\psi(x_k)^Td_k\leq-\chi\|d_k\|^2 < 0$. Otherwise, $d_k = -\nabla\psi(x_k)$ which gives $\nabla\psi(x_k)^Td_k = -\|\nabla\psi(x_k)\|^2 < 0$. Thus, the direction $d_k$ used in the line search (3.8) is always a descent direction of $\psi$. Next we show that there exists at least a nonnegative integer $l$ satisfying (3.8). On the contrary, we suppose that for all nonnegative integer $l$,

which together with $\psi(x_k)\leq \Theta_k$ gives

By letting $l\rightarrow \infty$ in (3.10), we have $\nabla\psi(x_k)^Td_k\geq0$ which contradicts $\nabla\psi(x_k)^Td_k < 0$. So, we can obtain $x_{k+1}$ in Step 4. Now we show $\psi(x_{k+1})\leq \Theta_{k+1}$. In fact, if the condition (3.6) holds, then

Otherwise, by Step 3, we also have $\psi(x_{k+1})\leq \Theta_k$. Hence, from (3.9) it holds that

Therefore, we can conclude that if $\psi(x_k)\leq \Theta_k$ and $\nabla \psi(x_k)\neq0$ for some $k$, then $x_{k+1}$ can be generated by Algorithm 2.1 with $\psi(x_{k+1})\leq \Theta_{k+1}$. Since $\psi(x_{0}) = \Theta_{0}$, by induction on $k,$ we prove the theorem. □

Theorem 3.2. Every accumulation point $x^*$ of a sequence $\{x_k\}$ generated by Algorithm 3.1 is a stationary point of $\psi(x)$, i.e., $\nabla \psi(x^*) = 0.$

Proof. By Steps 2 and 3, we have $\psi(x_{k+1})\leq \Theta_k$ for all $k\geq0$. This and (3.9) yield that

Thus there exists $\Theta^*\geq0$ such that $\lim \limits_{k\rightarrow \infty} {\Theta_k} = \Theta^*$. Further, by (3.9) we have

and so

So, if there are infinitely many $k$ for which $\| {F}(x_k+d_k)\|\leq\xi\|{F}(x_k)\|$ holds, then $\sqrt{2\Theta^*}\le\xi\sqrt{2\Theta^*}$ which together with $\xi\in(0, 1)$ yields $\Theta^* = 0$, i.e., $\lim\limits_{k\rightarrow \infty}{F}(x_{k}) = 0.$ By the continuity, we have the desired result. Next, we assume that there exists an index $\bar{k}$ such that $\| {F}(x_k+d_k)\| > \xi\| {F}(x_k)\|$ for all $k\geq \bar{k}$, i.e., $\lambda_k$ is determined by (3.8) for all $k\geq \bar{k}$. Since $x^*$ is the accumulation point of $\{x_k\}$, there exists a subsequence $\{x_k\}_{k\in K}$ where $K\subset\{0, 1, ...\}$ such that $\lim\limits_{(K\ni)k\rightarrow \infty}x_k = x^*.$ We assume that $\nabla \psi(x^*)\neq0$ and will derive a contradiction. Since $\nabla \psi(x^*) = J(x^*)^TF(x^*)\neq0$, we have $\|J(x^*)\| > 0$ and $\|{F}(x^{*})\| > 0$. Moreover, by the continuity, we have

Obviously, $\mu^* > 0$. So, there exists a positive constant $\bar{\mu}$ such that $\mu_k\geq\bar{\mu} > 0$ for all $k\in K$. Since $\{\nabla \psi(x_k)\}$ is bounded on any convergent subsequence $\{x_k\}_{k\in K}$, for any $k\in K$, either

or $\|d_k\| = \|-\nabla\psi(x_k)\| < \infty$. Hence, the sequence $\{\|d_k\|\}_{k\in K}$ is bounded. By passing to the subsequence, we suppose $\lim\limits_{(K_1\ni)k\rightarrow \infty} d_k = d^*$ where $K_1\subset K$ is an infinite subset. In the following, we prove $\nabla\psi(x^*)^Td^* = 0.$ By (3.8) we have

This and $\lim \limits_{k\rightarrow \infty} {\psi}(x_{k}) = \lim \limits_{k\rightarrow \infty} {\Theta_k} = \Theta^*$ yield $\lim \limits_{k\rightarrow \infty} \lambda_k\|d_k\| = 0.$ Hence, if $\lambda_k\ge\bar{\lambda} > 0$ for any $k\in K_1$ where $\bar{\lambda} > 0$ is a constant, then $\lim\limits_{(K_1\ni)k\rightarrow \infty} d_k = d^* = 0$ and hence $\nabla\psi(x^*)^Td^* = 0.$ Otherwise, $\{\lambda_k\}_{k\in K_1}$ has a subsequence converging to zero and we suppose $\lim\limits_{(K_2\ni)k\rightarrow \infty}\lambda_k = 0$ where $K_2\subset K_1$ is an infinite set. From (3.8), for all $k\geq \bar{k}$ and $k\in {K}_2$,

which gives

Since $\psi$ is continuously differentiable at $x^*$, by letting $k\rightarrow \infty$ with $k\in K_2$ in (3.12), we have $\nabla\psi(x^*)^Td^*\geq0.$ On the other hand, since $d_k$ is a sufficient descent direction of $\psi$, we have $\nabla\psi(x^*)^Td^* = \lim\limits_{(K_2\ni)k\rightarrow \infty} \nabla\psi(x_k)^Td^k\leq0.$ These give $\nabla\psi(x^*)^Td^* = 0.$ Hence, we can conclude that $\nabla\psi(x^*)^Td^* = 0.$ Let $\bar{K}: = \{k\in K_1 |d_k = -\nabla\psi(x_k)\}.$ If $\bar{K}$ is an infinite set, then

which contradicts the assumption $\nabla \psi(x^*)\neq0.$ Otherwise, $\bar{K}$ is a finite set and $d_k$ satisfies (3.7) for all sufficiently large $k\in K_1.$ Then, by (3.7) we have

which gives $d^* = 0.$ By (3.4), we have for all $k\in K_1$,

Since $\lim\limits_{(K_1\ni)k\rightarrow \infty}(J_k^TJ_k+\mu_kI) = {J}(x^*)^T {J}(x^*)+\mu^*I,$ by (3.13) and $d^* = 0$, we have

Since $\|p_k\|\leq \rho\|\nabla\psi(x_k)\|$, we can deduce from (3.14) that

which also contradicts the assumption $\nabla \psi(x^*)\neq0.$ We complete the proof. □

Next, we analyze the convergence rete of Algorithm 3.1. Suppose that the generated iteration sequence $\{x_k\}$ has an accumulation point $x^*$ such that $F(x^*) = 0$ and Assumption 2.1 holds at $x^*$ for $\gamma = \upsilon = 1$. We will show that the whole sequence $\{x_k\}$ converges to $x^*$ at leat superlinearly for any $\alpha\in(0, 2]$ and $\theta > 1$.

Lemma 3.1. Assume that Assumption 2.1 holds for $\gamma = \upsilon = 1$. Let $\alpha\in(0, 2]$ and $\theta > 1$. If $x_{k}, x_{k}+d_k\in N(x^{*}, r/2)$, then there exists $\hat{c} > 0$ such that

Proof. Since $\overline{d}_{k}$ defined by (2.18) is the minimizer of $\varphi_{k}(d)$ in (2.20), by (2.4) and (2.10),

It holds from (2.20) and (3.16) that

Since $d_{k} = \bar{d}_{k}+(J_{k}^{T}J_{k}+\mu_{k}I)^{-1}p_k,$ we have from (2.5), (2.10), (2.11) and (3.17) that

where $\tilde{C} = \sqrt{L^2/4+a_{2}}+{Mb_{2}}a_1^{-1}.$ Moreover, by (2.17), $\alpha\in(0, 2]$ and $\theta > 1$, we have

Thus, by (2.4), (2.17), (3.18) and (3.19), we have

which together with (2.2) gives

Letting $\hat{c}: = ({\tilde{C}+Lc^2/2}){\kappa}^{-1}$, we complete the proof. □ □

Lemma 3.2. Under the same conditions in Lemma 3.1, there exists an index $\bar{k}$ such that for all $k\geq\bar{k}$ it holds: $\textrm{(i)}$ $x_k, x_k+d_k\in N(x^*, r/2);$ $\textrm{(ii)}$ $\|{F}(x_k+d_{{k}})\|\leq\xi\|{F}(x_k)\|.$

Proof. By Lemma 3.1, similarly as the proof of [9, Lemma 11], we can prove the result. □□

Theorem 3.3. Under the same conditions in Lemma 3.1, the whole sequence $\{x_k\}$ converges to $x^*$ with

Proof. By Lemma 3.2 and Step 2 of Algorithm 3.1, we have $x_{k+1} = x_k+d_k$ and $\|F(x_{k+1})\|\leq\xi\|F(x_k)\|$ for all $k\geq\bar{k}$. It follows that $\lim\limits_{k\to \infty}\|F(x_k)\| = 0,$ which together with (2.2) yields $\lim\limits_{k\to \infty}\mathrm{dist}(x_k, X^*) = 0.$ Thus, from Lemma 3.1, for all sufficiently large $k$,

Since $\min\{\frac{\alpha}{2}+1, \theta\} > 1$ and $\lim\limits_{k\to \infty}\mathrm{dist}(x_k, X^*) = 0$, we have $\hat{c}\mathrm{dist}(x_{k}, X^{*})^{\min\{\frac{\alpha}{2}+1, \theta\}-1} < \frac{1}{2}$ for all sufficiently large $k$. It follows that for all sufficiently large $k$,

This implies that for all sufficiently large $k$,

that is

By (3.19) and Lemma 3.1, for all sufficiently large $k$,

which together with $\lim\limits_{k\to \infty}\mathrm{dist}(x_k, X^*) = 0$ gives $\lim\limits_{k\to \infty}d_k = 0$ and

By (3.20) and (3.22), for all sufficiently large $k$,

So, when $k$ is sufficiently large, (3.23) gives

This and $\lim\limits_{k\to \infty}d_k = 0$ yield $\lim\limits_{k \to \infty }x_{k} = x^*$. Further, by (3.21) and (3.24) we have

The proof is completed. □ □

4.   Numerical results

We apply Algorithm 3.1 to solve the nonlinear equations arising in the well-known linear complementarity problem (LCP):

where $M\in {\mathbb{R}}^{n\times n}$ and $q\in {\mathbb{R}}^n$ are given matrix and vector. To reformulate the LCP into an equivalent system of equations, we define the function $\phi: {\mathbb{R}}^2\rightarrow {\mathbb{R}}$ as

where $\mathrm{sgn}(t): = \begin{cases} 1 & {\mbox{if}\; t>0 }\\ 0 & {\mbox{if}\; t = 0. }\\ -1 & {\mbox{if}\; t<0 } \end{cases}$

Proposition 4.1. $\textrm{(i)}$ $\mathrm{\phi}(a, b) = 0\Longleftrightarrow a\geq0, \; b\geq0, \; ab = 0.$

$\textrm{(ii)}$ $\mathrm{\phi}$ is continuously differentiable at any $(a, b)\in{\mathbb{R}}^2$ whose gradient is given by

Proof. Let $f(t): = \mathrm{sgn}(t)t^2.$ Since $f_q$ is a bijective function, it follows that

The result (ⅱ) holds because $f(t)$ is continuously differentiable everywhere with $f'(t) = 2|t|.$ □

Let $x: = (u, v)$. By using the function $\phi$, we may have that solving the LCP is equivalent to computing a solution of the smooth nonlinear equations

In the following, we apply Algorithm 3.1 to solve the nonlinear equations (4.3). The parameters are chosen as $\rho = 10^{-3}, \xi = 0.5, \gamma = 10^{-5}, \zeta = 10^{-5}, \delta = 0.8, \theta = 1, \tau = 0.5$ and $\sigma, \alpha$ are given the specific experiments. In Step 2, GMRES is used as the linear solver to find the inexact direction $d_k.$ Moreover, we use $\|F(x_k)\|\leq10^{-5}$ as the stopping criterion.

We test two classes of LCPs defined as follows:

LCP (ⅰ) Let $M$ be the block diagonal matrix with $\frac{N_1^TN_1}{\|N_1^TN_1\|}, ..., \frac{N_4^TN_4}{\|N_4^TN_4\|}$ as block diagonals, i.e., $M = {{\textbf{diag}}}\big(\frac{N_i^TN_i}{\|N_i^TN_i\|}\big)$ with $N_i = {\bf rand}(\frac{n}{4}, \frac{n}{4})$ for $i = 1, ..., 4$. Take $q = {\bf rand}(n, 1)$. Obviously, the matrix $M$ is positive semidefinite.

LCP (ⅱ) Let $M = {{\textbf{diag}}}\big(\frac{N_i}{\|N_i\|}-{\bf eye}(n/4)\big)$ with $N_i = {\bf rand}(\frac{n}{4}, \frac{n}{4})$ for $i = 1, ..., 4$. Take $q = {\bf rand}(n, 1)$.

We use $v_0 = (1, 0, ..., 0)^T$ and $u_0 = Mv_0+q$ as the initial point. Tables 1 and 2 show numerical experimental results of Algorithm 3.1 with different values of $\sigma$ and $\alpha$, in which IT denotes the iteration number, CPU denotes the CPU time in seconds, Fx denotes the value of $\|F(x_k)\|$ at the final iteration point and "–" stands for that the algorithm fails to find the solution. These numerical results show that Algorithm 3.1 is efficient for solving LCPs. It can find a solution point meeting the desired accuracy in very few iteration numbers and in short CPU time. Moreover, from our numerical implementations, we may find that Algorithm 3.1 with $\sigma = 1$, i.e., $\mu_{k} = \|F_{k}\|^{\alpha}$, has advantage over it with $\sigma = 0$, i.e., $\mu_{k} = \|J_{k}^{ {T}}F_{k}\|^{\alpha}$. At last, we point out that we have tested Algorithm 3.1 with different values of $\tau$ and found that the numerical performances are same. □

5.   Conclusions

We have presented a family of inexact Levenberg-Marquardt methods for the nonlinear equations. The presented LM method takes more general LM parameters and perturbation vectors which are convex combinations of $\|F_k\|^\alpha$ and $\|J_k^TF_k\|^\alpha$ and $\|F_k\|^{\alpha+\theta}$ and $\|J_k^TF_k\|^{\alpha+\theta}$. Under the H$\mathrm{\ddot{o}}$derian local error bound condition and the H$\mathrm{\ddot{o}}$derian continuity of the Jacobian, we have derived an explicit formula of the convergence order of these inexact LM methods. Moreover, we have developed a family of globally convergent inexact LM methods and showed its effectiveness by some numerical experiments.

Use of AI tools declaration

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

Acknowledgments

Research of this paper was supported by Natural Science Foundation of Henan Province (222300420520) and Key scientific research projects of Higher Education of Henan Province (22A110020).

Conflict of interest

All authors declare no conflicts of interest in this paper.