1 Introduction

The Weighted Linear Complementarity Problem (WLCP) is a generalization of the linear complementarity problem in which the zero on the right side of the complementarity equation is replaced by a nonnegative weight vector. The WLCP is important because a wide range of problems from sciences, engineering and economics can be modeled as a WLCP. In [13], Potra has shown that the quadratic programming and weighted centering problem, which is a generalization of the linear programming and weighted centering problem introduced by Anstreicher [3], can be formulated as a special case of monotone WLCP. Then, he defined a smooth central path for WLCP and proposed two interior-point methods (IPMs) for solving the WLCP, both of which follow the smooth central path. Potra [14] extended the notion of sufficiency for linear complementarity problem (LCP) introduced by Cottle et al. [7] to the WLCP. He also showed that if a sufficient WLCP is strictly feasible, then it is solvable. The author uses the notion of the central path of the WLCP introduced in [13] and proposes a path-following IPM. Tang and Zhou [17] introduced a modified damped Gauss–Newton method for nonmonotone WLCP. Tang and Zhang [16] proposed a nonmonotone smoothing Newton algorithm for solving general WCPs. Tang and Zhou [18] proposed a nonmonotone Levenberg–Marquardt type method for solving the weighted nonlinear complementarity problem (WNCP) and gave its global convergence without any additional condition. Zhang [22] presented a new one-step smoothing Newton method for solving the monotone WLCP needing only to solve one linear system of equations and performing only one line search per iteration.

Full-Newton step IPMs for solving linear optimization (LO) were initiated by Roos et al. [15]. These methods have the advantage that no line searches are needed during the solution process to update the iterates. Various full-Newton step algorithms have been presented in the literature to solve different formulations of LCPs. In 2003, Darvay introduced a new technique for finding search directions for LO [8]. The key idea of this approach consists of considering an algebraic equivalent transformation on the system which defines the central path. That is, a continuously differentiable, invertible, monotone increasing function \(\psi :(\xi , \infty )\rightarrow {\textbf{R}}\), with \(0\le \xi <1\) is applied on both sides of the nonlinear equations of the central path. The new search directions are determined by applying Newton’s method to the resulting system. Then, the author presented a feasible IPM with full-Newton steps for LO. Infeasible IPMs (IIPMs) for LO and symmetric optimization (SO) based on this technique are proposed in [2, 9]. The AET technique extended to other areas, such as LCPs [1, 10, 12], semidefinite optimization [19], Second-order cone optimization (SOCO) [20] and SO [21]. In [11], an adaptive full-Newton step IIPM for solving sufficient horizontal LCP is presented and sufficient conditions are given for the superlinear convergence of the sequence of iterates. Recently, Asadi et al. [4] extended the full-Newton step IPM to the monotone WLCP and established the feasibility of the full steps and a quadratic rate of convergence to the target points on the central path. In [6], a full-modified-Newton step O(n) IIPM is presented for the special WLCP. Chi and Wang [5] proposed a full-Newton step IIPM for solving a special WLCP.

Motivated by above-mentioned results, in this paper, we extend the full-Newton step IPM based on the AET technique for the monotone WLCP. The square root function is used to obtain an equivalent form of the system defining the same central path used in [13, 14]. We apply the Newton method to the resulting system in order to get new search directions and we take full steps along these directions. We analyze the method and derive an iteration bound for WLCP having the same complexity as the one obtained for these types of problems. The method developed in [4] is a special case of our method for \(\psi (t)=t\).

The paper is organized as follows: In Sect. 2, we remember the monotone WLCP and the notion of the central path used in [13] for WLCP. In Sect. 3, we describe the AET and we obtain the scaled Newton system. A theoretical framework of the algorithm is presented in Sects. 4, 5 is devoted to the analysis of the algorithm. The iteration bound is derived in Sect. 6. Some numerical results are presented in Sect. 7. Concluding remarks are given in Sect. 8.

2 WLCP and its Central Path

The WLCP consists of finding \((x, s, y)\in {\textbf{R}}^{n}\times {\textbf{R}}^n\times {\textbf{R}}^m\) such that

$$\begin{aligned} \begin{array}{ccccccc} Px+Qs+Ry=a,~~~ x,s\ge 0~~~\\ xs=w, \end{array} \end{aligned}$$
(1)

