# A Smoothing Newton Method with a Mixed Line Search for Monotone Weighted Complementarity Problems

Authors: Xiaoqin Jiang; He Huang
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In this paper, we present a smoothing Newton method for solving the monotone weighted complementarity problem (WCP). In each iteration of our method, the iterative direction is achieved by solving a system of linear equations and the iterative step length is achieved by adopting a line search. A feature of the line search criteria used in this paper is that monotone and nonmonotone line search are mixed used. The proposed method is new even when the WCP reduces to the standard complementarity problem. Particularly, the proposed method is proved to possess the global convergence under a weak assumption. The preliminary experimental results show the effectiveness and robustness of the proposed method for solving the concerned WCP.


---

## Body

## 1. Introduction

The weighted linear complementarity problem, introduced by Potra [1], is to find a vector s,t,u∈ℜn×ℜn×ℜm such that(1)s,t≥0,Ps+Qt+Ru=q,St=w,where P∈ℜn+m×n, Q∈ℜn+m×n, and R∈ℜn+m×m are the given matrices, q∈ℜn+m is a given vector,(2)S≔s1s2⋱snis ann×nreal matrix,and w∈ℜn is a given nonnegative weighted vector. We denote this problem by the WMLCP. When w=0, WMLCP (1) reduces to a mixed linear complementarity problem which has extensively been studied in the literature [2].In [1], Potra showed that the problem of Fisher market equilibrium may be modeled as a WMLCP, and particularly, it could be solved more efficiently than a corresponding complementarity problem model; Anstreicher [3] proved that the problem of the weighted centering may also be reformulated as a WMLCP and proposed an interior point method to solve it. Since then, this kind of problem has been studied a lot. For example, Potra [4] studied some theories and proposed an interior point method to solve the WMLCP with the involved matrix being sufficient; Zhang [5] presented a smoothing Newton method to solve WMLCPs; Tang [6] proposed a variant nonmonotone smoothing algorithm to solve WMLCPs; Chi et al. [7] investigated the existence and uniqueness of the solution for a class of weighted horizontal linear complementarity problems.Recall that a standard finite-dimensional complementarity problem (denoted by the CP) is to find a vector pairs,t∈ℜ2n such that(3)s≥0,t=fs≥0,s⊤t=0,where f:ℜn⟶ℜn is a given mapping and the subscript ⊤ denotes transpose. Problem (3) has many applications in fields such as engineering and economics (see, for example, [8]), and it has received great attention [2, 9–11]. Recently, a subclass of CPs, tensor complementarity problems, was also studied extensively (see, for example, survey papers [12–14]). Two extensions of tensor complementarity problems and an application to the problem of traffic equilibrium problems were given in [15].Inspired by the above papers, we investigate an extension of the CP, called the weighted complementarity problem (denoted by WCP), which is to find a vector pairs,t∈ℜ2n such that(4)s≥0,t=fs≥0,St=w,where f:ℜn⟶ℜn is a given mapping. Obviously, when w=0, WCP (4) becomes a CP. When f is a linear mapping, say fs=Ns+p with N being an n×n real matrix and p∈ℜn, the corresponding WCP is named as a weighted linear complementarity problem (WLCP); otherwise, it is named as a weighted nonlinear complementarity problem. Recall that a mapping f is called to be monotone if and only if s−t⊤fs−ft≥0 holds for all s,t∈ℜn. If f is a monotone mapping, then the corresponding WCP (4) is called a monotone WCP. We will investigate the numerical method for solving the WCP.It is well known that CP (3) may be reformulated as a system of parameterized smoothing equations in terms of some complementarity function [16–18]. Thus, in order to achieve a solution of CP (3), one may use some Newton-type method to iteratively solve the obtained system of equations and make the smoothing parameter tend to zero. This is the so-called smoothing Newton method. This class of methods has been successfully applied to solving lots of optimization and related problems, including linear complementarity problems [19–24], linear programs [25], nonlinear complementarity problems [26–30], variational inequalities [27, 31], semidefinite complementarity problems [32–37], system of inequalities [19, 34], symmetric cone complementarity problems [35, 36], mathematical programs with complementarity constraints [38, 39], and absolute value equations [40]. In order to achieve the global convergence, most of the known smoothing Newton methods require the assumption that the solution set of the concerned problem is nonempty and compact. In [29], the author proposed a smoothing Newton method for solving CP (3) with a monotone mapping and showed that the smoothing Newton method is globally convergent when the problem has at least a solution. This assumption is weaker than the ones required in the global convergence of smoothing Newton methods (see, for example, [41]). Moreover, since the nonmonotone line search technique can improve the likelihood of finding a global optimal solution and convergence speed in cases where the involving function is highly nonconvex and has a valley in a small neighbourhood of some point, the nonmonotone line search criterion has been used in some smoothing Newton methods for solving CPs (see, for example, [42–45]). More nonmonotone techniques can be found in [46–50]. In addition, some related Newton-type methods can be found in [51–55].Inspired by the above methods, we investigate the nonmonotone smoothing Newton method for solving WCP (4). We use the following assumption.Assumption 1.
f is a continuously differentiable monotone mapping and WCP (4) has at least a solution.
In terms of the algorithmic framework of the one studied in [29] for CP (3) and some nonmonotone line search criteria used in [42, 43], by using a symmetric perturbed smoothing function, we propose a smoothing Newton method with a mixed line search criterion to solve WCP (4), where, in each iteration, a system of linear equations is solved to find the iterative direction and a line search is performed to achieve the iterative step length. Particularly, we show that the proposed smoothing Newton method is globally convergent if Assumption 1 is satisfied. This assumption is weaker than most of them used in the analysis on the global convergence of smoothing Newton methods for CP (3). When WCP (4) reduces to CP (3), our proof of main results given in this article is simpler than that of the corresponding ones in [29].
The article is organized as follows. In Section2, we describe a reformulation of WCP (4) and propose a smoothing Newton method for solving WCP (4). In Section 3, we prove the global convergence of the proposed smoothing Newton method. The preliminary numerical experiments and conclusions are given in Sections 4 and 5, respectively.
In this article, we useℜ+n to represent the nonnegative orthant in ℜn and ℜ++n to represent the positive orthant in ℜn. Denote(5)Θ≔1,2,…,n,Ω≔0,1,2,….
For anys,t∈ℜn, si means the ith component of s and s,t stands for s⊤,t⊤⊤ simplicity. For any ν,s,t,νk,sk,tk∈ℜ+×ℜ2n, we denote r≔ν,s,t and rk≔νk,sk,tk. Moreover, the solution set of WCP (4) is denoted by SOLwf.


