# Convergence Analysis of a Trust-Region Multidimensional Filter Method for Nonlinear Complementarity Problems

Authors: C. W. Wu; J. P. Cao; L. F. Wang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

For solving nonlinear complementarity problems, a new algorithm is proposed by using multidimensional filter techniques and a trust-region method. The algorithm is shown to be globally convergent under the reasonable assumptions and does not depend on any extra restoration procedure. In particular, it shows that the subproblem is a convex quadratic programming problem, which is easier to be solved. The results of numerical experiments show its efficiency.


---

## Body

## 1. Introduction

LetFx:ℜn⟼ℜn be a continuous differentiable function. The nonlinear complementarity problem (NCP) is to find a vector x∈ℜn such that(1)x≥0,Fx≥0,xTFx=0.For convenience, denoteℐ=1,2,…,n. Throughout this paper, ⋅ denotes the Euclidean norm.The traditional approach for NCP involves reformulating the problem as an optimization problem [1–12] or a nonlinear differentiable function [13–18]. In this paper, a new method for solving this optimization problem is based on the class of trust-region methods and also filter methods introduced by Fletcher and Leyffer in 1997 and subsequently published as [19]. This technique has important reference value for many nonlinear system problems [20–22]. The idea of filter methods is that trial points are accepted as long as they could reduce the value of objective function or improve the feasibility, which is different from the conventional approach of combining these two measures by a penalty function. Filter approaches play an important role to balance the objective function and constraints and have advantages over penalty function methods. Numerical experiments have shown the impressing efficiency of filter methods [19, 23]. The global convergence proof of filter-SQP algorithm is given by Fletcher et al. [24], and relevant superlinear local convergence is achieved by Ulbrich [25].Because of good numerical results, filter techniques are extensively studied to handle the nonlinear complementarity problem [7–9, 26, 27]. Most of the contributions to NCP of filter algorithms rely on an external “restoration procedure” [19, 27–29] whose purpose is to reduce constraint infeasibilities, since the filter idea introduced by Fletcher and Leyffer [19] is based on constrained optimization problems, and the constrained optimization problems transformed by NCP may be infeasible. Gould et al. [30, 31] proposed a multidimensional filter algorithm for nonlinear unconstrained optimization problems instead of a two-dimensional filter [19] for constrained optimization problems. This motivates us to consider the possibility of reformulating NCP as an unconstrained optimization problem and solving the optimization by a multidimensional filter method. In spite of the fact, we suggest a reformulation of NCP as an optimization problem with nonnegativity constraints because Fischer [2] points out that stationary points with negative components can be avoided in contrast to the reformulation as unconstrained minimization problem. Unfortunately, the multidimensional filter method is proposed on unconstrained optimization [30, 31].There are two main motivations of this paper. One is to find an effective method to overcome the influence of “restoration procedure” on the efficiency of the algorithm. The other is to find a technology to solve the constrained optimization problem with nonnegative constraints by using a multidimensional filter method, just like solving the unconstrained optimization problem, so as to solve the NCP problem. Our proposal is to reformulate NCP as an optimization problem with nonnegative constraints and solve the optimization by a multidimensional filter method. The gradient-projection method [32] shows that the first-order optimality condition of the nonnegativity constrained optimization problem is equivalent to the fact that the projected gradient is zero, which is similar to the optimality condition of the unconstrained optimization problem. The characteristics of NCP make sure that the trust-region subproblem of the equivalent reformulation is a convex quadratic programming problem because the matrix B in the subproblem is a positive semidefinite symmetric matrix. Even we find that the twice continuously differentiability of Fx implies that B is uniformly bounded. It is very important for the global convergent analysis of our algorithm. Especially, the new algorithm does not depend on any extra restoration procedure because it always remains the compatibility of the trust-region subproblem.This paper is organized as follows: the algorithm and preliminaries are introduced in Section2 and the global convergence analysis for the proposed method is given in Section 3. Some numerical results are reported in Section 4. The final section gives some conclusions.


## 2. The Algorithm and Preliminaries

In this section, we will describe the specific strategies and motivations for solving problem (1) and finally present a multidimensional filter algorithm for the nonlinear complementarity problem.


### 2.1. Equivalent Model and Gradient-Projection Method

We consider using the Fischer–Burmeister function [33] to reformulate NCP as the following optimization problem and solve the optimization by a multidimensional filter method:(2)minx≥0fμx≔12ΦμxTΦμx,where μ≥0 is a smooth parameter, and Φμx=x12+F12x+μ2−x1−F1x,…,xn2+Fn2x+μ2−xn−FnxT. For μ=0, we get the following equivalence relation [34]: x∗solves (1) ⟺x∗ solves (2). Nonnegative constraints in optimization problem (2) can help to avoid stationary points with negative components [2], but it brings some troubles to the multidimensional filter method [30, 31]. Therefore, we use a gradient-projection method [32] and define the “projected” gradient of fμx into the feasible set of problem (2) as follows:(3)g¯μ,ix=gμ,ix,xi≥gμ,ix,xi,xi<gμ,ix,where gμ,ix is the i-th component of the gμx, gμx≔∇xfμx and i∈ℐ.The advantage of this strategy is obvious:xμ∗ is a KKT point of problem (2) if and only if g¯μxμ∗=0. So, we can use a multidimensional filter method to solve problem (2) when μ approaches to zero just as we can solve unconstrained optimization problem.


