A nonmonotone inexact Broyden-like algorithm for nonlinear complementarity problems

Abstract

In this paper, by constructing a new smoothing complementary function, we reformulate the nonlinear complementarity problem as a nonlinear smooth system of equations. Combining non-monotonic line search techniques with an inexact Broyden-like algorithm, we establish a nonmonotone inexact Broyden-like algorithm. The global and local quadratic convergence of this method is proved under suitable conditions. Numerical experiments show that the algorithm is effective for solving nonlinear complementarity problems.

Keywords

Complementarity problem / global convergence / local quadratic convergence / Broyden-like algorithm

1 Preliminaries

Consider the nonlinear complementarity problem [3] \left(NCP\left(F\right)\right): Given a nonlinear vector function F\left(x\right):{\mathbb{R}}^n\to {\mathbb{R}}^n, find a vector x\in {\mathbb{R}}^n such that

(1.1)x\ge 0,F\left(x\right)\ge 0,x^{T}F\left(x\right)=0

holds.

It is well known that NCP(F) is often solved by being transformed into an equivalent system of equations, namely

(1.2)\mathrm{\Phi }\left(x\right)=0,

where \mathrm{\Phi }:{\mathbb{R}}^n\to {\mathbb{R}}^n is a semismooth function. In this paper, the Fischer-Burmeister (FB) function [7] is used to complete it, namely

{\varphi }_{\mathrm{F}\mathrm{B}}(a,b)=a+b-\sqrt{a^2+b^2}.

Thus,

(1.3)\mathrm{\Phi }\left(x\right)=\left[\begin{array}{c}{\varphi }_{FB}\left(x_1,F_1\left(x\right)\right)\\ ⋮\\ {\varphi }_{FB}\left(x_n,F_n\left(x\right)\right)\end{array}\right].

It is verified that {\varphi }_{FB}(a,b)=0 is equivalent to a\ge 0, b\ge 0, and ab=0. However, the FB function is non-differentiable at \left(0,0\right). To obtain a new smooth FB function, a smoothing parameter \mu >0 is introduced:

(1.4)\varphi (\mu ,a,b)=(e^{\mu }+\mu )(a+b)-\sqrt{{\mu }^2+(a+\mu b{)}^2+(b+\mu a{)}^2}.

Then \varphi (0,a,b)={\varphi }_{\mathrm{F}\mathrm{B}}(a,b).

Let z:=(\mu ,x)\in {\mathbb{R}}_{++}\times {\mathbb{R}}^2,

(1.5)H\left(z\right)=H\left(\mu ,x\right)=\left[\begin{array}{c}\mu \\ \Psi \left(z\right)\end{array}\right],

where

\mathrm{\Psi }\left(z\right):=\mathrm{\Psi }\left(\mu ,x\right)=\left[\begin{array}{c}\varphi \left(\mu ,x_1,F_1\left(x\right)\right)\\ ⋮\\ \varphi \left(\mu ,x_n,F_n\left(x\right)\right)\end{array}\right].

Thus, solving Problem (1.1) is equivalent to solving the following nonlinear system of equations:

(1.6)H\left(z\right)=0.

For any z=(\mu ,x)\in {\mathbb{R}}_{++}\times {\mathbb{R}}^n, simple calculations yield:

(1.7)H^{\prime }\left(z\right)=\left[\begin{array}{cc}1& 0\\ V\left(z\right)& D_1\left(z\right)+D_2\left(z\right)F^{\prime }\left(x\right)\end{array}\right].

Here,

V\left(z\right):=\mathrm{v}\mathrm{e}\mathrm{c}\left\{{\varphi }^{\prime }\left(\mu ,x_i,F_i\left(x\right)\right):i\in \mathbb{N}\right\},

D_1\left(z\right):=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\left\{a_1\right(z),a_2(z),\dots ,a_n(z\left)\right\},

D_2\left(z\right):=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}\left\{b_1\left(z\right),b_2\left(z\right),\dots ,b_n\left(z\right)\right\},

(1.8){\varphi }^{\prime }\left(\mu ,x_i,F_i\left(x\right)\right)={\mathrm{e}}^{\mu }\left(x_i+F_i\left(x\right)\right)-\frac{\mu +2x_i{F}_i\left(x\right)+\mu \left(x_i^2+F_i^2\left(x\right)\right)}{\sqrt{{\mu }^2+(x_i+\mu F_i(x){)}^2+(\mu x_i+F_i\left(x\right){)}^2}},