## 2. A Smoothing Newton Method

For any givenγ∈ℜ, we define a mapping ϕγ:ℜ3⟶ℜ by(6)ϕγν,α,β≔1+να+β−1−ν2α−β2+4γ+4ν,for any ν,α,β∈ℜ+×ℜ×ℜ. In fact, when γ=0, the above mapping (i.e., ϕ0⋅,⋅,⋅) is just the symmetric perturbed smoothing function introduced in [28].Lemma 1.
Givenν,α,β,γ,δ∈ℜ++×ℜ×ℜ×ℜ+×ℜ. Then, we have the following two results:(a)
ϕγ0,α,β=0 holds if and only if(7)α≥0,β≥0,αβ=γ.(b)
ϕγν,α,β=δ holds if and only if(8)α+νβ−δ2>0,να+β−δ2>0,α+νβ−δ2να+β−δ2=ν+γ.Proof.
These two results can be easily proved by using the definition ofϕγ⋅. We omit the proof here.
Furthermore, for any given weighted vectorw∈ℜ+n, we define a mapping for the WCP, Gw:ℜ1+2n⟶ℜ1+2n, by(9)Gwr≔Gwν,s,t≔νt−fsΦwr,for any r≔ν,s,t∈ℜ×ℜn×ℜn, where(10)Φwr≔ϕw1ν,s1,t1ϕw2ν,s2,t2⋮ϕwnν,sn,tn∈ℜn.
Then, by using (9) and Lemma 1 (a), it follows that(11)Gwr=0I^12=0,s,t∈SOLwf.
The following results can be easily obtained.Proposition 1.
Suppose thatf is a continuously differentiable monotone mapping. Then,(a)
For eachr∈ℜ++×ℜn×ℜn, the mapping Gw is continuously differentiable at r, and(12)Gw′r=1000−f′sIΦwrν′Φwrs′Φwrt′,whereI∈ℜn×n is the identity matrix, v≔Φwrν′∈ℜn, U≔Φwrs′∈ℜn×n, and V≔Φwrt′∈ℜn×n with(13)vi=si+ti−2−1−νsi−ti21−ν2si−ti2+4wi+4ν,∀i∈Θ,Uii=1+ν−1−ν2si−ti1−ν2si−ti2+4wi+4ν,∀i∈Θ,Vii=1+ν+1−ν2si−ti1−ν2si−ti2+4wi+4ν,∀i∈Θ,andUij=0 and Vij=0 for all i,j∈Θ with i≠j.(b)
Gw′r is nonsingular at each point r∈ℜ++×ℜn×ℜn.Therefore, by (11) and the continuity of the mapping Gw, we may find a solution of WCP (4) in the following way: use some Newton-type method to iteratively solve Gwr=0 and make Gwr↓0.Algorithm 1.
(a smoothing Newton method).Step 0. Given w∈ℜ+n. Take δ,σ∈0,1, ν0>0, s0,t0∈ℜ2n, and a positive integer M. Set r0≔ν0,s0,t0. Take ρ>1 satisfying Gwr0≤ρν0. Denote e0≔1,0,…,0∈ℜ1+2n. Set C0≔Gwr0 and Q0≔1. Choose η0∈0,1 and a sufficiently small positive number ϵ. Set m0≔1 and k≔0.Step 1. If Gwrk=0, stop.Step 2. Let drk≔dνk,dsk,dtk∈ℜ×ℜn×ℜn solve(14)Gwrk+Gw′rkdrk=1ρCke0,whereGw′ is defined by (4).Step 3. Let γk be the maximum in 1,δ,δ2,…, satisfying(15)Gwrk+γkdrk≤1−σ1−1ργkCk.Step 4. Set mk+1≔mink+1,M. If ∑i=0mkηk−iCk−i−Ck>0, then we set ηk+1≔0; otherwise, we choose ηk+1∈0,1. Set(16)Qk+1≔1+ηk+1∑i=0mkηk−i,Ck+1≔ηk+1∑i=0mkηk−iCk−i+Gwrk+γkdrkQk+1.Step 5. Let rk+1≔rk+γkdrk and k≔k+1. Go to Step 1.
In Algorithm1, we set a selection condition: ∑i=0mkηk−iCk−i−Ck>0. If it is satisfied for some k∈Ω, then ηk+1=0; hence, by (16), we have that Ck+1=Gwrk+1. In this case, the line search in the k+1th iteration is a monotone line search. Moreover, if the above selection condition is not satisfied for some k∈Ω, then the line search in the k+1th iteration is a nonmonotone line search. Thus, the line search criterion designed in Algorithm 1 is a mixed line search that switches between monotone and nonmonotone line search.
Algorithm1is new even in the case of the weighted vector involved being the zero vector (in this case, the WCP reduces to the CP). Moreover, Algorithm 1 is simpler than many smoothing Newton methods for solving the CP in the sense that it requires only to solve a system of linear equations and to do a line search in each iteration of the algorithm. In fact, a similar algorithmic framework (without the nonmonotone line search) was proposed in [29] for solving (3).
In the following, we show that Algorithm1 is well defined.Lemma 2.
Suppose thatf is a continuously differentiable monotone mapping and the sequence rk=νk,sk,tk is generated by Algorithm 1. Then, we have the following results:(a)
Ck+1≤Ck for all k∈Ω(b)
Ck≤ρνk for all k∈Ω(c)
0<νk+1≤νk for all k∈Ω(d)
Gwrk≤Ck for all k∈Ω(e)
Algorithm1 is well definedProof.
(a) For anyk∈Ω, if ∑i=0mkηk−iCk−i−Ck≤0, then we have that(17)Ck+1≤ηk+1∑i=0mkηk−iCk+Gwrk+1Qk+1≤ηk+1∑i=0mkηk−iCk+1−σ1−1/ργkCkQk+1=Ck−σ1−1/ργkQk+1Ck≤Ck,where the first inequality holds due to (16) and the second inequality holds due to (15); otherwise, we have that ηk+1=0, and hence, by (16) and (15), we can obtain that(18)Ck+1=Gwrk+1≤1−σ1−1ργkCk≤Ck.
Thus,Ck+1≤Ck for all k∈Ω.
(b) From Step 0 in Algorithm1, it is easy to see that C0=Gwr0≤ρν0. Suppose that Cl≤ρνl for some l∈Ω, then(19)Cl+1−ρνl+1=Cl+1−ρ1−γlνl+1ργlCl≤Cl+1−ρ1−γl1ρCl+1ργlCl=Cl+1−Cl≤0,where the first equality follows from the first equation in (14), the first inequality from the inductive assumption, and the last inequality from the above (a). Thus, Ck≤ρνk for all k∈Ω.
(c) By the first equation in (14), we have νk+1=1−γkνk+γkC0/ρ>0 for all k∈Ω. Moreover, for any k∈Ω, we have that(20)νk+1=1−γkνk+1ργkCk≤1−γkνk+1ργkρνk=νk,where the first equality follows from the first equation in (14) and the inequality in (b). Thus, 0<νk+1≤νk for all k∈Ω.
(d) By (16), we have that for any k∈Ω,(21)Gwrk=QkCk−ηk∑i=1mk−1ηk−iCk−i≤Qk−ηk∑i=1mk−1ηk−iCk=Ck,where the inequality follows from the above (a). Thus, Gwrk≤Ck for all k∈Ω.
(e) On the one hand, sinceνk≥0 for all k∈Ω, it follows from Proposition 1 that Gw′rk (see (12)) is invertible, and hence, equation (14) is solvable for all k∈Ω. On the other hand, for any k∈Ω, if we let Rwkγ≔Gwrk+γdrk−Gwrk−γGw′rkdrk, then, by (14), we have that(22)Gwrk+γdrk=Rwkγ+Gwrk+γGw′rkdrk≤Rwkγ+1−γGwrk+γ1ρCk≤Rwkγ+1−γCk+γ1ρCk≤Rwkγ+1−γ1−1ρCk,where the second inequality holds due to the above (d). Since the function G is continuously differentiable at any r∈ℜ++×ℜn×ℜn, it follows from (a) that Rwkγ=oγ for all k∈Ω. This means that the line search (15) is well defined. Thus, Algorithm 1 is well defined.