### 2.2. Trust-Region Subproblem

To solve problem (2), we compute a trial step dk by finding an approximation to the solution of the trust-region subproblem:(4)minQkd=fμkxk+∇xfμkxkTd+12dTBkd,s.t.xk+d≥0,d∞≤Δk,where xk is the current iteration point, Δk is the trust-region radius, and Bk=∇xΦμkxk∇xΦμkxkT, and ∇xΦμx≔bijnn, bij=∂Φμ,jx/∂xi. The positive parameters μk tend to zero during the iterate of algorithm. A trial point xk+ is then computed by the trial step dk; denote xk+=xk+dk.Subproblem (4) obviously has a solution d=0 at least. Therefore, our new algorithm does not depend on any extra restoration procedure [19, 27–29] because it always remains the compatibility of the trust-region subproblem. Especially, we note that the characteristics of NCP make sure that the trust-region subproblem of the equivalent reformulation is a convex quadratic programming problem, which is comparatively easy to solve.


### 2.3. The Multidimensional Filter Mechanism

Whether the new trial pointxk+ can be considered as a successful point requires the following multidimensional filter mechanism [30, 32] to assist in judgment. This mechanism helps the components of function g¯μx to approach to zero evenly and provides an effective rule to judge whether xk+ is accepted. In practical computation, a iterate point xk is said to dominate another point xl if and only if g¯μk−1,ixk≤g¯μl−1,ixl, ∀i∈ℐ. Besides, a filter set ℱ is a set of points such that no pair dominates any other.Acceptability rule: a new trial pointxk+ is acceptable for the filter ℱk if and only if(5)∀xl∈ℱk,∃j∈ℐ,g¯μk,jxk+≤g¯μl−1,jxl−γgg¯μl−1xl,where γg∈0,1/n. If an iterate xk is acceptable for the filter ℱk, we add it to the filter and remove from it every xl∈ℱk such that g¯μk,ixk+≤g¯μl−1,ixl for all i∈ℐ, i.e.,(6)ℱk+1=ℱk∪xk+\Dk,where(7)Dk=xl∈ℱkg¯μk,ixk+≤g¯μl−1,ixl,∀i∈ℐ.


### 2.4. A Multidimensional Filter Algorithm for NCPs

In this part, we will present a multidimensional filter algorithm for nonlinear complementarity problem (1).Algorithm 1.
A multidimensional filter algorithm for NCPs.Step 0: initialization. An initial point and an initial trust-region radiusΔ0 are given. Let an initial point x0, an initial trust-region radius Δ0>0, and an initial filter set ℱ0=105,…,105T be given, as well as constants ε, γg∈0,1/n, 0<γ1<γ2<1<γ3, 0<η1<η2<1, 0<Δ0≤Δmax. Compute fμ0x0,  gμ0x0, g¯μ0x0, B0, set k≔0.Step 1: test for optimality. Ifg¯μkxk+μk<ε, stop.Step 2: determine a trial step. Compute a solutiondk of subproblem (4).Step 3: ifdk=0, set xk+1=xk,μk+1=θμk,Bk+1=Bk, k≔k+1, and go to Step1; otherwise, set xk+=xk+dk, and compute fμkxk+, g¯μkxk+.Step 4: test for optimality. Ifg¯μkxk++μk<ε, stop; otherwise, compute(8)ρk=fμkxk−fμkxk+Qk0−Qkdk.Step 5: tests to accept the trial step.(i)
Ifρk≥η1, set xk+1=xk+,ℱk+1=ℱk∪xk+\Dk;(ii)
Besides, ifρk<η1 and xk+ is acceptable for the filter ℱk, set xk+1=xk+,ℱk+1=ℱk∪xk+\Dk,(iii)
Otherwise, setxk+1=xk, ℱk+1=ℱk.Step 6: update the trust-region radius and the smooth parameter.(9)Δk+1=γ1Δk,γ2Δk,ifρk<η1,γ2Δk,Δk,ifρk∈η1,η2,minΔmax,γ3Δk,ifρk≥η2.(10)μk+1=θμk,ifμk>0.1g¯μkxk+1,μk,otherwise.Step 7: computefμk+1xk+1, gμk+1xk+1, g¯μk+1xk+1, Bk+1, set k≔k+1, and go to Step1.
Note that, there is an advantage to choosing a largeΔk+1=γ3Δk when ρk≥η2, but it may be unwise to choose it to be too large; hence, we give a upper bound Δmax and set Δk+1=minΔmax,γ3Δk when ρk≥η2. Specifically, Bk+1=∇xΦμk+1xk+1∇xΦμk+1xk+1T can be computed easily instead of updating Bk+1 with higher numerical expenditure (e.g., BFGS). By the way, from (8), we are surprised to find that the smooth parameter μk does not tend to zero before g¯μkxk during our algorithm. In other words, fμkx is twice continuously differentiable form beginning to end; this is a critical condition to our algorithm.