(1.9)a_i\left(z\right)=\left({\mathrm{e}}^{\mu }+\mu \right)-\frac{\left(1+{\mu }^2\right)x_i+2\mu F_i\left(x\right)}{\sqrt{{\mu }^2+(x_i+\mu F_i(x){)}^2+(\mu x_i+F_i\left(x\right){)}^2}},

(1.10)b_i\left(z\right)=({\mathrm{e}}^{\mu }+\mu )-\frac{2\mu x_i+(1+{\mu }^2)F_i\left(x\right)}{\sqrt{{\mu }^2+(x_i+\mu F_i(x){)}^2+(\mu x_i+F_i\left(x\right){)}^2}}.

Therefore, for any i=1,2,\dots ,n, there is

(1.11)

Lemma 1.1　 Let the functions H and \Psi be defined by Equation (1.5). Then,

(i) for any z=(\mu ,x)\in {\mathbb{R}}_{++}\times {\mathbb{R}}^n, the function \Psi is continuously differentiable;

(ii) for any z=(\mu ,x)\in {\mathbb{R}}_{++}\times {\mathbb{R}}^n, if the function F is a P_0-function, then H^{\prime }\left(z\right), as defined by Equation (1.7), is nonsingular.

The idea of the quasi-Newton method is to replace H^{\prime }(z^k) in the Newton equation with an approximation matrix B_k of H^{\prime }(z^k). Recently, Zheng et al. [10] proposed a nonmonotone Broyden-like algorithm for solving complementarity problems. Under appropriate assumptions, this algorithm not only achieves global convergence but also has local superlinear and quadratic convergence rates. However, in each iteration of this algorithm, it is required to precisely solve a linear system of equations. When there are many variables in the system of equations, the computational cost of accurately solving the system of equations is high. Inspired by references [6, 9, 10], we adopt the nonmonotone line search criterion from reference [9] to establish a nonmonotone and inexact Broyden-like algorithm for solving complementarity problems.

2 Algorithm

This section presents a nonmonotone and inexact Broyden-like algorithm for solving the nonlinear complementarity problem. Define the merit function as:

(2.1)f\left(z\right)=\Vert H\left(z\right)\Vert .

The specific steps of this new algorithm are as follows.

Algorithm 2.1　(Nonmonotone Inexact Broyden-like Algorithm)

Step 0: Choose constants \delta ,\alpha ,\sigma ,{\sigma }_1, \overline{\theta }\in \left(0,1\right), {\mu }_0>0, \kappa \in \left(0,1\right), {\sigma }_2\in (0,\frac{1-\kappa }{2}),{\rho }_{\mathrm{m}\mathrm{i}\mathrm{n}}\in \left[0,1\right),{\rho }_{\mathrm{m}\mathrm{a}\mathrm{x}}\in \left(0,1\right], and a random vector z^0=({\mu }_0,x^0)\in {\mathbb{R}}_{++}\times {\mathbb{R}}^n. Define a positive sequence , and let \eta >0 be a given constant, there is

(2.2)

Arbitrarily select a nonsingular matrix B_0\in {\mathbb{R}}^{n+1}\times {\mathbb{R}}^{n+1}. Let k:=0.

Step 1: If f(z^k)=0, terminate the algorithm. Otherwise, solve the following system of equations:

(2.3)H(z^k)+B_k\mathrm{\Delta }{z}^k=\left[\begin{array}{c}0\\ r_k\end{array}\right].

We obtain \mathrm{\Delta }{z}^k=(\mathrm{\Delta }{\mu }_k,\mathrm{\Delta }{x}^k), where \Vert r_k\Vert \le {\eta }_{k}f(z^k), and B_k\in {\mathbb{R}}^{n+1}\times {\mathbb{R}}^{n+1} is an approximation of the matrix H^{\prime }(z^k), which is defined by Equation (1.7).

Step 2: If the following inequality holds:

(2.4)f(z^k+\mathrm{\Delta }{z}^k)\le \alpha f(z^k)-\sigma {\Vert \mathrm{\Delta }{z}^k\Vert }^2,

set {\lambda }_k=1 and proceed to Step 4.

Step 3: Set {\lambda }_k:={\delta }^{m_k}, where m_k is the smallest nonnegative integer m ∈ \{0,1,2,\dots \} such that the following inequality is satisfied

(2.5)f(z^k+{\delta }^m\mathrm{\Delta }{z}^k)\le C_k-{\sigma }_1{\Vert {\delta }^m\mathrm{\Delta }{z}^k\Vert }^2-{\sigma }_2{\delta }^{m}f(z^k),

where