## 3. Global Convergence of Algorithm1

We now show that Algorithm1 is globally convergent under Assumption 1.Theorem 1.
Let Assumption1 be satisfied. Then, the following results hold:(a)
The sequencerk=νk,sk,tk generated by Algorithm 1 is bounded(b)
Every accumulation point ofsk,tk solves WCP (4)Proof.
(a) We verify the boundedness ofrk by the following three parts.
Part 1. We verify the boundedness of νk. Such a result holds directly from Lemma 2 (c).
Part 2. We verify the boundedness of sk. Suppose, on the contrary, that sk is unbounded. For our purposes, we need to construct sequences xk and yk by(23)xk≔1νktk−fsk,∀k∈Ω,(24)yk≔1νkΦwrk+νksk,∀k∈Ω.
For anyk∈Ω, by Lemma 2 (b), we have Ck≤ρνk, and by Lemma 2 (d), we have Gwrk≤Ck. Thus, Gwrk≤ρνk for all k∈Ω. This, together with (23) and (24) as well as the definition of the mapping Gw in (9), implies that(25)xk≤ρ2−1,yk≤ρ2−1,∀k∈Ω.
These mean that both sequencesxk and yk are uniformly bounded.
Furthermore, we construct sequencess^k and t^k by(26)s^k≔sk+νktk−12νkyk;t^k≔νksk+tk−12νkyk,∀k∈Ω.
Then, by using Lemma1(b) and the definition of yk in (24), we have(27)s^ik≥0,t^ik≥0,s^ikt^ik=νk+wi,∀i∈Θ,∀k∈Ω,which leads to(28)s^k⊤t^k=nνk+∑i=1nwi.
Moreover, by Assumption1 it follows that SOLwf≠∅, and hence, there exists s∗,t∗⊆ℜn×ℜn satisfying(29)si∗≥0,ti∗=fis∗≥0,si∗ti∗=wi,∀i∈Θ.
Thus, by using (28) and inequalities given in (27) and (29), we further obtain that(30)nνk=s^k⊤t^k−∑i=1nwi=s^k⊤t^k−s∗⊤t∗≥s^k⊤t^k−s∗⊤t^k−s^k⊤t∗−s∗⊤t∗=s^k−s∗⊤t^k−t∗,∀k∈Ω.
Substituting (26) into (30), we obtain that(31)nνk≥sk−s∗⊤tk−t∗+sk−s∗⊤νksk−12νkyk+νktk−12νkyk⊤tk−t∗+νktk−12νkyk⊤νksk−12νkyk,holds for any k∈Ω. In what follows, we investigate the right-hand side of (31). Since Assumption 1 holds, we have that the mapping f is monotone, and hence,(32)sk−s∗⊤fsk−fs∗≥0,sk−12yk⊤fsk−f12yk≥0,∀k∈Ω.
Hence, by using (23) and (24), we obtain that for any k∈Ω,(33)sk−s∗⊤tk−t∗=sk−s∗⊤fsk−fs∗+sk−s∗⊤νkxk≥νksk−s∗⊤xk,where the first equality holds due to (23) and (29) and(34)νktk−12νkyk⊤νksk−12νkyk=νk2sk−12yk⊤fsk−f12yk+f12yk−12yk+νkxk≥νk2sk−12yk⊤f12yk−12yk+νkxk.
Denote(35)gsk≔tk−t∗2+t∗−12νkyk⊤tk−t∗,∀k∈Ω.
Then, it holds that eithergsk is bounded or gsk⟶+∞ as k⟶∞. Moreover, we have that(36)νktk−12νkyk⊤tk−t∗=νkgsk,holds for any k∈Ω. Thus, by combining (31), (33), (34), and (36), we obtain that(37)n≥sk−s∗⊤xk+sk−s∗⊤sk−12yk+νksk−12yk⊤f12yk−12yk+νkxk+gsk,∀k∈Ω.
By the assumption thatsk is unbounded, it holds that the right-hand side of (37) tends to +∞ as k⟶+∞, which is a contradiction to the fact that the left-hand side of (37) is a constant. Therefore, the assumption that sk is unbounded does not hold, i.e., sk is bounded.
Part 3. We verify the boundedness of tk. On the one hand, we have that fsk is bounded since sk is bounded and the mapping f is continuous. On the other hand, by (23), we have that tk=νkxk+fsk holds for all k∈Ω. Thus, by the boundedness of sequences νk,xk, and fsk, we can obtain that tk is bounded. Therefore, by combining Part 1 with Part 2 and Part 3, we obtain that rk is bounded.
(b) We verify that every accumulation point ofsk,tk solves WCP (3). From Lemma 2 (a)–(d), we have that for all k∈Ω,(38)0≤Gwrk+1≤Ck+1≤Ck≤ρνk≤ρν0<∞.
Thus, by using the boundedness of the iterative sequence in (a) and taking the subsequence if necessary, we can assume thatr∗≔ν∗,s∗,t∗ is the limiting point of the sequence rk and denote that C∗≔limitk⟶∞Ck and Gw∗≔limitk⟶∞Gwrk. Since the mapping Gw is continuous, it is obvious that Gw∗=Gwr∗. Moreover, it is not difficult to verify from (16) that C∗=Gw∗. If Gw∗=0, then we can derive the desired result by a simple continuity discussion.
In the following, assumeGw∗≠0. Then, C∗=Gw∗>0 and ν∗>0. We consider the following two cases.Case 1.
Suppose thatγk≥γ^>0 for all k∈Ω, where γ^ is an s constant. Then, by (15), we have that for any k∈Ω,(39)Gwrk+γkdrk≤1−σ1−1ργkCk≤1−σ1−1ργ^Ck.
Letk⟶∞, so we can obtain that 1≤1−σ1−1/ργ^, which leads to a contradiction.Case 2.
Suppose thatlimitk⟶∞γk=0. Then, for any sufficiently large k∈Ω, the stepsize γ¯k≔γk/δ does not satisfy the line search criteria (15), i.e.,(40)Gwrk+γ¯kdrk>1−σ1−1ργ¯kCk≥1−σ1−1ργ¯kGwrk,where the second inequality holds from Lemma 2 (d). Thus, for any sufficiently large k∈Ω,(41)Gwrk+γ¯kdrk−Gwrkγ¯k>−σ1−1ρGwrk.
Sinceν∗>0, it is easy to show from (14) that the sequence drk is convergent. Denote dr∗≔limitk⟶∞drk. Let k⟶∞, and it follows from (41) that(42)−σ1−1ρGw∗≤1Gw∗Gwr∗,Gw′r∗dr∗=−Gw∗+C∗ρGw∗Gwr∗,e0≤−Gw∗+C∗ρ,which leads to −σ1−1/ρ≤−1+1/ρ. This is a contradiction.
Therefore, by combining Case1 with Case 2, we obtain that every accumulation point of sk,tk solves WCP (4).
Combining (a) with (b), we complete the proof of the theorem.
The basic idea in showing the boundedness of the iterative sequence (i.e., the proof of Theorem1 (a)) is similar to the ones in [29], Lemma 3.4 and Theorem 3.1. However, the proof of Theorem 1 is more simpler than those of Lemma 3.4 and Theorem 3.1 in [29].