## 2.1. Equivalent Model and Gradient-Projection Method

We consider using the Fischer–Burmeister function [33] to reformulate NCP as the following optimization problem and solve the optimization by a multidimensional filter method:(2)minx≥0fμx≔12ΦμxTΦμx,where μ≥0 is a smooth parameter, and Φμx=x12+F12x+μ2−x1−F1x,…,xn2+Fn2x+μ2−xn−FnxT. For μ=0, we get the following equivalence relation [34]: x∗solves (1) ⟺x∗ solves (2). Nonnegative constraints in optimization problem (2) can help to avoid stationary points with negative components [2], but it brings some troubles to the multidimensional filter method [30, 31]. Therefore, we use a gradient-projection method [32] and define the “projected” gradient of fμx into the feasible set of problem (2) as follows:(3)g¯μ,ix=gμ,ix,xi≥gμ,ix,xi,xi<gμ,ix,where gμ,ix is the i-th component of the gμx, gμx≔∇xfμx and i∈ℐ.The advantage of this strategy is obvious:xμ∗ is a KKT point of problem (2) if and only if g¯μxμ∗=0. So, we can use a multidimensional filter method to solve problem (2) when μ approaches to zero just as we can solve unconstrained optimization problem.


## 2.2. Trust-Region Subproblem

To solve problem (2), we compute a trial step dk by finding an approximation to the solution of the trust-region subproblem:(4)minQkd=fμkxk+∇xfμkxkTd+12dTBkd,s.t.xk+d≥0,d∞≤Δk,where xk is the current iteration point, Δk is the trust-region radius, and Bk=∇xΦμkxk∇xΦμkxkT, and ∇xΦμx≔bijnn, bij=∂Φμ,jx/∂xi. The positive parameters μk tend to zero during the iterate of algorithm. A trial point xk+ is then computed by the trial step dk; denote xk+=xk+dk.Subproblem (4) obviously has a solution d=0 at least. Therefore, our new algorithm does not depend on any extra restoration procedure [19, 27–29] because it always remains the compatibility of the trust-region subproblem. Especially, we note that the characteristics of NCP make sure that the trust-region subproblem of the equivalent reformulation is a convex quadratic programming problem, which is comparatively easy to solve.


## 2.3. The Multidimensional Filter Mechanism

Whether the new trial pointxk+ can be considered as a successful point requires the following multidimensional filter mechanism [30, 32] to assist in judgment. This mechanism helps the components of function g¯μx to approach to zero evenly and provides an effective rule to judge whether xk+ is accepted. In practical computation, a iterate point xk is said to dominate another point xl if and only if g¯μk−1,ixk≤g¯μl−1,ixl, ∀i∈ℐ. Besides, a filter set ℱ is a set of points such that no pair dominates any other.Acceptability rule: a new trial pointxk+ is acceptable for the filter ℱk if and only if(5)∀xl∈ℱk,∃j∈ℐ,g¯μk,jxk+≤g¯μl−1,jxl−γgg¯μl−1xl,where γg∈0,1/n. If an iterate xk is acceptable for the filter ℱk, we add it to the filter and remove from it every xl∈ℱk such that g¯μk,ixk+≤g¯μl−1,ixl for all i∈ℐ, i.e.,(6)ℱk+1=ℱk∪xk+\Dk,where(7)Dk=xl∈ℱkg¯μk,ixk+≤g¯μl−1,ixl,∀i∈ℐ.


## 2.4. A Multidimensional Filter Algorithm for NCPs

In this part, we will present a multidimensional filter algorithm for nonlinear complementarity problem (1).Algorithm 1.
A multidimensional filter algorithm for NCPs.Step 0: initialization. An initial point and an initial trust-region radiusΔ0 are given. Let an initial point x0, an initial trust-region radius Δ0>0, and an initial filter set ℱ0=105,…,105T be given, as well as constants ε, γg∈0,1/n, 0<γ1<γ2<1<γ3, 0<η1<η2<1, 0<Δ0≤Δmax. Compute fμ0x0,  gμ0x0, g¯μ0x0, B0, set k≔0.Step 1: test for optimality. Ifg¯μkxk+μk<ε, stop.Step 2: determine a trial step. Compute a solutiondk of subproblem (4).Step 3: ifdk=0, set xk+1=xk,μk+1=θμk,Bk+1=Bk, k≔k+1, and go to Step1; otherwise, set xk+=xk+dk, and compute fμkxk+, g¯μkxk+.Step 4: test for optimality. Ifg¯μkxk++μk<ε, stop; otherwise, compute(8)ρk=fμkxk−fμkxk+Qk0−Qkdk.Step 5: tests to accept the trial step.(i)
Ifρk≥η1, set xk+1=xk+,ℱk+1=ℱk∪xk+\Dk;(ii)
Besides, ifρk<η1 and xk+ is acceptable for the filter ℱk, set xk+1=xk+,ℱk+1=ℱk∪xk+\Dk,(iii)
Otherwise, setxk+1=xk, ℱk+1=ℱk.Step 6: update the trust-region radius and the smooth parameter.(9)Δk+1=γ1Δk,γ2Δk,ifρk<η1,γ2Δk,Δk,ifρk∈η1,η2,minΔmax,γ3Δk,ifρk≥η2.(10)μk+1=θμk,ifμk>0.1g¯μkxk+1,μk,otherwise.Step 7: computefμk+1xk+1, gμk+1xk+1, g¯μk+1xk+1, Bk+1, set k≔k+1, and go to Step1.
Note that, there is an advantage to choosing a largeΔk+1=γ3Δk when ρk≥η2, but it may be unwise to choose it to be too large; hence, we give a upper bound Δmax and set Δk+1=minΔmax,γ3Δk when ρk≥η2. Specifically, Bk+1=∇xΦμk+1xk+1∇xΦμk+1xk+1T can be computed easily instead of updating Bk+1 with higher numerical expenditure (e.g., BFGS). By the way, from (8), we are surprised to find that the smooth parameter μk does not tend to zero before g¯μkxk during our algorithm. In other words, fμkx is twice continuously differentiable form beginning to end; this is a critical condition to our algorithm.