(2.6)C_k=\{\begin{array}{c}f(z^k),k=0,\\ {\rho }_k{C}_{k-1}+\left(1-{\rho }_k\right)f(z^k),k\ge 1,\end{array}

and {\rho }_k\in [{\rho }_{\mathrm{m}\mathrm{i}\mathrm{n}},{\rho }_{\mathrm{m}\mathrm{a}\mathrm{x}}].

Step 4: Set z^{k+1}:=z^k+{\lambda }_k\mathrm{\Delta }{z}^k.

Step 5: Update B_k to obtain B_{k+1}:

(2.7)B_{k+1}=B_k+{\theta }_k\frac{\left(y_k-B_k{s}^k\right){\left(s^k\right)}^{\mathrm{T}}}{\Vert s^k{\Vert }^2},

where s^k={\lambda }_k\mathrm{\Delta }{z}^k=z^{k+1}-z^k,y_k=H\left(z^{k+1}\right)-H(z^k), and the parameter {\theta }_k is chosen to satisfy |{\theta }_k-1|\le \overline{\theta } such that B_{k+1} remains nonsingular.

Step 6: Set k:=k+1 and return to Step 1.

Note　In Step 1, if r_k=0 for all k, Algorithm 2.1 reduces to the nonmonotone Broyden-like algorithm in [10]. If {\rho }_k=0 in Equation (2.6), Algorithm 2.1 reduces to the inexact Broyden-like algorithm in [9].

Lemma 2.1　 Algorithm 2.1 is well-posed, i.e., for any k\ge 0, there exists a nonnegative integer m_k such that the nonmonotone line search Condition (2.5) is satisfied.

Proof　Refer to Lemma 4 in [9]. □

Corollary 2.1　 Let the sequence \left\{z^k\right\} be generated by Algorithm 2.1. Then, for any k\ge 0,

(2.8)f(z^k)\le C_k.

Lemma 2.2　 Let the function H(\cdot ) be defined by Equation (1.5). Then

H\left(z\right)=0\iff r=0\iff H\left(z\right)=\left[\begin{array}{c}0\\ r\end{array}\right].

Proof　We can get following equations from Equations (1.5) and (2.3):

H\left(z\right)=0\iff r=0\Rightarrow H\left(z\right)=\left[\begin{array}{c}0\\ r\end{array}\right].

Then, it is required to prove

H\left(z\right)=\left[\begin{array}{c}0\\ r\end{array}\right]\Rightarrow r=0.

In fact, given

H\left(z\right)=\left[\begin{array}{c}\mu \\ \mathrm{\Psi }\left(z\right)\end{array}\right]=\left[\begin{array}{c}0\\ r\end{array}\right],

there are \mu =0,\mathrm{\Psi }\left(z\right)=r. Thus,

\Vert \Psi \left(z\right){\Vert }^2=\Vert r{\Vert }^2\le {\eta }_k^2{f}^2\left(z\right)={\eta }_k^2({\mu }^2+\Vert \Psi (z\left){\Vert }^2\right).

Since 1-{\eta }_k>0,\mu =0, it follows that

\Vert \Psi \left(z\right){\Vert }^2\le \frac{{\eta }_k^2}{1-{\eta }_k^2}{\mu }^2=0\Rightarrow \Psi \left(z\right)=0\Rightarrow r=0.

The lemma is proven. □

3 Convergence analysis

This section discusses the convergence properties of Algorithm 2.1. To establish the global convergence of Algorithm 2.1, the following assumptions are provided:

Assumption 3.1　(i) The level set \Omega =\{z\in {\mathbb{R}}_{++}\times {\mathbb{R}}^n|f(z)\le f(z^0\left)\right\} is bounded.

(ii) H^{\prime }\left(z\right) is Lipschitz continuous, i.e., there exists a constant L such that

\Vert H^{\prime }\left(z^1\right)-H^{\prime }\left(z^2\right)\Vert \le L\Vert z^1-z^2\Vert ,\mathrm{\forall }{z}^1,z^2\in \mathrm{\Omega }.

(iii) For all \mathrm{\forall }z\in \Omega ,H^{\prime }\left(z\right) is nonsingular.

Lemma 3.1　 Let the sequence \left\{z^k\right\} be generated by Algorithm 2.1. Then, the sequence \left\{C_k\right\} is nonincreasing, and \left\{z^k\right\}\subset \Omega.

Proof　Refer to Lemma 6 in [10]. □

Lemma 3.2　 If Assumption 3.1 holds and the sequence \left\{z^k\right\} is generated by Algorithm 2.1, then

Proof　According to Assumption 3.1 and Equations (2.5) and (2.6), there is

{\sigma }_1{\Vert {\lambda }_k\mathrm{\Delta }{z}^k\Vert }^2+{\sigma }_2{\lambda }_{k}f(z^k)\le C_k-f\left(z^{k+1}\right)\le \frac{1}{1-{\rho }_1}(C_k-C_{k+1}).

Based on Lemma 3.2 and C_k\ge 0, it is concluded that the sequence \left\{C_k\right\} converges. Summing the inequality above over k yields the lemma’s conclusion.

The proof is complete. □

For convenience, define

(3.1)A_{k+1}:={\int }_0^1{H}^{\prime }\left(z^k+t{s}^k\right)\mathrm{d}t.

Then, y^k=A_{k+1}{s}^k, where y^k=H\left(z^{k+1}\right)-H(z^k)和s^k={\lambda }_k\mathrm{\Delta }{z}^k. Thus, Equation (2.7) can be rewritten as

(3.2)B_{k+1}=B_k+{\theta }_k\frac{\left(A_{k+1}-B_k\right)s^k{\left(s^k\right)}^{\mathrm{T}}}{\Vert s^k{\Vert }^2}.

Define

(3.3){\zeta }_k:=\frac{\Vert y_k-B_k{s}^k\Vert }{\Vert s^k\Vert },

and there is

(3.4){\zeta }_k=\frac{\Vert \left(A_{k+1}-B_k\right)s^k\Vert }{\Vert s^k\Vert }=\frac{\Vert \left(A_{k+1}-B_k\right)\mathrm{\Delta }{z}^k\Vert }{\Vert \mathrm{\Delta }{z}^k\Vert }.

The following lemma can be derived from Theorem 2.6 in reference [8].

Lemma 3.3　 Let the sequence \left\{{\zeta }_k\right\} be defined by Equation (3.4), and the sequence \left\{z^k\right\} be generated by Algorithm 2.1. If , then

\underset{k\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}} \frac{1}{k}\sum _{i=0}^{k-1} {\zeta }_i^2=0.