where \(P, Q\in {\textbf{R}}^{(n+m)\times n}\) and \(R\in {\textbf{R}}^{(n+m)\times m}\) are given matrices, \(a\in {\textbf{R}}^{m+n}\) is a given vector, and \(w\in {\textbf{R}}^n_+\) is a given weight vector. Here, xs denotes the vector with components \(x_is_i\). It is further assumed that the matrix R has full column rank. The WLCP (1) is called monotone, if

$$\begin{aligned} P\varDelta x+Q\varDelta s+R\varDelta y=0~~\textrm{implies}~~ \varDelta x^T\varDelta s\ge 0, \end{aligned}$$

and it is called skew-symmetric, if

$$\begin{aligned} P\varDelta x+Q\varDelta s+R\varDelta y=0~~\textrm{implies}~~ \varDelta x^T\varDelta s=0. \end{aligned}$$

We denote the set of all feasible points (1) by

$$\begin{aligned} {\mathcal {F}}:=\{(x, s, y)\in {\textbf{R}}^n_+\times {\textbf{R}}_+^n\times {\textbf{R}}^m: Px+Qs+Ry=a\}, \end{aligned}$$

and the solution set of (1) by

$$\begin{aligned} {\mathcal {F}}^*:=\{(x, s, y)\in {\mathcal {F}}:~ xs=w\}. \end{aligned}$$

The set of all strictly feasible points of (1) is given by

$$\begin{aligned} {\mathcal {F}}^0:=\{(x, s, y)\in {\mathcal {F}}:~ x,~s>0\}. \end{aligned}$$

Given a strictly feasible starting point \((x^0, s^0, y^0)\in {\mathcal {F}}^0\). We set

$$\begin{aligned} \begin{array}{ccccccc} \mu ^0=\frac{(x^0)^Ts^0}{n},~ c=x^0s^0,~\gamma =\frac{\min c}{\mu ^0},~w(\mu )=(1-\frac{\mu }{\mu ^0})w+\frac{\mu }{\mu ^0}c,~\mu \in (0, \mu ^0]. \end{array} \end{aligned}$$
(2)

The central path of the WLCP (1) is the set of all points \((\mu ; x, s, y)\), with \(\mu \in [0, \mu ^0]\), satisfying

$$\begin{aligned} \begin{array}{ccccccc} Px+Qs+Ry=a,~~ x,s>0\\ \qquad \quad xs=w(\mu ). \end{array} \end{aligned}$$
(3)

This path is well-defined; in fact, it is shown that if the WLCP is monotone and \({\mathcal {F}}^0\ne \emptyset \), then (3) has a unique solution for any \(\mu \in [0, \mu ^0]\) (see [14]). It is worth noting that by construction, \((\mu ^0; x^0, s^0, y^0)\) belongs to the central path, because it follows from \((x^0, s^0, y^0)\in {\mathcal {F}}^0\) that \(Px^0+Qs^0+Ry^0=a\), moreover, we have \(x^0s^0=c=(1-\frac{\mu ^0}{\mu ^0})w+\frac{\mu ^0}{\mu ^0}c=w(\mu ^0)\). Note that the central path converges to a solution of (1) if \(\mu \downarrow 0\).

3 A New Search Direction for WLCP

Based on Darvay’s technique for LO [8], we introduce a method for finding new search directions for IPMs in WLCP. Let us define the continuously differentiable function \(\psi :{\textbf{R}}_+\rightarrow {\textbf{R}}_+\) and assume that the inverse function \(\psi ^{-1}\) exists. In this way, we can write system (3) in the following equivalent form:

$$\begin{aligned} \begin{array}{ccccccc} Px+Qs+Ry=a,~~~~ x,s>0~~~~~~\\ \quad \,\psi (xs)=\psi (w(\mu )). \end{array} \end{aligned}$$
(4)

We assume that \(Px+Qs+Ry=a\) for a triple (x, s, y) such that \(x>0\) and \(s>0\). Applying Newton’s method to system (4) and linearizing it, we obtain the following system for the search directions \(\varDelta x, \varDelta s\), and \(\varDelta y\):