## 3. Analysis for Global Convergence

Global convergence properties of Algorithm1 will be proved under the following assumptions.A1. Fx:ℜn⟶ℜn is a twice continuously differentiable function.A2. The iterates xk remain in a closed, bounded convex domain Ω of ℜn.Note that, for subproblem (4), A1 and A2 together imply that Bk is uniformly bounded on Ω. In other words, there exist constants κumb>0 such that Bk≤κumb,∀k.


### 3.1. Well Definedness

Letdk denote the solution of (4), then we have some technical lemmas which are very important for the global convergence of Algorithm 1.Lemma 1.
Ifdk=0, we have g¯μkxk=0.Proof.
We first change the constraintd∞≤Δk to another form d+Δke≥0 and d−Δke≤0, then we have the Lagrange function of (4):(11)Ld,λ,μ¯,μ^=Qkd−λTxk+d−μ¯Td+Δke+μ^Td−Δke,where λ,μ¯,μ^∈Rn are Lagrange multipliers, e=1,1,…,1T∈ℜn. Since dk is the solution of (4), we then obtain that(12)∇dLdk,λ,μ¯,μ^=0,λ,μ¯,μ^≥0,xk+dk≥0,dk+Δke≥0,dk−Δke≤0,λTxk+dk=μ¯Tdk+Δke=μ^Tdk−Δke=0.
Observe thatdk=0 and Δk>0 ensure that(13)gμkxk=λ+μ¯−μ^,λ,xk≥0,λTxk=0,μ¯=μ^=0.
Thus,xkTgμkxk=0, i.e., g¯μkxk=0.Lemma 2.
(see [32]). There exists a constant κmdc∈0,1 such that(14)Qk0−Qkdk≥κmdcg¯μkxkming¯μkxk1+Bk,Δk.Lemma 3.
(see [35]). Suppose that A1 and A2 hold. If g¯μkxk≠0 and(15)Δk≤minκmdc1−η2κubh,11+κumb⋅g¯μkxk,we have ρk≥η2, and Δk+1≥Δk.Consequently, we may now obtain that the trust-region radius cannot become arbitrarily small if the iterates stay away from first-order critical points.Lemma 4.
Suppose that A1 and A2 hold. Suppose furthermore that there exists a constantκlpg>0 such that g¯μkxk≥κlpg for all k. Then, there is a constant κlbd>0 such that Δk≥κlbd for all k.Proof.
Assume that iterationk0 is the first such that(16)Δk0≤γ1κlpg⋅minκmdc1−η2κubh,11+κumb.
Then, we have from our assumptiong¯μkxk≥κlpg and (9) that γ1Δk−1≤Δk,∀k, and hence, Δk0−1≤minκmdc1−η2/κubh,1/1+κumb⋅g¯μk0−1xk0−1. It implies that (15) holds and thus Δk0−1≤Δk0. But this contradicts the fact that iteration k0 is the first such that (16) holds, and our initial assumption is therefore impossible.


### 3.2. Convergence to Stationary Points