In particular, there exists a subsequence of \left\{{\zeta }_k\right\} that converges to 0. If

then

In particular, the entire sequence \left\{{\zeta }_k\right\} converges to 0.

Theorem 3.1　 If Assumption 3.1 holds, and the sequence \left\{z^k\right\} is generated by Algorithm 2.1, then every cluster point of \left\{z^k\right\} is a solution to Equation (1.6).

Proof　From Assumption 3.1 and Lemma 3.1, it is known that the sequence \left\{z^k\right\} is bounded. With generality, assume that \left\{z^k\right\} converges to \hat{z} (where \hat{z} is a cluster point of \left\{z^k\right\}). It follows that \hat{z} satisfies f\left(\hat{z}\right)=0. The analysis is divided into two cases:

Case 1: If there exist infinitely many k such that Condition (2.4) holds, then there are infinitely many k such that f\left(z^{k+1}\right)\le \alpha f(z^k). This implies \underset{k\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{f}} f(z^k)=0. Thus, the conclusion holds.

Case 2: If for all sufficiently large k,{\lambda }_k is defined by Equation (2.5), then from Lemmas 3.2 and 3.3, it is known that the sequence \left\{{\zeta }_k\right\} has a subsequence {\left\{{\zeta }_k\right\}}_{k\in K} that converges to 0. Since {\left\{z^k\right\}}_{k\in K} is bounded, it is assumed that {\left\{z^k\right\}}_{k\in K} converges to \hat{z}=(\hat{\mu },\hat{x}). According to Lemma 3.2, there are s^k=z^{k+1}-z^k\to 0 and A_{k+1}\to H^{\prime }\left(\hat{z}\right). Therefore, there exists a constant M>0 such that \Vert A_{k+1}^{-1}\Vert \le M for sufficiently large k\in K. According to Equations (2.4) and (3.4), there is

\begin{array}{rl}\Vert \mathrm{\Delta }{z}^k\Vert & =\Vert A_{k+1}^{-1}\left((A_{k+1}-B_k)\mathrm{\Delta }{z}^k-H(z^k)+\left[\begin{array}{c}0\\ r_k\end{array}\right]\right)\Vert \\ & \le M({\zeta }_k\Vert \mathrm{\Delta }{z}^k\Vert +f(z^k)+\eta f(z^k\left)\right).\end{array}

This implies that for sufficiently large k\in K, there exists a constant M_1>0, such that

(3.5)\Vert \mathrm{\Delta }{z}^k\Vert \le M_{1}f(z^k).