$$\begin{aligned} \begin{array}{ccccccc} P\varDelta x+Q\varDelta s+R\varDelta y=0,~~~~~~~~~ ~~~~~~\\ \quad \,\, s\psi ^{'}(xs)\varDelta x+x\psi ^{'}(xs)\varDelta s=\psi (w(\mu ))-\psi (xs). \end{array} \end{aligned}$$
(5)

This system can be rewritten as follows:

$$\begin{aligned} \begin{array}{ccccccc} P\varDelta x+Q\varDelta s+R\varDelta y=0,~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~~~~~\\ \qquad \qquad \quad s\varDelta x+x\varDelta s=\big (\psi ^{'}(xs)\big )^{-1}\big (\psi (w(\mu ))-\psi (xs)\big ). \end{array} \end{aligned}$$
(6)

The new iterates are then given as:

$$\begin{aligned} x^+=x+\varDelta x,~~~ s^+=s+\varDelta s,~~ y^+=y+\varDelta y, \end{aligned}$$

indicating that a full-Newton step is taken along the search directions. Now we introduce the following notations:

$$\begin{aligned} v=\sqrt{\frac{xs}{\mu }},~~ d_x=\frac{v\varDelta x}{x},~~ d_s=\frac{v\varDelta s}{s}. \end{aligned}$$
(7)

Then, the system (6) becomes as follows:

$$\begin{aligned} \begin{array}{ccccccc} {{\tilde{P}}}d_x+{{\tilde{Q}}}d_s+R\varDelta y=0, ~~~~~~~~~~~~\\ \quad \quad \quad d_x+d_s=p_v, \end{array} \end{aligned}$$
(8)

where \({{\tilde{P}}}=PV^{-1}X,~{\tilde{Q}}=QV^{-1}S,~V=\textrm{diag}(v),~ X=\textrm{diag}(x), S=\textrm{diag}(s),\) and

$$\begin{aligned} p_v=\frac{\psi (w(\mu ))-\psi (\mu v^2)}{\mu v\psi ^{'}(\mu v^2)}. \end{aligned}$$

It is worth noting that for different functions \(\psi \), we obtain different new search directions.

4 A New Interior-Point Algorithm for WLCP

We mention that \(\psi (t)=t\) yields \(p_v=v^{-1}(\frac{w(\mu )}{\mu }-v^2)\), and we obtain the search direction introduced in [4]. Here, we consider \(\psi (t)=\sqrt{t}, t>0\) based on Darvay’s technique for LO [8]. For this function, we have

$$\begin{aligned} p_v=2\left( \sqrt{\frac{w(\mu )}{\mu }}-v\right) . \end{aligned}$$
(9)

To measure the proximity of any approximation (x, s, y) of \((x(\mu ), s(\mu ), y(\mu ))\) to the central path (4), we define a proximity function as follows:

$$\begin{aligned} \delta :=\delta (x, s; \mu )=\frac{1}{2}\Vert p_v\Vert =\Big \Vert \sqrt{\frac{w(\mu )}{\mu }}-v\Big \Vert . \end{aligned}$$

Note that for any \((x, s, y)\in {\mathcal {F}}\), we have

$$\begin{aligned} xs=w(\mu ) \Leftrightarrow v^2=\frac{w(\mu )}{\mu } \Leftrightarrow v=\sqrt{\frac{w(\mu )}{\mu }} \Leftrightarrow \delta (x, s; \mu )=0. \end{aligned}$$

Let \(q_v=d_x-d_s\). One can easily find

$$\begin{aligned} d_x=\frac{p_v+q_v}{2},~~ d_s=\frac{p_v-q_v}{2}, \end{aligned}$$

and

$$\begin{aligned} d_xd_s=\frac{p_v^2-q_v^2}{4}. \end{aligned}$$
(10)

Since the WLCP is monotone, we have \(\varDelta x^T\varDelta s\ge 0\), and this implies

$$\begin{aligned} \Vert q_v\Vert ^2=\Vert d_x-d_s\Vert ^2=\Vert d_x+d_s\Vert ^2-4d_x^Td_s\le \Vert p_v\Vert ^2=4\delta ^2. \end{aligned}$$
(11)

We now outline the method.

\({{\mathbf{Algorithm~}:\mathrm{Full-Newton~step~IPM ~for~ WLCP }}}\)

Input: Required parameter \(\varepsilon >0\); threshold parameter \(0<\tau <1\);

barrier update parameter \(0<\theta <1\);

An initial point \((x^0, s^0, y^0)\in {\mathcal {F}}^0\) with \(\delta (x^0, s^0; \mu ^0)\le \tau \), where \(\mu _0=\frac{(x^0)^Ts^0}{n}\);

Set \(k=0\);

while \(\Vert \sqrt{w}-\sqrt{x^ks^k}\Vert >\varepsilon \) do;

Set \(\mu ^{k+1}=(1-\theta )\mu ^k\);

Obtain the search direction \((\varDelta x^k, \varDelta s^k, \varDelta y^k)\) by solving (8) and using (7);

Set  \((x^{k+1}, s^{k+1}, y^{k+1})=(x^{k}, s^{k}, y^{k})+(\varDelta x^k, \varDelta s^k, \varDelta y^k)\);

Set  \(k:=k+1\);

end while.

5 Analysis of the Algorithm

In the next lemma, we give a condition which guarantees the strict feasibility of the full-Newton step.

Lemma 5.1

A new iterate \((x^+, s^+, y^+)\) is strictly feasible if

$$\begin{aligned} \delta :=\delta (x, s; \mu )<\sqrt{\gamma }. \end{aligned}$$

Proof

Consider a step length \(0\le \alpha \le 1\) and define

$$\begin{aligned} x(\alpha )=x+\alpha \varDelta x,~~~~ s(\alpha )=s+\alpha \varDelta s. \end{aligned}$$

Therefore,

$$\begin{aligned} x(\alpha )s(\alpha )=xs+\alpha (x\varDelta s+s\varDelta x)+\alpha ^2\varDelta x\varDelta s. \end{aligned}$$

Using (7), the second equation of (8) and (10), we get

$$\begin{aligned} \frac{1}{\mu }x(\alpha )s(\alpha ){} & {} =v^2+\alpha v(d_x+d_s)+\alpha ^2d_xd_s\nonumber \\{} & {} =v^2+\alpha vp_v+\alpha ^2\frac{p_v^2-q_v^2}{4}\nonumber \\{} & {} =(1-\alpha )v^2+\alpha (v^2+vp_v)+\alpha ^2\frac{p_v^2-q_v^2}{4}\nonumber \\{} & {} =(1-\alpha )v^2+\alpha \Big (\frac{w(\mu )}{\mu }-(1-\alpha )\frac{p_v^2}{4}-\alpha \frac{q_v^2}{4}\Big ). \end{aligned}$$
(12)

The last equality holds, since

$$\begin{aligned} v^2+vp_v=v^2+2v\Big (\sqrt{\frac{w(\mu )}{\mu }}-v\Big )=2v\sqrt{\frac{w(\mu )}{\mu }}-v^2=\frac{w(\mu )}{\mu }-\frac{p_v^2}{4}. \end{aligned}$$

Furthermore, for \(0\le \alpha \le 1\), we have

$$\begin{aligned} \Big \Vert (1-\alpha )\frac{p_v^2}{4}+\alpha \frac{q_v^2}{4}\Big \Vert _{\infty }\le (1-\alpha )\frac{\Vert p_v^2\Vert _{\infty }}{4}+\alpha \frac{\Vert q_v^2\Vert _{\infty }}{4}~~\\ \le (1-\alpha )\frac{\Vert p_v\Vert ^2}{4}+\alpha \frac{\Vert q_v\Vert ^2}{4}~~~~\\ \le (1-\alpha )\delta ^2+\alpha \delta ^2=\delta ^2<\gamma , \end{aligned}$$

where the third inequality is due to (11). From this inequality, we have

$$\begin{aligned} 0<\gamma -\Big \Vert (1-\alpha )\frac{p_v^2}{4}+\alpha \frac{q_v^2}{4}\Big \Vert _{\infty } \le \min _i\frac{w_i(\mu )}{\mu }-\max _i\Big |(1-\alpha )\frac{(p_v^2)_i}{4}+\alpha \frac{(q_v^2)_i}{4}\Big |\\ =\min _i\Big (\frac{w_i(\mu )}{\mu }-(1-\alpha )\frac{(p_v^2)_i}{4}-\alpha \frac{(q_v^2)_i}{4}\Big ),~~ \end{aligned}$$

which shows that

$$\begin{aligned} \frac{w(\mu )}{\mu }-(1-\alpha )\frac{p_v^2}{4}-\alpha \frac{q_v^2}{4}>0. \end{aligned}$$

Thus for all \(0\le \alpha \le 1\), we have

$$\begin{aligned} (1-\alpha )v^2+\alpha \Big (\frac{w(\mu )}{\mu }-(1-\alpha )\frac{p_v^2}{4}-\alpha \frac{q_v^2}{4}\Big )>0. \end{aligned}$$

Now, it follows from (12) that \(x(\alpha )s(\alpha )>0\) for all \(0\le \alpha \le 1\). This shows that the components of \(x(\alpha )\) and \(s(\alpha )\) cannot vanish. Since \(x>0\) and \(s>0\) and \(x(\alpha )\) and \(s(\alpha )\) are linear functions in \(\alpha \), we have \(x(\alpha )>0\) and \(s(\alpha )>0\) for all \(0\le \alpha \le 1\). Hence, \(x(1)=x^+>0\) and \(s(1)=s^+>0\). This proves the lemma. \(\square \)

Lemma 5.2

Let \(\delta =\delta (x, s; \mu )\). After a full-Newton step

$$\begin{aligned} \min v^+\ge \sqrt{\gamma -\delta ^2}, \end{aligned}$$

where \(v^+=\sqrt{\frac{x^+s^+}{\mu }.}\)

Proof

By setting \(\alpha =1\) in (12), we get

$$\begin{aligned} \frac{x^+s^+}{\mu }=\frac{w(\mu )}{\mu }-\frac{q_v^2}{4}. \end{aligned}$$
(13)

Now, from (13) and the definition of \(v^+\), we have

$$\begin{aligned} \min \big ((v^+)^2\big ){} & {} =\min \Big (\frac{w(\mu )}{\mu }-\frac{q_v^2}{4}\Big )\ge \min \frac{w(\mu )}{\mu }-\frac{\Vert q_v^2\Vert _{\infty }}{4}\\{} & {} \ge \frac{\min c}{\mu ^0}-\frac{\Vert q_v\Vert ^2}{4}\ge \gamma -\delta ^2.~~~~~~~~~~~~~~~~~~~~ \end{aligned}$$

Taking the square root on both sides of the above inequality leads to the desired inequality and the proof is complete. \(\square \)

Lemma 5.3

Let \(\delta :=\delta (x, s; \mu )<\sqrt{\gamma }\). Then, we have

$$\begin{aligned} \delta ^+:=\delta (x^+, s^+; \mu )\le \frac{\delta ^2}{\sqrt{\gamma }+\sqrt{\gamma -\delta ^2}}. \end{aligned}$$

Thus, \(\delta ^+\le \frac{1}{\sqrt{\gamma }}\delta ^2\), which shows the quadratic convergence of the algorithm.

Proof

Using Lemma 5.2, (13) and (11), we have

$$\begin{aligned} \delta ^+ =\Big \Vert \sqrt{\frac{w(\mu )}{\mu }}-v^+\Big \Vert{} & {} =\Big \Vert \frac{e}{\sqrt{\frac{w(\mu )}{\mu }}+v^+}\big (\frac{w(\mu )}{\mu }-(v^+)^2\big )\Big \Vert \\{} & {} \le \frac{1}{\sqrt{\gamma }+\sqrt{\gamma -\delta ^2}}\Big \Vert \frac{w(\mu )}{\mu }-(v^+)^2\Big \Vert \\{} & {} =\frac{1}{\sqrt{\gamma }+\sqrt{\gamma -\delta ^2}}\big \Vert \frac{q_v^2}{4}\big \Vert \\{} & {} \le \frac{1}{\sqrt{\gamma }+\sqrt{\gamma -\delta ^2}}\frac{\Vert q_v\Vert ^2}{4}\\{} & {} \le \frac{\delta ^2}{\sqrt{\gamma }+\sqrt{\gamma -\delta ^2}}, \end{aligned}$$

which completes the proof. \(\square \)

Lemma 5.4

After a full-Newton step, one has

$$\begin{aligned} (x^+)^Ts^+\le \Vert w(\mu )\Vert _1. \end{aligned}$$

Proof

From (13), we obtain

$$\begin{aligned} \frac{(x^+)^Ts^+}{\mu }=e^T\frac{w(\mu )}{\mu }-e^T\frac{q_v^2}{4} =\frac{1}{\mu }\Vert w(\mu )\Vert _1-\frac{1}{4}\Vert q_v\Vert ^2\le \frac{1}{\mu }\Vert w(\mu )\Vert _1, \end{aligned}$$

as desired. \(\square \)

Lemma 5.5

Let \(\delta :=\delta (x, s; \mu )<\sqrt{\gamma }\) and \(\mu ^+:=(1-\theta )\mu \), where \(0<\theta <1\). Then, we have

$$\begin{aligned} \delta (x^+, s^+; \mu ^+)\le \frac{1}{\sqrt{1-\theta }\Big (\sqrt{\gamma -\frac{\theta }{\mu ^0}\Vert w-c\Vert }+\sqrt{\gamma -\delta ^2}\Big )} \Big (\delta ^2+\frac{\theta }{\mu ^0}\Vert w-c\Vert \Big ). \end{aligned}$$

Proof

Let \({{\bar{v}}}^+:=\sqrt{\frac{x^+s^+}{\mu ^+}}\). From the definition of \(w(\mu )\), we have

$$\begin{aligned} w(\mu ^+)=w(\mu )+\frac{\theta \mu }{\mu ^0}(w-c)\ge \frac{\mu }{\mu ^0}c+\frac{\theta \mu }{\mu ^0}(w-c) =(1-\theta )\frac{\mu }{\mu ^0}c+\frac{\theta \mu }{\mu ^0}w>0. \end{aligned}$$

Therefore, using (11), (13) and Lemma 5.2, we have

$$\begin{aligned}{} & {} \delta (x^+, s^+; \mu ^+)\\{} & {} =\Big \Vert \sqrt{\frac{w(\mu ^+)}{\mu ^+}}-{\bar{v}}^+\Big \Vert =\Big \Vert \sqrt{\frac{w(\mu )+\frac{\theta \mu }{\mu ^0}(w-c)}{(1-\theta )\mu }}-\frac{v^+}{\sqrt{1-\theta }}\Big \Vert \\{} & {} =\frac{1}{\sqrt{1-\theta }}\Big \Vert \sqrt{\frac{w(\mu )}{\mu }+\frac{\theta }{\mu ^0}(w-c)}-v^+\Big \Vert \\{} & {} \le \frac{1}{\sqrt{1-\theta }\Big (\sqrt{\gamma -\frac{\theta }{\mu ^0}\Vert w-c\Vert }+\sqrt{\gamma -\delta ^2}\Big )} \Big \Vert \frac{w(\mu )}{\mu }+\frac{\theta }{\mu ^0}(w-c)-(v^+)^2\Big \Vert \\{} & {} \le \frac{1}{\sqrt{1-\theta }\Big (\sqrt{\gamma -\frac{\theta }{\mu ^0}\Vert w-c\Vert }+\sqrt{\gamma -\delta ^2}\Big )} \Big (\big \Vert \frac{w(\mu )}{\mu }-(v^+)^2\big \Vert +\frac{\theta }{\mu ^0}\Vert w-c\Vert \Big )\\{} & {} \le \frac{1}{\sqrt{1-\theta }\Big (\sqrt{\gamma -\frac{\theta }{\mu ^0}\Vert w-c\Vert }+\sqrt{\gamma -\delta ^2}\Big )} \Big (\frac{\Vert q_v\Vert ^2}{4}+\frac{\theta }{\mu ^0}\Vert w-c\Vert \Big )\\{} & {} \le \frac{1}{\sqrt{1-\theta }\Big (\sqrt{\gamma -\frac{\theta }{\mu ^0}\Vert w-c\Vert }+\sqrt{\gamma -\delta ^2}\Big )} \Big (\delta ^2+\frac{\theta }{\mu ^0}\Vert w-c\Vert \Big ). \end{aligned}$$

The proof is complete. \(\square \)

6 Iteration Bound

We obtain a worst-case upper bound on the number of iterations of the proposed algorithm. Before doing so, we determine the values for the barrier parameter \(\theta \) and the threshold parameter \(\tau \) guaranteeing that the algorithm is well-defined, that is, if \(\delta :=\delta (x, s; \mu )\le \tau \) then \(\delta (x^+, s^+; \mu ^+)\le \tau .\) From Lemma 5.5, using \(\delta \le \tau \), the condition \(\delta (x^+, s^+; \mu ^+)\le \tau \) holds if

$$\begin{aligned} \frac{1}{\sqrt{1-\theta }\Big (\sqrt{\gamma -\frac{\theta }{\mu ^0}\Vert w-c\Vert }+\sqrt{\gamma -\tau ^2}\Big )} \Big (\tau ^2+\frac{\theta }{\mu ^0}\Vert w-c\Vert \Big )\le \tau . \end{aligned}$$
(14)

For any given \(\tau \), this inequality determines how big the updates of the barrier parameter \(\theta \) are allowed to be. Let

$$\begin{aligned} \tau =\sqrt{\frac{\gamma }{2}},~~ \theta =\frac{\min c}{3(\min c+\Vert w-c\Vert +1)}. \end{aligned}$$
(15)

Clearly, we have \(\tau =\sqrt{\frac{\gamma }{2}}<\sqrt{\gamma }\). Thus, from Lemma 5.1, the full-Newton step will be feasible. Note that \(\theta \le \frac{1}{3}\), which yields \(\frac{1}{\sqrt{1-\theta }}\le \sqrt{\frac{3}{2}}\). Moreover, using the values of \(\theta \) and \(\tau \) given in (15), we obtain

$$\begin{aligned}{} & {} \frac{1}{\sqrt{1-\theta }\Big (\sqrt{\gamma -\frac{\theta }{\mu ^0}\Vert w-c\Vert }+\sqrt{\gamma -\tau ^2}\Big )} \Big (\tau ^2+\frac{\theta }{\mu ^0}\Vert w-c\Vert \Big )\\{} & {} \le \frac{3}{\sqrt{2}(2+\sqrt{3})\sqrt{\frac{\gamma }{2}}}\big (\frac{5}{3}\big )\frac{\gamma }{2}\\{} & {} =\frac{5}{\sqrt{2}(2+\sqrt{3})}\sqrt{\frac{\gamma }{2}}\le \sqrt{\frac{\gamma }{2}}. \end{aligned}$$

Thus, the condition (14) is satisfied. Hence, Algorithm is well-defined.

Theorem 6.1

If WLCP is monotone and \(\theta \) and \(\tau \) are defined as in (15), then Algorithm finds an \(\varepsilon \)-approximate solution \((x, s, y)\in {\mathcal {F}}^0\) such that

$$\begin{aligned} \Vert \sqrt{w}-\sqrt{xs}\Vert \le \varepsilon \end{aligned}$$

in at most

$$\begin{aligned} \left\lceil \frac{6\big (\min c+\Vert c-w\Vert +1\big )}{\min c}\log \frac{\sqrt{\frac{\min c}{2}}+\beta }{\varepsilon }\right\rceil \end{aligned}$$

iterations, where \(\beta =\max \big \{\big \Vert \sqrt{c-w}\big \Vert , \big \Vert \frac{c-w}{2\sqrt{w}+e}\big \Vert \big \}\) and \(e=(1, \ldots , 1)^T.\)

Proof

We have

$$\begin{aligned} \Vert \sqrt{w}-\sqrt{xs}\Vert{} & {} \le \Vert \sqrt{w(\mu )}-\sqrt{xs}\Vert +\Vert \sqrt{w(\mu )}-\sqrt{w}\Vert ~\nonumber \\{} & {} =\sqrt{\mu }\Big \Vert \sqrt{\frac{w(\mu )}{\mu }}-v\Big \Vert +\Vert \sqrt{w(\mu )}-\sqrt{w}\Vert \nonumber \\{} & {} =\sqrt{\mu }\delta +\Vert \sqrt{w(\mu )}-\sqrt{w}\Vert \nonumber \\{} & {} \le \sqrt{\frac{\mu \gamma }{2}}+\Vert \sqrt{w(\mu )}-\sqrt{w}\Vert . \end{aligned}$$
(16)

On the other hand, from the definition of \(w(\mu )\), we obtain

$$\begin{aligned} \big \Vert \sqrt{w(\mu )}-\sqrt{w}\big \Vert =\Big \Vert \sqrt{w+\frac{\mu }{\mu ^0}(c-w)}-\sqrt{w}\Big \Vert . \end{aligned}$$

Consider the following cases:

Case 1. \(c-w\ge 0\). We have

$$\begin{aligned} \Big \Vert \sqrt{w+\frac{\mu }{\mu ^0}(c-w)}-\sqrt{w}\Big \Vert \le \Big \Vert \sqrt{w}+\sqrt{\frac{\mu }{\mu ^0}(c-w)}-\sqrt{w}\Big \Vert =\sqrt{\frac{\mu }{\mu ^0}}\big \Vert \sqrt{c-w}\big \Vert . \end{aligned}$$

Case 2. \(c-w<0\). We have

$$\begin{aligned} \Big \Vert \sqrt{w+\frac{\mu }{\mu ^0}(c-w)}-\sqrt{w}\Big \Vert \simeq \Big \Vert \sqrt{w}+\frac{\frac{\mu }{\mu ^0}(c-w)}{2\sqrt{w}+e}-\sqrt{w}\Big \Vert \le \sqrt{\frac{\mu }{\mu ^0}}\Big \Vert \frac{c-w}{2\sqrt{w}+e}\Big \Vert . \end{aligned}$$

Using the above two inequalities, we have

$$\begin{aligned} \Big \Vert \sqrt{w+\frac{\mu }{\mu ^0}(c-w)}-\sqrt{w}\Big \Vert \le \sqrt{\frac{\mu }{\mu ^0}}\beta . \end{aligned}$$

Substituting the above bound into (16), we obtain the first inequality below and, after k iterations, we obtain second inequality below.

$$\begin{aligned} \Vert \sqrt{w}-\sqrt{xs}\Vert \le \Big (\sqrt{\frac{\mu ^0\gamma }{2}}+\beta \Big )\sqrt{\frac{\mu }{\mu ^0}} \le \Big (\sqrt{\frac{\mu ^0\gamma }{2}}+\beta \Big )(1-\theta )^{\frac{k}{2}}. \end{aligned}$$

Using the definition of \(\gamma \) from (2), we deduce that \(\Vert \sqrt{w}-\sqrt{xs}\Vert \le \varepsilon \) is satisfied if

$$\begin{aligned} \Big (\sqrt{\frac{\min c}{2}}+\beta \Big )(1-\theta )^{\frac{k}{2}}\le \varepsilon . \end{aligned}$$

Taking logarithms of both sides and using the inequality \(\log (1+\theta )\le \theta \) for \(\theta >-1\), we obtain

$$\begin{aligned} k\ge \frac{6\big (\min c+\Vert c-w\Vert +1\big )}{\min c}\log \frac{\sqrt{\frac{\min c}{2}}+\beta }{\varepsilon }, \end{aligned}$$

which completes the proof. \(\square \)

7 Numerical Results

In this section, we present computational results of an implementation of our algorithm in MATLAB R2009a on some randomly generated WLCPs. We generate the matrices R and Q with entries randomly selected from the interval \([-6, 6]\). To build the matrix P, we first constructed matrix \(A\in {\textbf{R}}^{n\times n}\) with elements randomly from \([-6, 6]\). Then, we considered \(P=-Q(A^TA)\). Elements of w were chosen randomly from [0.2, 0.8]. We used the value of the accuracy parameter \(\varepsilon =10^{-8}\) and we reduced the value of the barrier update parameter \(\mu \) by the factor \(1-\theta \) when \(\theta =0.25\). Table shows the number of iterations (iter) as well as the value of the complementarity gap \(\mu \) at the \(\varepsilon \)-approximate solutions for the WLCP problems.

Table 1 Numerical results
Full size table

8 Concluding Remarks

In this paper, we presented a full-Newton step IPM based on the AET for solving monotone WLCP. The square root function is used to obtain an equivalent form of the system defining the central path. The Newton method is applied to the resulting system in order to obtain new search directions. By appropriately selecting the barrier and threshold parameters, the iterates are shown to be in a certain neighborhood \(\delta (x, s; \mu )\le \tau \) of the central path . It is also shown that the proximity measure reduces quadratically at each iteration. The derived iteration bound coincides with the iteration bounds obtained for these types of problems [13, 14]. Some numerical results illustrate the efficiency of the method for solving monotone WLCPs.