For convenience of discussion, we shall denoteT=kdk=0 as the set of zero-solution of (4) iterations, denote S=kxk+1≠xk as the set of successful iterations, denote U=kρk<η1,xk+is not accepted byℱk as the set of unsuccessful iterations, and denote P=kρk<η1,xk+is accepted byℱk as the set of iterations which is not accepted by trust-region rule but filter rule (5). Now, we consider the first-order global convergent conclusion of our algorithm in the following three cases: T=+∞, U=+∞, and S=+∞.Theorem 1.
Suppose that A1 and A2 hold and thatT=+∞, then limk∈Tg¯μkxk+μk=0.Proof.
Note that, ifT=+∞, Lemma 1 implies that g¯μkxk=0. Moreover, by the mechanism of updating μk (10), we have μk+1=θμk. Then, we get the first-order global convergence of our Algorithm 1limk∈Tg¯μkxk+μk=0, i.e., Algorithm 1 can be terminated with finite steps.Theorem 2.
Suppose that A1 and A2 hold and thatU=+∞, then limk∈Ug¯μkxk+μk=0.Proof.
Assume, to arrive at a contradiction, that there existε>0 and k0 such that(17)g¯μkxk+μk≥ε,∀k>k0.
SinceU=+∞, there exists a positive integer k1>k0 such that(18)xk=xk1,∀k≥k1.
By the mechanism of updatingμk (10), we can consider two cases.Case 1.
limk⟶∞μk≠0, i.e., there exists a positive integer k2≥k1 such that μk=μk2 for all k≥k2. By Algorithm 1, we obtain that(19)Δk≤γ2k−k2Δk2,μk≤0.1g¯μkxk+1,for all k≥k2. Hence, we can deduce from (18) and (19) that g¯μkxk≥κlpg for all k≥k2, where κlpg=10μk2. Note that γ2∈0,1 in Algorithm 1, so we have limk⟶∞Δk=0. Applying Lemma 4, there is a constant κlbd>0 such that Δk≥κlbd for all k, which contradicts the fact limk⟶∞Δk=0, as stated in (19). Therefore, Case 1 cannot hold.Case 2.
limk⟶∞μk=0. We deduce from (17) that there is a integer k3≥k1 such that g¯μkxk≥0.5ε≥10μk for all k≥k3, i.e., μk≤0.1g¯μkxk=0.1g¯μkxk+1, for all k≥k3. By the mechanism of updating μk, then we have μk=μk3 for all k≥k3, which contradicts limk⟶∞μk=0. Thus, Case 2 cannot hold. Our initial assumption must then be false.Theorem 3.
Suppose that A1 and A2 hold and thatS=+∞, then limk∈Sg¯μkxk+μk=0.Proof.
Assume, to arrive at a contradiction, that there existε>0 and k0 such that(20)g¯μkxk+μk≥ε,∀k>k0.
By the mechanism of updatingμk (10), we can consider two cases.Case 3.
limk⟶∞μk≠0, i.e., there exists a positive integer k1>k0 such that μk=μk1 for all k≥k1. Observe first that (10) implies that μk≤0.1g¯μkxk+1=0.1g¯μk+1xk+1,∀k≥k1. Let κlpg=10μk1, then(21)g¯μkxk≥κlpg,∀k>k1.(i)
P<+∞ (i.e. S\P=+∞). That means there exists a positive integer k2≥k1 such that either k∈S\P or k∈S¯ for all k≥k2. Besides, we can deduce from S=+∞ that ρk≥η1 for all k∈S\P. Then, by (9), we have that for all k>k2,(22)fμk2xk2−fμkxk=∑j=k2,j∈S\Pk−1fμjxj−fμj+1xj+1+∑j=k2,j∈S¯k−1fμjxj−fμj+1xj+1=∑j=k2,j∈S\Pk−1fμjxj−fμj+1xj+1≥∑j=k2,j∈S/Pk−1η1Qj0−Qjdj≥η1κmdcκlpg⋅∑j=k2,j∈S/Pk−1minκlpg1+κumb,Δj.Hence, we deduce from the boundedness offμkxk that limk>k2Δk=0. But it derives a contradiction from (21) and Lemma 3.(ii)
P=+∞. Assumptions A1 and A2 show that g¯μkxk+1 is a bounded subsequence. Then, there exists an infinite subsequence kiki>k1⊆P such that(23)limi⟶∞g¯μkixki+1=g¯∞≥κlpg.
By definition ofki∈P, xki+1 is acceptable for the current filter ℱki. This implies, by (21) and filter mechanism (5), that, for each xk∈ℱki, there exists an index jk∈ℐ such that(24)g¯μki,jkxki+1≤g¯μk−1,jkxk−γgg¯μk−1xk=g¯μk−1,jkxk−γgg¯μkxk≤g¯μk−1,jkxk−γgκlpg.
Ifxki−1+1∉ℱki, we obtain from (6) and (7) that there exists xks∈ℱki such that g¯μks−1,jxks≤g¯μki−1,jxki−1+1,∀j∈ℐ. Thus, (24) ensures that there exists an index jks∈ℐ such that(25)g¯μki,jksxki+1−g¯μki−1,jksxki−1+1≤−γgκlpg.
Ifxki−1+1∈ℱki, (23) implies that there exists an index jki−1+1∈ℐ such that(26)g¯μki,jki−1+1xki+1−g¯μki−1,jki−1+1xki−1+1≤−γgκlpg.
Since the finite possibility ofjki−1+1, let jki−1+1=j0. Then, the left-hand side of inequality (25) and (26) tends to zero when i tends to infinity because of (23), which is impossible. In a word, Case 3 does not happen.Case 4.
limk⟶∞μk=0. The infiniteness of S and (10) implies that there exists a infinite index K⊆S such that limk∈Kg¯μkxk+1=limk∈Kg¯μkxk+=0. We then obtain that limk∈Kg¯μkxk++μk=0, which contradicts (20), and therefore, Case 4 cannot hold, yielding the desired result.


## 3.1. Well Definedness