Assume {\{\mathrm{\Delta }{z}^k\}}_{k\in K} converges to \mathrm{\Delta }\hat{z}=(\mathrm{\Delta }\hat{\mu },\mathrm{\Delta }\hat{\omega }). Based on Equation (2.4), there is \Vert (A_{k+1}-B_k)\mathrm{\Delta }{z}^k\Vert ={\zeta }_k\Vert \mathrm{\Delta }{z}^k\Vert, which implies that for k\in K as k\to \mathrm{\infty }, B_k\mathrm{\Delta }{z}^k\to H^{\prime }\left(\hat{z}\right)\mathrm{\Delta }\hat{z}. Assume {\left\{r_k\right\}}_{k\in K} converges to \hat{r}, and with the help of Equation (2.2), \left\{{\eta }_k\right\} converges to \hat{\eta }. Therefore, for k\in K, when k\to \mathrm{\infty }, taking the limit on k in Equation (2.3), there is

(3.6)H\left(\hat{z}\right)+H^{\prime }\left(\hat{z}\right)\mathrm{\Delta }\hat{z}=\left[\begin{array}{c}0\\ \hat{r}\end{array}\right].

Let \underset{k(\in K)\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}{\lambda }_k=\hat{\lambda }. Then \hat{\lambda }\ge 0 and \hat{\lambda }\mathrm{\Delta }\hat{z}=0. If \hat{\lambda }>0, then \mathrm{\Delta }\hat{z}=0. Substituting them into Equation (3.6), there is

H\left(\hat{z}\right)=\left[\begin{array}{c}0\\ \hat{r}\end{array}\right].

According to Lemma 2.2, H\left(\hat{z}\right)=0 and f\left(\hat{z}\right)=0. If \hat{\lambda }=0, there is

\underset{k(\in K)\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}} {\lambda }_k=\hat{\lambda }=0.

For sufficiently large k\in K, Step 3 of Algorithm 2.1 implies that {\lambda }_k^{\prime }=\frac{{\lambda }_k}{\delta } does not satisfy Equation (2.5). Thus,

f(z^k+{\lambda }^{\prime }\mathrm{\Delta }{z}^k)-C_k\ge -{\sigma }_1{\Vert {\lambda }^{\prime }\mathrm{\Delta }{z}^k\Vert }^2-{\sigma }_2{\lambda }_k^{\prime }f(z^k).

From Corollary 2.1, it is known that

f(z^k+{\lambda }^{\prime }\mathrm{\Delta }{z}^k)-f(z^k)\ge -{\sigma }_1\Vert {\lambda }^{\prime }\mathrm{\Delta }{z}^k{\Vert }^2-{\sigma }_2{\lambda }_k^{\prime }f(z^k).

Rewriting this inequality, we have

\frac{f^2(z^k+{\lambda }^{\prime }\mathrm{\Delta }{z}^k)-f^2(z^k)}{{\lambda }^{\prime }}\ge (-{\sigma }_1\Vert {\lambda }^{\prime }\mathrm{\Delta }{z}^k{\Vert }^2-{\sigma }_{2}f(z^k\left)\right)\left(f\right(z^k+{\lambda }^{\prime }\mathrm{\Delta }{z}^k)+f(z^k\left)\right).

For k\in K, if k\to \mathrm{\infty }, there is

(3.7)-2{\sigma }_2{f}^2\left(\hat{z}\right)\le H\left(\hat{z}{)}^{\mathrm{T}}H\right(\hat{z})\mathrm{\Delta }\hat{z}\le -(1-\kappa \left)f^2\right(\hat{z}).

According to Equation (3.7), 1-\kappa -2{\sigma }_2\le 0, which implies {\sigma }_2\ge \frac{1-\kappa }{2}. This contradicts Step 0 of Algorithm 2.1. Therefore, f\left(\hat{z}\right)=0.

The proof is complete. □

The following analyzes the local convergence of Algorithm 2.1 by examining the properties of the functions H and \Psi defined in Equation (1.5).

Lemma 3.4　 Let the functions H:{\mathbb{R}}_{++}\times {\mathbb{R}}^n\to {\mathbb{R}}^{n+1} and \Psi :{\mathbb{R}}_{++}\times {\mathbb{R}}^n\to {\mathbb{R}}^n be defined by Equation (1.5). Then

(i) the function \Psi is semismooth on {\mathbb{R}}_{++}\times {\mathbb{R}}^n;