## 4. Numerical Experiments

In this section, we implement Algorithm1 for solving weighted linear complementarity problems. All experiments were performed on a Thinkpad notebook computer with 2.5 GHz CPU and 8 GB memory. The codes are run in MATLAB R2016a under Win 10. Our experiments are divided into two parts.Part 1. In this part, we implement Algorithm 1 for solving WCP (4). Specifically, we test the following problem:Problem 1.
Consider the following WLCP:(43)s≥0,t=Ns+p,St=w,which is randomly generated in the following way: for any given positive integer n, take N≔A⊤A with A≔0.1∗rand100,n and s∗≔randn,1. Let Λ≔randin,0.5∗n,1, and take p in the following way: pi≔−Ns∗i for all i∈Λ and pi≔rand1,1 for all i∈1,2,…,n\Λ. Let w≔S∗t∗.
Obviously, this problem is a monotone WLCP, which is solvable. In this problem,wi=0 for all i∈Λ. In the experiments, we take(44)M≔5,δ≔0.5,σ≔0.001,ν0≔0.01.
Supposen is taken as those listed in Table 1. Take the starting point s0≔−0.5∗randn,1. Set t0≔Ns0+p and r0≔ν0,s0,t0. Take ρ≔Gwr0/ν0. We take η0≔0.8, and for any k∈Ω, if the condition ∑i=0mkηk−iCk−i−Ck>0 is satisfied, we set ηk+1≔0; otherwise, we set ηk+1≔min0.01,0.5ηk. We terminate Algorithm 1 when Gwrk≤10−6.
For every choice ofn, the corresponding problem is tested five times and the experimental results are reported in Table 1, where It denotes the number of iterations, Itm denotes the number of iterations when the monotone line search is used (i.e., the case of ηk=0), NF denotes the number of evaluations for the mapping Gwrk, Val denotes the value of Gwrk, and Cpu denotes the CPU time in seconds, respectively.
From Table1, we have the following observations:(i)
From columns “It” and “Itm” in Table1, we see that the monotone line search and the nonmonotone line search both work in Algorithm 1. So, this algorithm is really an algorithm with a mixed line search.(ii)
It can be seen that Algorithm1 is effective for solving WLCPs since each tested problem was successfully solved in few iterations and short CPU time.(iii)
Algorithm1 is robust since different tested problems having the same size were successfully solved with small differences among the numbers of iterations.
Part 2. In fact, Algorithm 1 can be applied to solve WMLCP (1). For this purpose, instead of the mapping Gw⋅ defined by (9), we define a mapping for the WMLCP, Gw:ℜ1+2n+m⟶ℜ1+2n+m, by(45)Gwr≔Gwν,s,t,u≔νPs+Qt+Ru−qΦwr,for any r≔ν,s,t,u∈ℜ×ℜn×ℜn×ℜm, where the mapping Φw is the same as the one defined in Section 2 and Gw′r is used to denote the Jacobian matrix of Gw⋅ at any r=ν,s,t,u∈ℜ×ℜn×ℜn×ℜm.
In this part, we implement Algorithm1 for solving this type of weighted complementarity problem and compare it with two algorithms studied in the literature. The test problem is constructed in a similar way as those in [5, 6]. Specifically, we test the following problem.Table 1
The numerical results of Problem1.
nItItmNFValCpu100075139.07e − 071.94e + 0085201.00e − 073.08e + 0075151.17e − 072.09e + 006584.23e − 071.69e + 0085133.55e − 072.22e + 003000105295.69e − 073.56e + 0198222.75e − 093.30e + 0195247.07e − 073.28e + 01105268.09e − 083.60e + 01115284.99e − 074.57e + 015000109261.12e − 071.50e + 02105261.21e − 071.50e + 02115271.11e − 081.63e + 02105271.49e − 071.66e + 02105259.83e − 08158Problem 2.
Consider WMLCP (1), where matrices P, Q, and R and vector q are generated as follows:(46)P=AM,Q=0mn−In,R=0mm−A⊤,q=b−f,where A≔Im−B∈ℜm×n with B≔0.05∗randm,n−m and Im being an m×m identity matrix, M≔diagrandn,1, 0mn is an m×n matrix with all entries being zero, b≔As∗ with s∗≔0.5∗randn,1, and f≔0.5∗randn,1. Moreover, w≔S∗t∗ with t∗≔M∗s∗+f.
In order to generate a strictly feasible starting point, we first takestemp=sI;sB with sB≔0.1∗randn−m,1 and sI≔B∗sB, and then, we set the starting point by(47)s0≔0.5∗stemp+s∗,t0≔M∗s0+f,y0≔zerosm,1.
We implement our algorithm (i.e., Algorithm1), Algorithm 1 in [5], and Algorithm 1 in [1] for solving Problem 2, respectively. For our algorithm, all parameters are selected as the same as those in experiments of Part 1; and for Algorithm 1 in [5], all parameters are selected as the same as those in experiments in [5]. Denote(48)Res=Ps+Qt+Ru∞,Gap=w−Sx∞,normG=Gwrk.
For the first two algorithms, the termination criterion ismaxRes,Gap,normG≤10−6; while for the last algorithm, the termination criterion is maxRes,Gap≤10−6.
In the experiments of each algorithm, for every choice ofn and m, the corresponding problem is tested five times. The experimental results are reported in Table 2, where It and Cpu denote the number of iterations and the CPU time in seconds, respectively, and Val denotes maxRes,Gap,normG for the first two algorithms and maxRes,Gap for the last algorithm.
From the numerical results in Table2, it is easy to see that our algorithm is comparable to Algorithm 1 in [5], and these two algorithms are more efficient than Algorithm 1 in [1].Table 2
The numerical results of Problem2.
mnAlgorithm1Algorithm 1 in [5]Algorithm 1 in [1]It/Cpu/ValIt/Cpu/ValIt/Cpu/Val100015008/5.41e + 00/5.30e − 078/4.56e + 00/7.04e − 0719/1.85e + 01/1.64e − 079/5.64e + 00/5.32e − 089/4.78e + 00/7.03e − 0920/2.00e + 01/1.25e − 078/4.58e + 00/7.84e − 078/4.66e + 00/2.68e − 0815/1.41e + 01/1.10e − 078/3.84e + 00/6.81e − 088/4.67e + 00/6.36e − 1018/1.75e + 01/2.19e − 078/4.22e + 00/2.96e − 089/4.89e + 00/8.51e − 0917/18/5.41e − 07150020009/1.19e + 01/6.63e − 089/1.13e + 01/3.42e − 1021/5.45e + 01/2.53e − 0710/1.35e + 01/2.51e − 0712/1.60e + 01/6.32e − 0923/5.53e + 01/5.90e − 078/1.07e + 01/1.22e − 079/1.23e + 01/1.61e − 0822/5.48e + 01/8.99e − 0710/1.31e + 01/2.76e − 0810/1.26e + 01/4.22e − 0922/5.32e + 01/2.85e − 079/1.23e + 01/6.89e − 0810/1.28e + 01/7.38e − 0820/4.80e + 01/9.96e − 072500300010/5.18e + 01/1.65e − 0812/5.68e + 01/5.01e − 0733/2.92e + 02/8.33e − 078/4.13e + 01/7.81e − 0710/4.96e + 01/1.50e − 1026/2.34e + 02/2.16e − 0710/4.80e + 01/1.03e − 0912/5.99e + 01/3.24e − 0839/3.63e + 02/6.98e − 079/4.29e + 01/1.82e − 0812/5.68e + 01/1.78e − 0735/3.11e + 02/1.07e − 079/4.53e + 01/7.03e − 0710/4.86e + 01/9.47e − 0830/2.71e + 02/2.00e − 07


## 5. Conclusions

We proposed a smoothing Newton method with a mixed line search for solving monotone WCPs and showed the global convergence of the method under a weak assumption. The preliminary experimental results demonstrate the effectiveness and robustness of the method for solving the monotone WCP. We believe that many other smoothing Newton methods can also be modified to solve the WCP. Two future issues which have to be investigated are the theoretical properties of WCPs and solution methods for large-scale WCPs.



---

*Source: 7986351-2020-06-30.xml*