Letdk denote the solution of (4), then we have some technical lemmas which are very important for the global convergence of Algorithm 1.Lemma 1.
Ifdk=0, we have g¯μkxk=0.Proof.
We first change the constraintd∞≤Δk to another form d+Δke≥0 and d−Δke≤0, then we have the Lagrange function of (4):(11)Ld,λ,μ¯,μ^=Qkd−λTxk+d−μ¯Td+Δke+μ^Td−Δke,where λ,μ¯,μ^∈Rn are Lagrange multipliers, e=1,1,…,1T∈ℜn. Since dk is the solution of (4), we then obtain that(12)∇dLdk,λ,μ¯,μ^=0,λ,μ¯,μ^≥0,xk+dk≥0,dk+Δke≥0,dk−Δke≤0,λTxk+dk=μ¯Tdk+Δke=μ^Tdk−Δke=0.
Observe thatdk=0 and Δk>0 ensure that(13)gμkxk=λ+μ¯−μ^,λ,xk≥0,λTxk=0,μ¯=μ^=0.
Thus,xkTgμkxk=0, i.e., g¯μkxk=0.Lemma 2.
(see [32]). There exists a constant κmdc∈0,1 such that(14)Qk0−Qkdk≥κmdcg¯μkxkming¯μkxk1+Bk,Δk.Lemma 3.
(see [35]). Suppose that A1 and A2 hold. If g¯μkxk≠0 and(15)Δk≤minκmdc1−η2κubh,11+κumb⋅g¯μkxk,we have ρk≥η2, and Δk+1≥Δk.Consequently, we may now obtain that the trust-region radius cannot become arbitrarily small if the iterates stay away from first-order critical points.Lemma 4.
Suppose that A1 and A2 hold. Suppose furthermore that there exists a constantκlpg>0 such that g¯μkxk≥κlpg for all k. Then, there is a constant κlbd>0 such that Δk≥κlbd for all k.Proof.
Assume that iterationk0 is the first such that(16)Δk0≤γ1κlpg⋅minκmdc1−η2κubh,11+κumb.
Then, we have from our assumptiong¯μkxk≥κlpg and (9) that γ1Δk−1≤Δk,∀k, and hence, Δk0−1≤minκmdc1−η2/κubh,1/1+κumb⋅g¯μk0−1xk0−1. It implies that (15) holds and thus Δk0−1≤Δk0. But this contradicts the fact that iteration k0 is the first such that (16) holds, and our initial assumption is therefore impossible.


## 3.2. Convergence to Stationary Points