(ii) the function H is locally Lipschitz continuous and semismooth on {\mathbb{R}}_{++}\times {\mathbb{R}}^n. In addition, if F^{\prime }\left(x\right) is Lipschitz continuous on {\mathbb{R}}^n, then H is strongly semismooth on {\mathbb{R}}_{++}\times {\mathbb{R}}^n.

Proof　The proof is similar to Lemma 2.4 in reference [8]. □

Lemma 3.5　 If Assumption 3.1 holds, the sequence \left\{z^k\right\} is generated by Algorithm 2.1, and \underset{}{{lim}_{k\to \mathrm{\infty }}}{\eta }_k=0, then there exists a constant \zeta >0 and an index \overline{k}. When {\zeta }_k\le \zeta and k\ge \overline{k}, {\lambda }_k\equiv 1, where {\zeta }_k is defined in Equation (3.5). Furthermore, for k\ge \overline{k} such that {\zeta }_k\le \zeta, the following inequality holds:

(3.8)

Proof　From Step 2 of Algorithm 2.1, it is required to prove that there exists a constant \zeta >0 such that when {\zeta }_k\le \zeta and k is sufficiently large, Equation (3.8) holds. By Theorem 3.1, the sequence \left\{z^k\right\} converges to the solution of H\left(z\right)=0, denoted as z^{\ast }=(0,{\omega }^{\ast }). For sufficiently large k, there exists a constant M_1>0 such that: \Vert A_{k+1}^{-1}\Vert \le M_1. With the help of a proof similar to Equation (3.5), it is proved that there exist constants {\zeta }^{\prime }>0 and M_2>0 such that when {\zeta }_k\le {\zeta }^{\prime } and k is sufficiently large, there is

(3.9)\Vert \mathrm{\Delta }{z}^k\Vert \le M_{2}f(z^k).

Since the function H(\cdot ) is semismooth, for all z^k sufficiently close to z^{\ast }, there exists a constant L_1>0 such that

(3.10)f(z^k)=\Vert H(z^k)-H\left(z^{\ast }\right)\Vert \le L_1\Vert z^k-z^{\ast }\Vert .

On the other hand, because the matrix H\left(z^{\ast }\right) is nonsingular and the sequence \left\{z^k\right\} converges to z^{\ast }, for all z^k sufficiently close to z^{\ast }, there exists a constant L_2>0 such that

(3.11)f(z^k)=\Vert H(z^k)-H\left(z^{\ast }\right)\Vert \ge L_2\Vert z^k-z^{\ast }\Vert .

According to Equations (3.10) and (3.11), there is

(3.12)o\left(\Vert z^k-z^{\ast }\Vert \right)=o\left(\Vert H(z^k)-H\left(z^{\ast }\right)\Vert \right)=o\left(\Vert H(z^k)\Vert \right).

According to Equations (3.11) and (3.12), there is

(3.13)\Vert \mathrm{\Delta }{z}^k\Vert \le M_2\Vert H(z^k)-H\left(z^{\ast }\right)\Vert \le M_2{L}_1\Vert z^k-z^{\ast }\Vert .

With the help of Equation (2.3), there is

\begin{array}{rl}{A}_{k+1}(z^k+\mathrm{\Delta }{z}^k-z^{\ast })& =A_{k+1}(z^k-z^{\ast })+(A_{k+1}-B_k)\mathrm{\Delta }{z}^k-H(z^k)+\lfloor \begin{array}{c}0\\ r_k\end{array}\rfloor \\ & =(A_{k+1}-H^{\prime }(z^k\left)\right)(z^k-z^{\ast })+(A_{k+1}-B_k)\mathrm{\Delta }{z}^k+\left[\begin{array}{c}0\\ r_k\end{array}\right]\\ & -\left[H\right(z^k)-H(z^{\ast })-H^{\prime }(z^k\left)\right(z^k-z^{\ast }\left)\right].\end{array}

This implies

(3.14)\begin{array}{rl}\Vert z^k+\mathrm{\Delta }{z}^k-z^{\ast }\Vert & \le \Vert A_{k+1}^{-1}\Vert \left(\Vert A_{k+1}-H^{\prime }(z^k)\Vert \Vert z^k-z^{\ast }\Vert +\Vert \left(A_{k+1}-B_k\right)\mathrm{\Delta }{z}^k\right|\\ & +\Vert r_k\Vert +\Vert H(z^k)-H\left(z^{\ast }\right)-H^{\prime }(z^k)(z^k-z^{\ast })\Vert )\\ & \le M_1\left({\zeta }_k{M}_2{L}_1\Vert z^k-z^{\ast }\Vert +o\left(\Vert z^k-z^{\ast }\Vert \right)\right).\end{array}

For all z^k sufficiently close to z^{\ast }, there is

\begin{array}{rl}f(z^k+\mathrm{\Delta }{z}^k)& =\Vert H(z^k+\mathrm{\Delta }{z}^k)-H\left(z^{\ast }\right)\Vert \\ & \le L_1\Vert z^k+\mathrm{\Delta }{z}^k-z^{\ast }\Vert \\ & \le M_3\Vert z^k-z^{\ast }\Vert +o(\Vert z^k-z^{\ast }\Vert ),\end{array}

where M_3=M_1{M}_2{L}_1^2{\zeta }_k. For sufficiently large k, based on Equations (3.9), (3.13), and (3.14), there is

(3.15)f(z^k+\mathrm{\Delta }{z}^k)-\alpha f(z^k)+\sigma {\Vert \mathrm{\Delta }{z}^k\Vert }^2\le (M_3{\zeta }_k-\alpha L_2)\Vert z^k-z^{\ast }\Vert +o(\Vert z^k-z^{\ast }\Vert ).

Let \hat{\zeta }=\mathrm{m}\mathrm{i}\mathrm{n}\{\zeta ,\frac{\alpha L_2}{2M_3}\}. Then, according to Equation (3.15), when {\zeta }_k\le \hat{\zeta }, there is

f(z^k+\mathrm{\Delta }{z}^k)-\alpha f(z^k)+\sigma {\Vert \mathrm{\Delta }{z}^k\Vert }^2\le -\frac{\alpha L_2}{2}\Vert z^k-z^{\ast }\Vert +o(\Vert z^k-z^{\ast }\Vert ).

Thus, for z^k sufficiently close to z^{\ast }, {\lambda }_k=1 satisfies Equation (3.8). The proof is complete. □

The following analyzes the superlinear convergence of Algorithm 2.1.

Theorem 3.2　 If Assumption 3.1 holds, let z^{\ast } be a cluster point of the sequence \left\{z^k\right\} generated by Algorithm 2.1, and assume \underset{}{{lim}_{k\to \mathrm{\infty }}}{\eta }_k=0, then \left\{z^k\right\} converges superlinearly to z^{\ast }, i.e., \Vert z^{k+1}-z^{\ast }\Vert =o(\Vert z^k-z^{\ast }\Vert ).

Proof　From Equation (3.14), it is required to prove that \underset{}{\mathrm{l}{\mathrm{i}\mathrm{m}}_{k\to \mathrm{\infty }}}{\zeta }_k=0. According to Lemma 3.5, there exists an index \hat{k} such that for {\zeta }_k\le \zeta and k\in I_{\hat{k}}=\{k|k\ge \hat{k}\}, there is {\lambda }_k\equiv 1. Based on Lemma 3.2, there is

According to Equation (3.11), there is

Moreover,

\begin{array}{rl}\Vert s^k\Vert & =\Vert z^{k+1}-z^k\Vert =\Vert (z^{k+1}-z^{\ast })+(z^{\ast }-z^k)\Vert \\ & \le \Vert z^{k+1}-z^{\ast }\Vert +\Vert z^{\ast }-z^k\Vert .\end{array}

Thus, . By Lemma 3.3, it follows that \underset{k\to \mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}{\zeta }_k=0. The proof is complete. □

The proof follows similarly to Theorem 5.2 in reference [1], where the local quadratic convergence of Algorithm 2.1 is established under the given conditions.

Theorem 3.3　 If Assumption 3.1 holds, all V\in \mathrm{\partial }H\left(z^{\ast }\right) are nonsingular, and the function F\left(x\right) is Lipschitz continuous on {\mathbb{R}}^n, then the sequence \left\{z^k\right\} generated by Algorithm 2.1 converges quadratically to z^{\ast }, i.e.,

\Vert z^{k+1}-z^k\Vert =O\left({\Vert z^k-z^{\ast }\Vert }^2\right).

4 Numerical experiments

To verify the feasibility and effectiveness of the algorithm, this section presents several experiments. The algorithm was implemented with the help of MATLAB 7.0. The parameters were set as follows: \delta =0.5, {\mu }_0={10}^{-5}, \sigma ={\sigma }_1={\sigma }_2=0.01, {\rho }_k=0.5, {\theta }_k=1, \rho =0.5, {\eta }_k={0.01}^{k+1}, \alpha =0.01, r_k={\eta }_k\mathrm{\Psi }(z^k), and the termination criterion was f(z^k)\le {10}^{-6}. B_0 was initialized as the identity matrix.