For convenience of discussion, we shall denoteT=kdk=0 as the set of zero-solution of (4) iterations, denote S=kxk+1≠xk as the set of successful iterations, denote U=kρk<η1,xk+is not accepted byℱk as the set of unsuccessful iterations, and denote P=kρk<η1,xk+is accepted byℱk as the set of iterations which is not accepted by trust-region rule but filter rule (5). Now, we consider the first-order global convergent conclusion of our algorithm in the following three cases: T=+∞, U=+∞, and S=+∞.Theorem 1.
Suppose that A1 and A2 hold and thatT=+∞, then limk∈Tg¯μkxk+μk=0.Proof.
Note that, ifT=+∞, Lemma 1 implies that g¯μkxk=0. Moreover, by the mechanism of updating μk (10), we have μk+1=θμk. Then, we get the first-order global convergence of our Algorithm 1limk∈Tg¯μkxk+μk=0, i.e., Algorithm 1 can be terminated with finite steps.Theorem 2.
Suppose that A1 and A2 hold and thatU=+∞, then limk∈Ug¯μkxk+μk=0.Proof.
Assume, to arrive at a contradiction, that there existε>0 and k0 such that(17)g¯μkxk+μk≥ε,∀k>k0.
SinceU=+∞, there exists a positive integer k1>k0 such that(18)xk=xk1,∀k≥k1.
By the mechanism of updatingμk (10), we can consider two cases.Case 1.
limk⟶∞μk≠0, i.e., there exists a positive integer k2≥k1 such that μk=μk2 for all k≥k2. By Algorithm 1, we obtain that(19)Δk≤γ2k−k2Δk2,μk≤0.1g¯μkxk+1,for all k≥k2. Hence, we can deduce from (18) and (19) that g¯μkxk≥κlpg for all k≥k2, where κlpg=10μk2. Note that γ2∈0,1 in Algorithm 1, so we have limk⟶∞Δk=0. Applying Lemma 4, there is a constant κlbd>0 such that Δk≥κlbd for all k, which contradicts the fact limk⟶∞Δk=0, as stated in (19). Therefore, Case 1 cannot hold.Case 2.
limk⟶∞μk=0. We deduce from (17) that there is a integer k3≥k1 such that g¯μkxk≥0.5ε≥10μk for all k≥k3, i.e., μk≤0.1g¯μkxk=0.1g¯μkxk+1, for all k≥k3. By the mechanism of updating μk, then we have μk=μk3 for all k≥k3, which contradicts limk⟶∞μk=0. Thus, Case 2 cannot hold. Our initial assumption must then be false.Theorem 3.
Suppose that A1 and A2 hold and thatS=+∞, then limk∈Sg¯μkxk+μk=0.Proof.
Assume, to arrive at a contradiction, that there existε>0 and k0 such that(20)g¯μkxk+μk≥ε,∀k>k0.
By the mechanism of updatingμk (10), we can consider two cases.Case 3.
limk⟶∞μk≠0, i.e., there exists a positive integer k1>k0 such that μk=μk1 for all k≥k1. Observe first that (10) implies that μk≤0.1g¯μkxk+1=0.1g¯μk+1xk+1,∀k≥k1. Let κlpg=10μk1, then(21)g¯μkxk≥κlpg,∀k>k1.(i)
P<+∞ (i.e. S\P=+∞). That means there exists a positive integer k2≥k1 such that either k∈S\P or k∈S¯ for all k≥k2. Besides, we can deduce from S=+∞ that ρk≥η1 for all k∈S\P. Then, by (9), we have that for all k>k2,(22)fμk2xk2−fμkxk=∑j=k2,j∈S\Pk−1fμjxj−fμj+1xj+1+∑j=k2,j∈S¯k−1fμjxj−fμj+1xj+1=∑j=k2,j∈S\Pk−1fμjxj−fμj+1xj+1≥∑j=k2,j∈S/Pk−1η1Qj0−Qjdj≥η1κmdcκlpg⋅∑j=k2,j∈S/Pk−1minκlpg1+κumb,Δj.Hence, we deduce from the boundedness offμkxk that limk>k2Δk=0. But it derives a contradiction from (21) and Lemma 3.(ii)
P=+∞. Assumptions A1 and A2 show that g¯μkxk+1 is a bounded subsequence. Then, there exists an infinite subsequence kiki>k1⊆P such that(23)limi⟶∞g¯μkixki+1=g¯∞≥κlpg.
By definition ofki∈P, xki+1 is acceptable for the current filter ℱki. This implies, by (21) and filter mechanism (5), that, for each xk∈ℱki, there exists an index jk∈ℐ such that(24)g¯μki,jkxki+1≤g¯μk−1,jkxk−γgg¯μk−1xk=g¯μk−1,jkxk−γgg¯μkxk≤g¯μk−1,jkxk−γgκlpg.
Ifxki−1+1∉ℱki, we obtain from (6) and (7) that there exists xks∈ℱki such that g¯μks−1,jxks≤g¯μki−1,jxki−1+1,∀j∈ℐ. Thus, (24) ensures that there exists an index jks∈ℐ such that(25)g¯μki,jksxki+1−g¯μki−1,jksxki−1+1≤−γgκlpg.
Ifxki−1+1∈ℱki, (23) implies that there exists an index jki−1+1∈ℐ such that(26)g¯μki,jki−1+1xki+1−g¯μki−1,jki−1+1xki−1+1≤−γgκlpg.
Since the finite possibility ofjki−1+1, let jki−1+1=j0. Then, the left-hand side of inequality (25) and (26) tends to zero when i tends to infinity because of (23), which is impossible. In a word, Case 3 does not happen.Case 4.
limk⟶∞μk=0. The infiniteness of S and (10) implies that there exists a infinite index K⊆S such that limk∈Kg¯μkxk+1=limk∈Kg¯μkxk+=0. We then obtain that limk∈Kg¯μkxk++μk=0, which contradicts (20), and therefore, Case 4 cannot hold, yielding the desired result.


## 4. Numerical Experiments