Example 4.1　Kojima-Shindo Problem [2-3]

F\left(x\right)=\{\begin{array}{l}3x_1^2+2x_1{x}_2+2x_2^2+x_3+3x_4-6,\\ 2x_1^2+x_1+x_2^2+10x_3+2x_4-2,\\ 3x_1^2+x_1{x}_2+2x_2^2+2x_3+9x_4-9,\\ x_1^2+3x_2^2+2x_3+3x_4-3.\end{array}

This problem has a degenerate solution {(\frac{\sqrt{6}}{2},0,0,\frac{1}{2})}^{\mathrm{T}} and a non-degenerate solution (1,0,3,0{)}^{\mathrm{T}}. The experimental results are shown in Tab.1.

Example 4.2　Modified Mathiesen Equilibrium Problem [2, 4, 5, 10]

F\left(x\right)=\{\begin{array}{l}-x_2+x_3+x_4,\\ x_1-{\displaystyle \frac{4.5x_3+2.7x_4}{x_2+1}},\\ 5-x_1-{\displaystyle \frac{0.5x_3+0.3x_4}{x_3+1}},\\ 3-x_1.\end{array}

This problem has many infinitely optimal solutions (\lambda ,0,0,0), where \lambda \in \left[0,3\right]. When \lambda =0 or 3, the solution is degenerate; when \lambda \in \left(0,3\right), the solution is non-degenerate. The experimental results are shown in Tab.2.

Example 4.3　Murty Problem [2, 10]. The test function is F\left(x\right)=Mx+q,

where

M=\left[\begin{array}{ccccc}1& 2& 2& \cdots & 2\\ 0& 1& 2& \cdots & 2\\ 0& 0& 1& \cdots & 2\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ 0& 0& 0& \cdots & 1\end{array}\right],q=(-1,\cdots ,-1{)}^{\mathrm{T}}.

This problem has a unique optimal solution x^{\ast }=(0,\dots ,0,1{)}^{\mathrm{T}}. The initial point was chosen as x^0=(1,1,\dots ,1{)}^{\mathrm{T}}. The experimental results for different dimensions are shown in Tab.3.

The results in Tab.1-Tab.3 demonstrate that the nonmonotone and inexact Broyden-like algorithm reduces the number of iterations and significantly shortens runtime when solving nonlinear complementarity problems. This indicates that the algorithm is highly effective.

References

[1] Chen B.L. , Ma, C.F.. Superlinear/quadratic smoothing Broyden-like method for the generalized nonlinear complementarity problem. Nonlinear Anal. Real World Appl. 2011; 12: 1250–1263

[2] Fan B., Ma, C.F. , Xie, Y.J.. A Nonmonotone Broyden-like method for nonlinear complementarity problems. Math. Numer. Sin. 2013; 36(2): 181–194

[3] Harker P.T. , Pang, J.S.. Finite-dimensional variational inequality and nonlinear complementarity problems: a survey of theory, algorithms and applications. Math. Program. 1990; 48: 161–220

[4] Huang Z.H., Han, J.Y. , Chen, Z.W.. Predictor-corrector smoothing Newton method, based on a new smoothing function, for solving the nonlinear complementarity problem with a Po function. J. Optim. Theory Appl. 2003; 117: 39–68

[5] Jiang H.Y. , Qi, L.Q.. A new nonsmooth equations approach to nonlinear complementarity problems. SIAM J. Control Optim. 1997; 35: 178–193

[6] Liu R.J. , Dong, L.. Nonmonotone smoothing inexact Newton method for the nonlinear complementarity problem. J. Appl. Math. Comput. 2016; 51: 659–674

[7] Wang D.G., Pan, X. , Wang, D.Q.. Study on nonlinear complementarity problem by using the Fischer-Burmeister function. J. Inner Mongolia Agricultural Univ. 2006; 27(2): 133–134

[8] Wang Y.J., Ma, F.M. , Zhang, J.Z.. A nonsmooth L-M method for solving the generalized nonlinear complementarity problem over a polyhedral cone. Appl. Math. Optim. 2005; 52: 73–92

[9] Wu P.Y. , Zhang, L.. An inexact Broyden method for nonlinear equations. Math. Theory Appl. 2016; 36(2): 1–9

[10] Zheng X.Y., Shi, J.R., Yang, W. , Yin, Q.Y.. Nonmonotone smoothing Broyden-like method for generalized nonlinear complementarity problems. J. Appl. Math. Comput. 2017; 54: 277–295

RIGHTS & PERMISSIONS

Higher Education Press 2025