Now, we give some numerical results for the following 10 complementarity test problems in Table1. The values for the constants used in our tests are μ0=10−5, γg=10−3, γ1=0.25, γ3=2, η1=0.25, η2=0.95, Δ0=2, θ=0.1, Δmax=103, ε=10−5, ℱ0=105,…,105T. The iteration is terminated once fμkxk≤10−5.Table 1
Numerical result of test problems.
ExampleStart pointx0niterResf1.10,0,0,0T474.43e−121.20,0,0,0T497.98e−1523,2,1,2,3T521.43e−133.12,…,2T10381.66e−113.22,…,2T10351.05e−144.10.5,…,0.5T10356.60e−144.20,…,0T50055.78e−104.30,…,0T8091.92e−084.41,…,1T10338.00e−165—100161.65e−085—103721.63e−1061,0,1,0,…T10054.03e−1561,0,1,0,…T10366.23e−1470,…,0T100141.49e−1170,…,0T103251.94e−108−1.2,1,−1.2,1,…T10013.97e−248−1.2,1,−1.2,1,…T10339.25e−159—100153.61e−129—103153.04e−1110−1,…,−1T10075.53e−1010−1,…,−1T10374.35e−19In addition, we use the nonlinear equations to carry out large-scale data experiments. Letpx=0 be a (large-scale) differentiable system of nonlinear equations and let x∗∈Rn be defined by x∗=1,0,1,0,…T. For all i∈ℐ, set(27)Fix=pix−pix∗,ifiodd or,i>r,pix−pix∗+1,otherwise,where r≥0 is a given integer. In this way, x∗ is a solution of the nonlinear complementarity (but not necessarily its unique solution). As done in [36], we used the collection of 6 large-scale problems (Examples 5–10) form Lukšan [37]. Some numerical results for these test problems are presented in Table 1.Example 1.
(Kojima–Shindo nonlinear complementarity test problem)(i)
Degenerate example [7, 10, 11, 27, 38, 39]:(28)Fx=3x12+2x1x2+2x22+x3+3x4−62x12+x1+x22+10x3+2x4−23x12+x1x2+2x22+2x3+9x4−9x12+3x22+2x3+3x4−3.(ii)
Nondegenerate example [10, 38]:(29)Fx=3x12+2x1x2+2x22+x3+3x4−62x12+x1+x22+3x3+2x4−23x12+x1x2+2x22+2x3+3x4−1x12+3x22+2x3+3x4−3.
Example1 (i) has a degenerate solution 6/2,0,0,1/2T and a nondegenerate solution 1,0,3,0T. Example 1 (ii) has only one solution 6/2,0,0,1/2T which is nondegenerate.Example 2.
(Kanzow nonlinear complementarity test problem [10, 40]). We choose F=F1,…,FnT:ℜn⟼ℜn with(30)Fix=2xi−i+2⋅exp∑i=15xi−i+22,1≤i≤5.
Example2 has only one solution0,0,1,2,3T.Example 3.
(see [41]). We choose F=F1,…,FnT:ℜn⟼ℜn with(31)Fix=−xi−1+2xi−xi+1+13xi3−bi,1≤i≤n,where n is a positive integer and x0=xn+1=0. We choose the constant b=−11,…,−1i,…,−1nT and b=−111,…,−1ii,…,−1nnT, respectively.Example 4.
We consider the following four linear complementarity problem [7, 11, 27, 39, 42–44]: Fx=Mix+q, i=1,2,3,4, where q=−1,…,−1T, and M1,M2,M3,M4 are given as follows, respectively:(32)4−214⋱⋱⋱−214,4−1−14⋱⋱⋱−1−14,1/n2/n⋱n/n,122…212…21…2⋱⋮1.Example 5.
Countercurrent reader problem [37]:(33)pkx=α−1−αxk+2−xk1+4xk+1,ifk=1,−2−αxk+2−xk1+4xk−1,ifk=2,αxk−2−1−αxk+2−xk1+4xk+1,ifk∈2,n−1and modk,2=1,αxk−2−2−αxk+2−xk1+4xk−1,ifk∈2,n−1and modk,2=1,αxk−2−xk1+4xk+1,ifk=n−1,αxk−2−2−αxk1+4xk−1,ifk=n,where α=1/2. We choose the following initial point x¯:(34)x¯k=0.1,if modk,8=1,0.2,if modk,8=2and modk,8=0,0.3,if modk,8=3and modk,8=7,0.4,if modk,8=4and modk,8=6,0.5,if modk,8=5.Example 6.
Extended Powell badly scaled function [37]:(35)pkx=10000xkxk+1,if modk,2=1,e−xk−1+e−xk−1.0001,if modk,2=0.Example 7.
Trigonometric exponential system [37]:(36)pkx=3xk3+2xk+1−5+sinxk−xk+1sinxk+xk+1,ifk=1,3xk3+2xk+1−5+sinxk−xk+1sinxk+xk+1,+4xk−xk−1exk−1−xk,ifk∈1,n,4xk−xk−1exk−1−xk,ifk=n.Example 8.
Extended Rosenbrock function [37]:(37)pkx=10xk+1−xk2,if modk,2=1,1−xk−1,if modk,2=0.Example 9.
Extended Cragg and Levy Function [37].(38)pk=exk−xk+12,ifmodk,4=1,10xk−xk+13,ifmodk,4=2,tan2xk−xk+1,ifmodk,4=3,xk−1,ifmodk,4=0.
We choose the following initial pointx¯ as x¯k=1,ifmodk,4=1,2,otherwise.Example 10.
Broyden tridiagonal problem [37]:(39)pkx=3−2xkxk−2xk+1+1,ifk=1,3−2xkxk−xk−1−2xk+1+1,ifk∈1,n,3−2xkxk−xk−1+1,ifk=n.
The computational results are listed in Table1, in which iter denotes the number of iterations, and Resf stands for the computing accuracy, i.e., Resf=fμkxk. The numerical results show that Algorithm 1 is robust and efficient. The number of iterations and computing accuracy for most problems are satisfactory.


## 5. Conclusions

In this work, we have proposed multidimensional filter techniques for solving nonlinear complementarity problem (1) and have shown this algorithm to be globally convergent under a weaker assumption because assumptions A1 and A2 imply that the matrix sequence Bk in subproblem (4) is uniformly bounded. Moreover, we are surprised to find that Bk+1=∇xΦμkxk∇xΦμkxkT can be computed easily instead of updating Bk+1 by utilizing some methods (e.g., BFGS). The new algorithm differs from other traditional filter methods [7, 27, 39] for nonlinear complementarity problems; subproblem (4) is consistent throughout, so we do not need any extra restoration procedure which means higher numerical expenditure. Besides, we used the gradient-projection technique which makes sure that the optimality condition of constrained optimization problem (2) is equivalent to the fact that the projected gradient is zero, so the multidimensional filter techniques based on unconstrained optimization problem is suitable for problem (2). Finally, in this context, we provide a reasonable and effective way to balance the projected gradient g¯μkxk and the smooth parameter μk and then ensure that liminfk⟶+∞g¯μkxk+μk=0. The results of numerical experiments show its efficiency.



---

*Source: 2539196-2020-06-19.xml*