© Wuhan University 2023

0 Introduction

Since Karmarkar's seminal work in linear programming (LP)^[1], interior-point methods (IPMs) have emerged as a major research area and are widely regarded as highly effective methods. IPMs have been successfully extended to solve various optimization problems, such as semi-definite programming (SDP), linear complementarity problem (LCP), and second-order cone programming (SOCP). As a result, corresponding optimization software packages have been developed and widely adopted^[2,3]. Among the existing IPMs, primal-dual IPM is recognized as one of the most efficient methods.

Initially, the classical Newton direction determined by the logarithmic kernel function was used in primal-dual IPM. However, Peng et al ^[4] introduced the concept of self-regular kernel function in 2001 and used it to determine the search direction, which greatly improved the theoretical iteration complexity of the primal-dual IPM. This marked an important breakthrough in IPM research. Furthermore, Bai et al^[5] proposed a primal-dual IPM for linear programming based on a class of eligible kernel functions (not necessarily self-regular) and achieved excellent iteration complexity results. Currently, IPM based on kernel function is a very active research areas in mathematical programming^[6-8]. Roos^[2] proposed a primal-dual full-Newton step feasible IPM for LP in 1997, which avoids step size calculation and linear search and is known as the simplest primal-dual IPM. This algorithm has also been extended to other optimization models. For example, Wang et al^[9] generalized Roos' method to solve LCP and Darvay et al^[10,11] designed the full-Newton step IPM for LP and symmetric optimization (SO) based on algebraic equivalence transformation. Zhang et al proposed the full-Newton step IPM based on the positive-asymptotic kernel function to solve LCP, and obtained the best iteration result of the small-update algorithm${}^{[\mathrm{12}]}$.

Recently, Zhang and Geng et al^[13,14] proposed the full-Newton step feasible (infeasible) IPM for LP and SDP respectively using the kernel function with linear growth terms. Their algorithms obtained the best-known iterative complexity results and demonstrated good performance in corresponding calculation.

The weighted linear complementarity problem (wLCP), which is a generalization of the LCP, was first proposed by Potra in 2012^[15]. Since then, two IPMs have been proposed and analyzed for the monotonic wLCP. The wLCP has found wide applications in various fields such as science, finance, management, and engineering. Subsequently, Potra^[16] proposed a predictor-corrector IPM for the sufficient wLCP. More recently, Asadi et al^[17] proposed a full-Newton step feasible IPM for the monotonic wLCP and proved that the algorithm achieves the best known iterative complexity. Furthermore, Chi et al^[18] proposed a full-Newton step feasible IPM for the special wLCP based on specific continuous differentiable functions and used the Darvay algebraic equivalence transformation method to determine the search direction. Their approach yielded excellent theoretical complexity and demonstrated good practical calculation results.

A new full-Newton step primal-dual IPM is proposed for the special wLCP based on the search direction determined by the kernel function with linear growth term^[13,14]. The algorithm eliminates the calculation of the step size by using full-Newton steps. By utilizing the simple algebraic expression of the kernel function with linear growth term, an appropriate proximity measure is defined, and new technical results are established to overcome the difficulty of convergence analysis caused by the non-negative weight vector. Under weaker conditions, the polynomial complexity of the algorithm is proved, and its complexity order is shown to be the same as the best existing complexity order among similar methods. Numerical examples demonstrate the effectiveness of the proposed algorithm. To the authors' knowledge, this algorithm is the first full-Newton IPM based on kernel functions with linear growth terms for solving wLCP.

The remainder of this paper is organized as follows. In Section 1, we introduce the full-Newton step primal-dual interior-point algorithm. The convergence analysis and the iteration bound of the algorithm are shown in Section 2. In Section 3, we get the upper bound of the number of iterations of the algorithm. In Section 4, we present some numerical examples and results. Finally, some conclusions are given in Section 5.

1 Full-Newton Step Primal-Dual Interior-Point Algorithm

In this paper, we consider the following special wLCP, which is to find vectors $(\mathit{x},\mathit{y},\mathit{s}) \in {\mathbb{R}}^n \times {\mathbb{R}}^m \times {\mathbb{R}}^n$ such that

$\{\begin{array}{l}\mathit{A}\mathit{x}=\mathit{b}, \mathit{x}\ge \mathrm{0}\\ {\mathit{A}}^{\mathrm{T}}\mathit{y}+\mathit{s}=\mathit{c} , \mathit{s}\ge \mathrm{0}\\ \mathit{x}\mathit{s}=\mathit{\omega } \end{array}$(1)

where $\mathit{A}\in {\mathbb{R}}^{m\times n}$ is a given matrix with full row rank, $\mathit{b}\in {\mathbb{R}}^m$, $\mathit{c}\in {\mathbb{R}}^n$ are given vectors, and $\mathit{\omega }\in {\mathbb{R}}_{+}^n\triangleq \{\mathit{x}\in {\mathbb{R}}_{}^n|\mathit{x}\ge \mathrm{0}\}$ is a given weight vector. When $\mathit{\omega }=\mathrm{0}$, the system (1) reduces to the KKT condition for LP. Therefore, solving for special wLCP (1) becomes a more challenging problem than solving LP.

Denote the strictly feasible set of problem (1) as

$F^{\mathrm{0}}\triangleq \left\{(\mathit{x},\mathit{y},\mathit{s})\in {\mathbb{R}}_{++}^n \times {\mathbb{R}}^m \times {\mathbb{R}}_{++}^n|\mathit{A}\mathit{x}=\mathit{b},{\mathit{A}}^{\mathrm{T}}\mathit{y}+\mathit{s}=\mathit{c} \right\}$

where ${\mathbb{R}}_{++}^n\triangleq \{\mathit{x}\in {\mathbb{R}}_{}^n|\mathit{x}>\mathrm{0}\}.$

Choose an initial point $({\mathit{x}}^{\mathrm{0}},{\mathit{y}}^{\mathrm{0}},{\mathit{s}}^{\mathrm{0}}) \in F^{\mathrm{0}}, \mathit{\omega } (t)=t {\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}+(\mathrm{1}-t) \mathit{\omega } , t\in \left(\mathrm{0,1}\right)$.

Let $t_{\mathrm{0}}=\mathrm{1}, \mathit{\omega }>\mathrm{0}$ and consider the perturbed version of problem (1)

$\{\begin{array}{l}\mathit{A}\mathit{x}=\mathit{b}, \mathit{x}\ge \mathrm{0}\\ {\mathit{A}}^{\mathrm{T}}\mathit{y}+\mathit{s}=\mathit{c} , \mathit{s}\ge \mathrm{0}\\ \mathit{x}\mathit{s}=\mathit{\omega } (t)\end{array}$(2)

Throughout this paper, we assume that the special wLCP (1) satisfies the interior point condition (IPC), i.e.,$F^{\mathrm{0}}\ne \mathrm{\varnothing }$, which implies the existence of a solution for the problem (1). Since $\mathit{A}$ is a matrix supposed full row rank and the IPC holds, the parameter system (2) has a unique solution for each $\mathrm{0}<t\le t_{\mathrm{0}}$${}^{[\mathrm{18}]}$. It is denoted as $(\mathit{x}(t),\mathit{y}(t),\mathit{s}(t))$ and we call it the $t$-center of the special wLCP (1). The collection $\left\{(\mathit{x}(t),\mathit{y}(t),\mathit{s}(t))|t>\mathrm{0}\right\}$ gives a homotopy path, which is called the central path of the special wLCP (1). Furthermore, if $t\to \mathrm{0}$, then $\mathit{\omega } (t)\to \mathit{\omega }$, so the optimal solution to the special wLCP (1) is obtained.

To determine the search direction of the algorithm, we use the Newton method for solving the system (2), where the search direction $(\mathrm{\Delta }\mathit{x},\mathrm{\Delta }\mathit{y},\mathrm{\Delta }\mathit{s})$ satisfies the following system

$\{\begin{array}{l}\mathit{A}\mathrm{\Delta }\mathit{x}=\mathrm{0}, \mathit{x}\ge \mathrm{0}\\ {\mathit{A}}^{\mathrm{T}}\mathrm{\Delta }\mathit{y}+\mathrm{\Delta }\mathit{s}=\mathrm{0} , \mathit{s}\ge \mathrm{0}\\ \mathit{s}\mathrm{\Delta }\mathit{x}+\mathit{x}\mathrm{\Delta }\mathit{s}=\mathit{\omega }(t)-\mathit{x}\mathit{s} \end{array}$(3)

Define

$\mathit{\upsilon }=\sqrt[]{\frac{\mathit{x}\mathit{s}}{\mathit{\omega }(t)}}, {\mathit{d}}_x=\frac{\mathit{\upsilon } \mathrm{\Delta }\mathit{x}}{\mathit{x}}, {\mathit{d}}_s=\frac{\mathit{\upsilon } \mathrm{\Delta }\mathit{s}}{\mathit{s}}$(4)

then (3) is equivalent to the following scale system

$\{\begin{array}{l}\overline{\mathit{A}}{\mathit{d}}_x=\mathrm{0} \\ {\mathit{W}}^{-\mathrm{1}}(t){\overline{\mathit{A}}}^{\mathrm{T}}\mathrm{\Delta }\mathit{y}+{\mathit{d}}_s=\mathrm{0} \\ {\mathit{d}}_x+{\mathit{d}}_s={\mathit{\upsilon }}^{-\mathrm{1}}-\mathit{\upsilon } \end{array}$(5)

where $\overline{\mathit{A}}≔\mathit{A}{\mathit{V}}^{-\mathrm{1}}\mathit{X},\mathit{V}=\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(\mathit{\upsilon }),\mathit{X}≔\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(\mathit{x}),\mathit{W}(t)≔$$\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{g}(\mathit{\omega }(t))$.

Definition 1   ${}^{[\mathrm{4}]}$A twice differentiable function $\psi (t):{\mathbb{R}}_{++}\to {\mathbb{R}}_{+}$ is called a kernel function, if it satisfies the following conditions

$\psi (\mathrm{1})={\psi }^{\text{'}}(\mathrm{1})=\mathrm{0}$; ${\psi }^{″}(t)>\mathrm{0}, t>\mathrm{0}$; $\underset{t\to {\mathrm{0}}^{+}}{\mathrm{l}\mathrm{i}\mathrm{m}}\psi (t)=\underset{t\to +\mathrm{\infty }}{\mathrm{l}\mathrm{i}\mathrm{m}}\psi (t)=+\mathrm{\infty }$.

The barrier function $\Psi (\mathit{\upsilon })$ is determined by the kernel function $\psi (t)$ as below

$\Psi (\mathit{\upsilon })≔{\displaystyle \sum _{i=\mathrm{1}}^n}\psi ({\mathit{\upsilon }}_i)$(6)

Note that the right of the third equation in system (5) is the negative gradient of the barrier function

${\Psi }_{\mathrm{1}}(\mathit{\upsilon })={\displaystyle \sum _{i=\mathrm{1}}^n}(\frac{{\mathit{\upsilon }}_i^{\mathrm{2}}-\mathrm{1}}{\mathrm{2}}-\mathrm{l}\mathrm{o}\mathrm{g}{\mathit{\upsilon }}_i)$(7)

Obviously, for the barrier function ${\Psi }_{\mathrm{1}}(\mathit{\upsilon })$, its corresponding kernel function is the classical logarithmic kernel function ${\psi }_{\mathrm{1}}(t)=(t^{\mathrm{2}}-\mathrm{1})/\mathrm{2}-\mathrm{l}\mathrm{o}\mathrm{g}t$.

The approach in this paper differs only one detail: we replace ${\Psi }_{\mathrm{1}}(\mathit{\upsilon })$ with a new barrier function $\Psi (\mathit{\upsilon })$, and the system (5) can be rewritten as

$\{\begin{array}{l}\overline{\mathit{A}}{\mathit{d}}_x=\mathrm{0} \\ {\mathit{W}}^{-\mathrm{1}}(t){\overline{\mathit{A}}}^{\mathrm{T}}\mathrm{\Delta }\mathit{y}+{\mathit{d}}_s=\mathrm{0} \\ {\mathit{d}}_x+{\mathit{d}}_s=-\nabla \Psi (\mathit{\upsilon })\end{array}$(8)

where $\Psi (\mathit{\upsilon })$ corresponds to the kernel function as $\psi (t)≔\mathrm{2}(t-\mathrm{1})-\mathrm{2}\mathrm{l}\mathrm{o}\mathrm{g}t$. Thus, the third equations in (8) is ${\mathit{d}}_x+{\mathit{d}}_s=\mathrm{2}({\mathit{\upsilon }}^{-\mathrm{1}}-\mathit{e})$, so the system (8) becomes

$\{\begin{array}{l}\overline{\mathit{A}}{\mathit{d}}_x=\mathrm{0} \\ {\mathit{W}}^{-\mathrm{1}}(t){\overline{\mathit{A}}}^{\mathrm{T}}\mathrm{\Delta }\mathit{y}+{\mathit{d}}_s=\mathrm{0} \\ {\mathit{d}}_x+{\mathit{d}}_s=\mathrm{2}({\mathit{\upsilon }}^{-\mathrm{1}}-\mathit{e})\end{array}$(9)

Defines proximity measure as follows

$\delta (\mathit{x},\mathit{s};\mathit{\omega } (t))≔\delta (\mathit{\upsilon })≔\frac{\mathrm{1}}{\mathrm{2}}\Vert \mathit{\upsilon }\left({\mathit{d}}_x+{\mathit{d}}_s\right)\Vert =\Vert \mathit{\upsilon }-\mathit{e}\Vert$(10)

Note 1 The kernel function $\psi (t)$ differs from the usual kernel function in that its growth term is linear in $t$. It was first introduced in Ref. [14] and was used to determine the iteration direction of the algorithm for LP.

Note 2 It is easy to verify that $\delta (\mathit{\upsilon })=\mathrm{0}\iff \mathit{\upsilon }=\mathit{e}\iff {\mathit{\upsilon }}^{\mathrm{2}}=\mathit{e}\iff \mathit{x}\mathit{s}=\mathit{\omega }(t)$. Therefore, $\delta (\mathit{\upsilon })$ can be used as a measure of iterate $(\mathit{x},\mathit{y},\mathit{s})$ to $t$-center of (2).

Note 3 In the existing literature, proximity measures are generally defined as $\delta (\mathit{\upsilon })≔\frac{\mathrm{1}}{\mathrm{2}}\Vert {\mathit{d}}_x+{\mathit{d}}_s\Vert$. However, in this paper we define a new norm-based proximity

$\delta (\mathit{\upsilon })≔\frac{\mathrm{1}}{\mathrm{2}}\Vert \mathit{\upsilon }\left({\mathit{d}}_x+{\mathit{d}}_s\right)\Vert =\Vert \mathit{\upsilon }-\mathit{e}\Vert$

This effectively simplifies the convergence analysis of the algorithm.

Now we outline the method. Select the appropriate parameter $\theta$ and any initial point ${\mathit{x}}^{\mathrm{0}}>\mathrm{0},{\mathit{s}}^{\mathrm{0}}>\mathrm{0},{\mathit{y}}^{\mathrm{0}}=\mathrm{0}$, let $\mathit{\omega } (t_{{}^{\mathrm{0}}})={\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}>\mathrm{0}$, for $t_{\mathrm{0}}=\mathrm{1}$. It is obvious that $\delta ({\mathit{x}}^{\mathrm{0}},{\mathit{s}}^{\mathrm{0}},\mathit{\omega }(t_{{}^{\mathrm{0}}}))=\mathrm{0}$ at the start of algorithm. Solve the system (9) and use (4) to obtain the search direction $(\mathrm{\Delta }\mathit{x},\mathrm{\Delta }\mathit{y},\mathrm{\Delta }\mathit{s})$, where $t_{+}≔(\mathrm{1}-\theta )t, \theta \in (\mathrm{0,1})$. The new iteration point is given by

${\mathit{x}}^{+}≔\mathit{x}+\mathrm{\Delta }\mathit{x}, {\mathit{y}}^{+}≔\mathit{y}+\mathrm{\Delta }\mathit{y}, {\mathit{s}}^{+}≔\mathit{s}+\mathrm{\Delta }\mathit{s}$(11)

that $({\mathit{x}}^{+},{\mathit{y}}^{+},{\mathit{s}}^{+})$is strictly feasible, namely $({\mathit{x}}^{+},{\mathit{y}}^{+},{\mathit{s}}^{+}) \in F^{\mathrm{0}}$ and satisfies

$\delta ({\mathit{x}}^{+},{\mathit{s}}^{+};\mathit{\omega } (t_{{}^{+}}))\le \frac{\mathrm{1}}{\mathrm{4}}{t}_{{}^{+}}$

If iteration point $(\mathit{x},\mathit{y},\mathit{s})$ satisfies condition $\Vert \mathit{x}\mathit{s}-\mathit{\omega }\Vert \le \epsilon$, then the algorithm iteration terminates.

A full-Newton step primal-dual IPM for the special wLCP is given as Algorithm 1.

Algorithm 1: A full-Newton step primal-dual IPM for wLCP

Input Accuracy parameter $\epsilon >0$; update parameter $\theta \in (\mathrm{0,1})$ let $({\mathit{x}}^0,{\mathit{y}}^0,{\mathit{s}}^0) \in F^0,$where $\delta ({\mathit{x}}^0,{\mathit{s}}^0;\mathit{\omega } (t_{{}^0}))\le \frac{1}{4}{t}_{{}^0}$ with $t_{{}^0}=1$; Set $k≔0$; begin $\mathit{x}≔{\mathit{x}}^0, \mathit{y}≔{\mathit{y}}^0, \mathit{s}≔{\mathit{s}}^0$;  while$\Vert \mathit{x}\mathit{s}-\mathit{\omega }\Vert >\epsilon$do   begin     obtain the search direction $(\mathrm{\Delta }\mathit{x},\mathrm{\Delta }\mathit{y},\mathrm{\Delta }\mathit{s})$ by solving the system (9) and using (4);    let ${\mathit{x}}^{+}≔\mathit{x}+\mathrm{\Delta }\mathit{x}, {\mathit{y}}^{+}≔\mathit{y}+\mathrm{\Delta }\mathit{y}, {\mathit{s}}^{+}≔\mathit{s}+\mathrm{\Delta }\mathit{s}$;     according to (17) below, get $\theta$;    set $t≔(1-\theta ) t, \mathit{\omega } (t)=t {\mathit{x}}^0{\mathit{s}}^0+(1-t) \mathit{\omega }$;$k≔k+1$;    end end

2 Analysis of the Algorithm

We start with some technical lemmas that play a key role in subsequent complexity analysis.

Lemma 1   ${}^{[\mathrm{2}]}$ Let $\mathit{u},\mathit{\upsilon }\in {\mathbb{R}}^n$, $\mathit{u}$ and $\mathit{\upsilon }$ are orthogonal. Then

${\Vert \mathit{u}\mathit{\upsilon }\Vert }_{\mathrm{\infty }}\le \frac{\mathrm{1}}{\mathrm{4}}{\Vert \mathit{u}+\mathit{\upsilon }\Vert }^{\mathrm{2}}, \Vert \mathit{u}\mathit{\upsilon }\Vert \le \frac{\sqrt[]{\mathrm{2}}}{\mathrm{4}}{\Vert \mathit{u}+\mathit{\upsilon }\Vert }^{\mathrm{2}}$

A basic property of the proximal measure $\delta (\mathit{\upsilon })$ is easily obtained by (10).

Lemma 2   Let $\delta (\mathit{\upsilon })≔\Vert \mathit{\upsilon }-\mathit{e}\Vert$. Then $\mathrm{1}-\delta (\mathit{\upsilon })\le {\mathit{\upsilon }}_i\le \mathrm{1}+\delta (\mathit{\upsilon }), i=\mathrm{1,2},\cdots ,n$.

From the system (9), we may get ${{\mathit{d}}_x}^{\mathrm{T}}{\mathit{d}}_s=\mathrm{0}$. Since, according to (9), Lemma 1 and Lemma 2, we derive that

${\Vert {\mathit{d}}_x{\mathit{d}}_s\Vert }_{\mathrm{\infty }}\le \frac{\mathrm{1}}{\mathrm{4}}{\Vert {\mathit{d}}_x+{\mathit{d}}_s\Vert }^{\mathrm{2}}=\frac{\mathrm{1}}{\mathrm{4}}{\Vert \mathrm{2}({\mathit{\upsilon }}^{-\mathrm{1}}-\mathit{e})\Vert }^{\mathrm{2}}={\Vert {\mathit{\upsilon }}^{-\mathrm{1}}-\mathit{e}\Vert }^{\mathrm{2}}={\Vert \frac{\mathit{\upsilon }-\mathit{e}}{\mathit{\upsilon }}\Vert }^{\mathrm{2}}\le {\left(\frac{\delta (\mathit{\upsilon })}{\mathrm{1}-\delta (\mathit{\upsilon })}\right)}^{\mathrm{2}}$(12)

In the same way, we also deduce that

$\Vert {\mathit{d}}_x{\mathit{d}}_s\Vert \le \sqrt[]{\mathrm{2}}{\left(\frac{\delta (\mathit{\upsilon })}{\mathrm{1}-\delta (\mathit{\upsilon })}\right)}^{\mathrm{2}}$(13)

Lemma 3   Let $\delta (\mathit{\upsilon })<\frac{\mathrm{1}}{\mathrm{2}}$. Then iteration points $({\mathit{x}}^{+},{\mathit{y}}^{+},{\mathit{s}}^{+})$ is strictly feasible, i.e., $({\mathit{x}}^{+},{\mathit{y}}^{+},{\mathit{s}}^{+}) \in F^{\mathrm{0}}$.

Proof   Consider the step size $\alpha \in [\mathrm{0,1}]$ and define

$\mathit{x}(\alpha ) ≔\mathit{x}+\alpha \mathrm{\Delta }\mathit{x}, \mathit{y}(\alpha ) ≔\mathit{y}+\alpha \mathrm{\Delta }\mathit{y}, \mathit{s}(\alpha ) ≔\mathit{s}+\alpha \mathrm{\Delta }\mathit{s}$

According to (4) and the system of equations (9), it follows that

$\mathit{x}(\alpha )\mathit{s}(\alpha )=\mathit{x}\mathit{s}+\alpha (\mathit{s}\mathrm{\Delta }\mathit{x}+\mathit{x}\mathrm{\Delta }\mathit{s})+{\alpha }^{\mathrm{2}}\mathrm{\Delta }\mathit{x}\mathrm{\Delta }\mathit{s}=\mathit{\omega }(t)[{\mathit{\upsilon }}^{\mathrm{2}}+\mathrm{2}\alpha (\mathit{e}-\mathit{\upsilon })+{\alpha }^{\mathrm{2}}{\mathit{d}}_x{\mathit{d}}_s]\ge \mathit{\omega }(t)[\alpha {\mathit{\upsilon }}^{\mathrm{2}}+\mathrm{2}\alpha (\mathit{e}-\mathit{\upsilon })+{\alpha }^{\mathrm{2}}{\mathit{d}}_x{\mathit{d}}_s]$

Due to the fact that $\mathrm{m}\mathrm{i}\mathrm{n}[{\mathit{\upsilon }}^{\mathrm{2}}+\mathrm{2}(\mathit{e}-\mathit{\upsilon })+\alpha {\mathit{d}}_x{\mathit{d}}_s]=\mathrm{m}\mathrm{i}\mathrm{n}[{(\mathit{\upsilon }-\mathit{e})}^{\mathrm{2}}+\mathit{e}+\alpha {\mathit{d}}_x{\mathit{d}}_s]$, $\mathit{\omega }(t)>\mathrm{0},$ and it follows from (12) that

$\mathit{x}(\alpha )\mathit{s}(\alpha )>\mathrm{0},\mathrm{i}\mathrm{f}\delta (\mathit{\upsilon })<\frac{\mathrm{1}}{\mathrm{2}}.$

Because $\mathit{x}(\alpha ), \mathit{s}(\alpha )$ are both linear function of $\alpha$ and $\mathit{x}(\mathrm{0})=\mathit{x}>\mathrm{0}, \mathit{s}(\mathrm{0})=\mathit{s}>\mathrm{0}$, this implies that $\mathit{x}(\alpha )>\mathrm{0} , \mathit{s}(\alpha )>\mathrm{0}$ for each $\alpha \in [\mathrm{0,1}]$. Correspondingly, we can get ${\mathit{x}}^{+}=\mathit{x}(\mathrm{1})>\mathrm{0}, {\mathit{s}}^{+}= \mathit{s}(\mathrm{1})>\mathrm{0}$. Hence, $({\mathit{x}}^{+},{\mathit{y}}^{+},{\mathit{s}}^{+})$ is strictly feasible. This completes the proof.

Lemma 4   Let ${\mathit{\upsilon }}_{+}≔\sqrt[]{\frac{{\mathit{x}}^{+}{\mathit{s}}^{+}}{\mathit{\omega }(t)}}$. Then

$\Vert ({\mathit{\upsilon }}_{+}{)}^{\mathrm{2}}\Vert \le {\delta }^{\mathrm{2}}(\mathit{\upsilon })+\sqrt[]{n}+\sqrt[]{\mathrm{2}}{\left(\frac{\delta (\mathit{\upsilon })}{\mathrm{1}-\delta (\mathit{\upsilon })}\right)}^{\mathrm{2}}.$

Proof   By following the proof of Lemma 3 and (13), we get

$\Vert ({\mathit{\upsilon }}_{+}{)}^{\mathrm{2}}\Vert =\Vert {\mathit{\upsilon }}^{\mathrm{2}}-\mathrm{2}\mathit{\upsilon }+\mathrm{2}\mathit{e}+{\mathit{d}}_x{\mathit{d}}_s\Vert =\Vert \mathit{e}+{(\mathit{\upsilon }-\mathit{e})}^{\mathrm{2}}+{\mathit{d}}_x{\mathit{d}}_s\Vert \le {\delta }^{\mathrm{2}}(\mathit{\upsilon })+\sqrt[]{n}+\sqrt[]{\mathrm{2}}{\left(\frac{\delta (\mathit{\upsilon })}{\mathrm{1}-\delta (\mathit{\upsilon })}\right)}^{\mathrm{2}}$

This completes the proof.

Lemma 5   Let ${\mathit{\upsilon }}_{+}≔\sqrt[]{\frac{{\mathit{x}}^{+}{\mathit{s}}^{+}}{\mathit{\omega }(t)}}$. Then the following inequality holds: $\Vert \mathit{e}-({\mathit{\upsilon }}_{+}{)}^{\mathrm{2}}\Vert \le \left[\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\delta (\mathit{\upsilon })\right)}^{\mathrm{2}}}\right]{\delta }^{\mathrm{2}}(\mathit{\upsilon })$.

Proof   According to the proof of Lemma 3 and (13), we have

$\begin{array}{l}\Vert \mathit{e}-({\mathit{\upsilon }}_{+}{)}^{\mathrm{2}}\Vert =\Vert \mathit{e}-\frac{\mathit{x}(\mathrm{1})\mathit{s}(\mathrm{1})}{\mathit{\omega }(t)}\Vert =\Vert \mathit{e}-[{\mathit{\upsilon }}^{\mathrm{2}}-\mathrm{2}\mathit{\upsilon }+\mathrm{2}\mathit{e}+{\mathit{d}}_x{\mathit{d}}_s]\Vert =\Vert -{(\mathit{\upsilon }-\mathit{e})}^{\mathrm{2}}-{\mathit{d}}_x{\mathit{d}}_s]\Vert \\ =\Vert {(\mathit{\upsilon }-\mathit{e})}^{\mathrm{2}}+{\mathit{d}}_x{\mathit{d}}_s]\Vert \le {\Vert \mathit{\upsilon }-\mathit{e}\Vert }^{\mathrm{2}}+\Vert {\mathit{d}}_x{\mathit{d}}_s\Vert \le \left[\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\delta (\mathit{\upsilon })\right)}^{\mathrm{2}}}\right]{\delta }^{\mathrm{2}}(\mathit{\upsilon }).\end{array}$

This completes the proof of the lemma.

The following lemma gives the local quadratic convergence of proximity measure.

Lemma 6   Let $\delta (\mathit{\upsilon })=\delta (\mathit{x},\mathit{s};\mathit{\omega }(t))<\frac{\mathrm{1}}{\mathrm{2}}$ with $n\ge \mathrm{2}$. Then $\delta ({\mathit{x}}^{+},{\mathit{s}}^{+};\mathit{\omega }(t))\le \left(\mathrm{4}+\frac{\sqrt[]{\mathrm{2}}}{\mathrm{2}}\right) {\delta }^{\mathrm{2}}(\mathit{\upsilon })$.

Proof   By the definition of $\delta (\mathit{\upsilon })$, we have

$\delta ({\mathit{x}}^{+},{\mathit{s}}^{+};\mathit{\omega }(t))≔\Vert {\mathit{\upsilon }}_{{}^{+}}-\mathit{e}\Vert =\Vert \frac{({\mathit{\upsilon }}_{{}^{+}}{)}^{\mathrm{2}}-\mathit{e}}{{\mathit{\upsilon }}_{{}^{+}}+\mathit{e}}\Vert \le \frac{\Vert ({\mathit{\upsilon }}_{{}^{+}}{)}^{\mathrm{2}}-\mathit{e}\Vert }{\Vert \mathit{e}\Vert }\le \frac{\Vert ({\mathit{\upsilon }}_{{}^{+}}{)}^{\mathrm{2}}-\mathit{e}\Vert }{\sqrt[]{n}}\le \frac{\Vert ({\mathit{\upsilon }}_{{}^{+}}{)}^{\mathrm{2}}-\mathit{e}\Vert }{\sqrt[]{\mathrm{2}}}$

from Lemma 5, we derive

$\delta ({\mathit{x}}^{+},{\mathit{s}}^{+};\mathit{\omega }(t))\le \frac{\mathrm{1}}{\sqrt[]{\mathrm{2}}}\left[\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\delta (\mathit{\upsilon })\right)}^{\mathrm{2}}}\right]{\delta }^{\mathrm{2}}(\mathit{\upsilon })\le \frac{\mathrm{1}}{\sqrt[]{\mathrm{2}}}\left[\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{(\mathrm{1}-\frac{\mathrm{1}}{\mathrm{2}})}^{\mathrm{2}}}\right]{\delta }^{\mathrm{2}}(\mathit{\upsilon })=\left(\mathrm{4}+\frac{\sqrt[]{\mathrm{2}}}{\mathrm{2}}\right){\delta }^{\mathrm{2}}(\mathit{\upsilon })$

This completes the proof.

Lemma 7   Let ${\mathit{\upsilon }}^{{}_{+}}≔\sqrt[]{\frac{{\mathit{x}}^{+}{\mathit{s}}^{+}}{\mathit{\omega }(t_{+})}}$ and $\delta ({\mathit{\upsilon }}^{{}_{+}})≔\Vert \mathit{e}-{\mathit{\upsilon }}^{{}_{+}}\Vert$. Then

$\delta ({\mathit{\upsilon }}^{{}_{+}})<\left[\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\delta (\mathit{\upsilon })\right)}^{\mathrm{2}}}\right]{\delta }^{\mathrm{2}}(\mathit{\upsilon })+\theta tK\left[\left(\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\delta (\mathit{\upsilon })\right)}^{\mathrm{2}}}\right){\delta }^{\mathrm{2}}(\mathit{\upsilon })+\sqrt[]{n}\right]$

where $K=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\mathrm{m}\mathrm{a}\mathrm{x}\left(\frac{{\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}}{\mathit{\omega }}\right), \mathrm{m}\mathrm{a}\mathrm{x}\left(\frac{\mathit{\omega }}{{\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}}\right)\right\}-\mathrm{1}.$

Proof   From the definition of$\mathit{\omega }(t)$, we can get $\mathit{\omega }(t_{{}^{+}})= \mathit{\omega }(t)+\theta t(\mathit{\omega }-{\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}})$, which implies

$\Vert \mathit{e}-({\mathit{\upsilon }}^{{}_{+}}{)}^{\mathrm{2}}\Vert \le \Vert \mathit{e}-\frac{{\mathit{x}}^{+}{\mathit{s}}^{+}}{\mathit{\omega }(t)}\Vert +\Vert \frac{{\mathit{x}}^{+}{\mathit{s}}^{+}}{\mathit{\omega }(t)}-\frac{{\mathit{x}}^{+}{\mathit{s}}^{+}}{\mathit{\omega }(t_{+})}\Vert \le \Vert \mathit{e}-({\mathit{\upsilon }}_{{}^{{}_{+}}}{)}^{\mathrm{2}}\Vert +\Vert \frac{{\mathit{x}}^{+}{\mathit{s}}^{+}}{\mathit{\omega }(t)}\cdot \frac{\theta t(\mathit{\omega }-{\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}})}{\mathit{\omega }(t_{+})}\Vert \le \Vert \mathit{e}-({\mathit{\upsilon }}_{{}^{{}_{+}}}{)}^{\mathrm{2}}\Vert +\theta t{\Vert \frac{\mathit{\omega }-{\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}}{\mathit{\omega }(t_{+})}\Vert }_{\mathrm{\infty }}\cdot \Vert ({\mathit{\upsilon }}_{{}^{{}_{+}}}{)}^{\mathrm{2}}\Vert$

It follows from Lemma 4 and Lemma 5 that

$\delta ({\mathit{\upsilon }}^{{}_{+}})=\Vert \frac{\mathit{e}-({\mathit{\upsilon }}^{{}_{+}}{)}^{\mathrm{2}}}{\mathit{e}+{\mathit{\upsilon }}^{{}_{+}}}\Vert \le \Vert \frac{\mathit{e}-({\mathit{\upsilon }}^{{}_{+}}{)}^{\mathrm{2}}}{\mathrm{1}+\mathrm{m}\mathrm{i}\mathrm{n}({\mathit{\upsilon }}^{{}_{+}})}\Vert \le \Vert \mathit{e}-({\mathit{\upsilon }}^{{}_{+}}{)}^{\mathrm{2}}\Vert \le \left[\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\delta (\mathit{\upsilon })\right)}^{\mathrm{2}}}\right]\cdot {\delta }^{\mathrm{2}}(\mathit{\upsilon })+\theta t{\Vert \frac{\mathit{\omega }-{\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}}{\mathit{\omega }(t_{+})}\Vert }_{\mathrm{\infty }}\cdot \left[{\delta }^{\mathrm{2}}(\mathit{\upsilon })+\sqrt[]{n}+\frac{\sqrt[]{\mathrm{2}}{\delta }^{\mathrm{2}}(\mathit{\upsilon })}{{\left(\mathrm{1}-\delta (\mathit{\upsilon })\right)}^{\mathrm{2}}}\right]$

And note that ${\Vert \frac{\mathit{\omega }-{\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}}{\mathit{\omega }(t_{+})}\Vert }_{\mathrm{\infty }}\le K$, we obtain

$\delta ({\mathit{\upsilon }}^{{}_{+}})<\left[\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\delta (\mathit{\upsilon })\right)}^{\mathrm{2}}}\right]{\delta }^{\mathrm{2}}(\mathit{\upsilon })+\theta tK\left[\left(\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\delta (\mathit{\upsilon })\right)}^{\mathrm{2}}}\right){\delta }^{\mathrm{2}}(\mathit{\upsilon })+\sqrt[]{n}\right]$

This completes the proof of the lemma.

Lemma 8   Let $\theta =\frac{\mathrm{1}-\left[\frac{\mathrm{1}}{\mathrm{4}}+\frac{\mathrm{4}\sqrt[]{\mathrm{2}}}{{(\mathrm{4}-t)}^{\mathrm{2}}}\right]t}{\mathrm{1}+\left[\frac{t^{\mathrm{2}}}{\mathrm{4}}+\frac{\mathrm{4}\sqrt[]{\mathrm{2}}{t}^{\mathrm{2}}}{{(\mathrm{4}-t)}^{\mathrm{2}}}+\mathrm{4}\sqrt[]{n}\right]K}, t\in (\mathrm{0,1})$. If $\delta (\mathit{\upsilon })\le \frac{\mathrm{1}}{\mathrm{4}}t$, then $\delta ({\mathit{\upsilon }}^{+})\le \frac{\mathrm{1}}{\mathrm{4}}{t}_{+}$.

Proof   By Lemma 7, we have

$\delta ({\mathit{\upsilon }}^{{}_{+}})<\left[\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\delta (\mathit{\upsilon })\right)}^{\mathrm{2}}}\right]{\delta }^{\mathrm{2}}(\mathit{\upsilon })+\theta tK\left[\left(\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\delta (\mathit{\upsilon })\right)}^{\mathrm{2}}}\right){\delta }^{\mathrm{2}}(\mathit{\upsilon })+\sqrt[]{n}\right]$(14)

Since the right-hand side is monotonically increasing with respect to $\delta (\mathit{\upsilon })$, then, for $\delta (\mathit{\upsilon })\le \frac{\mathrm{1}}{\mathrm{4}}t$ with $t\in (\mathrm{0,1})$, one has

$\delta ({\mathit{\upsilon }}^{{}_{+}})<\left[\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\frac{t}{\mathrm{4}}\right)}^{\mathrm{2}}}\right]{\left(\frac{t}{\mathrm{4}}\right)}^{\mathrm{2}}+\theta tK\left[\left(\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\frac{t}{\mathrm{4}}\right)}^{\mathrm{2}}}\right){\left(\frac{t}{\mathrm{4}}\right)}^{\mathrm{2}}+\sqrt[]{n}\right]$(15)

To guarantee $\delta ({\mathit{\upsilon }}^{+})\le \frac{\mathrm{1}}{\mathrm{4}}{t}_{+}$, the inequality (15) implies that it suffices to have

$\left[\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\frac{t}{\mathrm{4}}\right)}^{\mathrm{2}}}\right]{\left(\frac{t}{\mathrm{4}}\right)}^{\mathrm{2}}+\theta tK\left[\left(\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\frac{t}{\mathrm{4}}\right)}^{\mathrm{2}}}\right){\left(\frac{t}{\mathrm{4}}\right)}^{\mathrm{2}}+\sqrt[]{n}\right]\le \frac{\mathrm{1}}{\mathrm{4}}{t}^{+}$(16)

where $t^{+}=(\mathrm{1}-\theta ) t, \theta \in (\mathrm{0,1})$.

From (16), we obtain

$\theta \le \frac{\mathrm{1}-\left[\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\frac{t}{\mathrm{4}}\right)}^{\mathrm{2}}}\right]\frac{t}{\mathrm{4}}}{\mathrm{1}+\mathrm{4}K\left[\left(\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\frac{t}{\mathrm{4}}\right)}^{\mathrm{2}}}\right){\left(\frac{t}{\mathrm{4}}\right)}^{\mathrm{2}}+\sqrt[]{n}\right]}=\frac{\mathrm{1}-\left[\frac{\mathrm{1}}{\mathrm{4}}+\frac{\mathrm{4}\sqrt[]{\mathrm{2}}}{{(\mathrm{4}-t)}^{\mathrm{2}}}\right]t}{\mathrm{1}+\left[\frac{t^{\mathrm{2}}}{\mathrm{4}}+\frac{\mathrm{4}\sqrt[]{\mathrm{2}}{t}^{\mathrm{2}}}{{(\mathrm{4}-t)}^{\mathrm{2}}}+\mathrm{4}\sqrt[]{n}\right]K}, t\in (\mathrm{0,1})$

At this stage, we choose $\theta =\frac{\mathrm{1}-\left[\frac{\mathrm{1}}{\mathrm{4}}+\frac{\mathrm{4}\sqrt[]{\mathrm{2}}}{{(\mathrm{4}-t)}^{\mathrm{2}}}\right]t}{\mathrm{1}+\left[\frac{t^{\mathrm{2}}}{\mathrm{4}}+\frac{\mathrm{4}\sqrt[]{\mathrm{2}}{t}^{\mathrm{2}}}{{(\mathrm{4}-t)}^{\mathrm{2}}}+\mathrm{4}\sqrt[]{n}\right]K}, t\in (\mathrm{0,1})$, then (16) holds. This completes the proof.

3 Iterative Complexity Boundary

Let

$\theta =\frac{\mathrm{1}-\left[\frac{\mathrm{1}}{\mathrm{4}}+\frac{\mathrm{4}\sqrt[]{\mathrm{2}}}{{(\mathrm{4}-t)}^{\mathrm{2}}}\right]t}{\mathrm{1}+\left[\frac{t^{\mathrm{2}}}{\mathrm{4}}+\frac{\mathrm{4}\sqrt[]{\mathrm{2}}{t}^{\mathrm{2}}}{{(\mathrm{4}-t)}^{\mathrm{2}}}+\mathrm{4}\sqrt[]{n}\right]K}$(17)

where $t\in \left(\mathrm{0,1}\right),K=\mathrm{m}\mathrm{a}\mathrm{x}\left\{\mathrm{m}\mathrm{a}\mathrm{x}\left(\frac{{\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}}{\mathit{\omega }}\right), \mathrm{m}\mathrm{a}\mathrm{x}\left(\frac{\mathit{\omega }}{{\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}}\right)\right\}-\mathrm{1}$.

Due to $t_{\mathrm{0}}=\mathrm{1}, \mathit{\omega } (t_{{}^{\mathrm{0}}})={\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}$, we obtain $\delta ({\mathit{x}}^{\mathrm{0}}, {\mathit{s}}^{\mathrm{0}}, \mathit{\omega }(t_{{}^{\mathrm{0}}}))=\mathrm{0}<\frac{\mathrm{1}}{\mathrm{4}}{t}_{\mathrm{0}}$. Note that $t_{+}≔(\mathrm{1}-\theta )t, \theta \in (\mathrm{0,1})$. Lemma 3 and Lemma 8 show the new iteration point $({\mathit{x}}^{+},{\mathit{y}}^{+},{\mathit{s}}^{+})$ obtained after full-Newton step is strictly feasible, and

$\delta ({\mathit{x}}^{+},{\mathit{s}}^{+};\mathit{\omega }(t_{{}^{+}}))\le \frac{\mathrm{1}}{\mathrm{4}}{t}_{{}^{+}}$

Next, we will discuss the iteration complexity of the algorithm. We first examine the value of the "dual gap".

Lemma 9   Assume that the parameters $\theta , K$ are defined as in (17). If $\delta (\mathit{\upsilon })\le \frac{\mathrm{1}}{\mathrm{4}}t$, then

$\Vert {\mathit{x}}^{+}{\mathit{s}}^{+}-\mathit{\omega }\Vert \le \left[\left(\frac{\mathrm{1}}{\mathrm{16}}+\frac{\sqrt[]{\mathrm{2}}}{\mathrm{9}}\right)\cdot {\Vert \mathit{\omega }(t)\Vert }_{\mathrm{\infty }}+{\Vert {\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}-\mathit{\omega }\Vert }_{}\right]t$

Proof   From Lemma 5, we obtain

$\Vert {\mathit{x}}^{+}{\mathit{s}}^{+}-\mathit{\omega }\Vert \le \Vert {\mathit{x}}^{+}{\mathit{s}}^{+}-\mathit{\omega }(t)\Vert +\Vert \mathit{\omega }(t)-\mathit{\omega }\Vert t\le \Vert \mathit{\omega }(t)\left(({\mathit{\upsilon }}_{{}^{{}_{+}}}{)}^{\mathrm{2}}-\mathit{e}\right)\Vert +\Vert {\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}-\mathit{\omega }\Vert t\le {\Vert \mathit{\omega }(t)\Vert }_{\mathrm{\infty }}\cdot \left[\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\delta (\mathit{\upsilon })\right)}^{\mathrm{2}}}\right]{\delta }^{\mathrm{2}}(\mathit{\upsilon })+\Vert {\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}-\mathit{\omega }\Vert t$

Therefore, if $\delta (\mathit{\upsilon })\le \frac{\mathrm{1}}{\mathrm{4}}t$, then

$\Vert {\mathit{x}}^{+}{\mathit{s}}^{+}-\mathit{\omega }\Vert \le {\Vert \mathit{\omega }(t)\Vert }_{\mathrm{\infty }}\cdot \left[\mathrm{1}+\frac{\sqrt[]{\mathrm{2}}}{{\left(\mathrm{1}-\frac{t}{\mathrm{4}}\right)}^{\mathrm{2}}}\right]{\left(\frac{t}{\mathrm{4}}\right)}^{\mathrm{2}}+\Vert {\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}-\mathit{\omega }\Vert t\le \left[\left(\frac{\mathrm{1}}{\mathrm{16}}+\frac{\sqrt[]{\mathrm{2}}}{\mathrm{9}}\right){\Vert \mathit{\omega }(t)\Vert }_{\mathrm{\infty }}+\Vert {\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}-\mathit{\omega }\Vert \right]t$

This completes the proof.

Based on the previous discussion, the iteration bound is given by the following theorem:

Theorem 1   Assume that the parameters $\theta , K$ are defined as in (17). If the special wLCP (1) is strictly feasible, then Algorithm 1 finds an $\epsilon$-approximate solution of the special wLCP (1) after at most

$\lceil \frac{\mathrm{1}+\mathrm{4}K\sqrt[]{n}+\frac{K}{\mathrm{4}}+\frac{\sqrt[]{\mathrm{2}}K}{\mathrm{9}}}{\frac{\mathrm{3}}{\mathrm{4}}-\frac{\mathrm{4}\sqrt[]{\mathrm{2}}}{\mathrm{9}}}\cdot \mathrm{l}\mathrm{o}\mathrm{g}\frac{\left(\frac{\mathrm{1}}{\mathrm{16}}+\frac{\sqrt[]{\mathrm{2}}}{\mathrm{9}}\right)\mathrm{m}\mathrm{a}\mathrm{x}\left\{\mathrm{m}\mathrm{a}\mathrm{x}\left({\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}\right), \mathrm{m}\mathrm{a}\mathrm{x}\left(\mathit{\omega }\right)\right\}+{\Vert {\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}-\mathit{\omega }\Vert }_{}}{\epsilon }\rceil$

iterations.

Proof   From ${\Vert \mathit{\omega }\left(t\right)\Vert }_{\mathrm{\infty }}\le \mathrm{m}\mathrm{a}\mathrm{x}\left\{\mathrm{m}\mathrm{a}\mathrm{x}\left({\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}\right), \mathrm{m}\mathrm{a}\mathrm{x}\left(\mathit{\omega }\right)\right\}$ and Lemma 9, we obtain

$\begin{array}{l}\Vert {\mathit{x}}^k{\mathit{s}}^k-\mathit{\omega }\Vert \le \left(\left(\frac{\mathrm{1}}{\mathrm{16}}+\frac{\sqrt[]{\mathrm{2}}}{\mathrm{9}}\right)\mathrm{m}\mathrm{a}\mathrm{x}\left\{\mathrm{m}\mathrm{a}\mathrm{x}\left({\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}\right), \mathrm{m}\mathrm{a}\mathrm{x}\left(\mathit{\omega }\right)\right\}+{\Vert {\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}-\mathit{\omega }\Vert }_{}\right)t_{k-\mathrm{1}}\\ \le \left(\left(\frac{\mathrm{1}}{\mathrm{16}}+\frac{\sqrt[]{\mathrm{2}}}{\mathrm{9}}\right)\mathrm{m}\mathrm{a}\mathrm{x}\left\{\mathrm{m}\mathrm{a}\mathrm{x}\left({\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}\right), \mathrm{m}\mathrm{a}\mathrm{x}\left(\mathit{\omega }\right)\right\}+{\Vert {\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}-\mathit{\omega }\Vert }_{}\right)(\mathrm{1}-{\theta }_{\mathrm{m}\mathrm{i}\mathrm{n}}{)}^{k-\mathrm{1}}{t}_{\mathrm{0}}\end{array}$

According to (17), we get

${\theta }_{\mathrm{m}\mathrm{i}\mathrm{n}}=\frac{\frac{\mathrm{3}}{\mathrm{4}}-\frac{\mathrm{4}\sqrt[]{\mathrm{2}}}{\mathrm{9}}}{\mathrm{1}+\mathrm{4}K\sqrt[]{n}+\frac{K}{\mathrm{4}}+\frac{\sqrt[]{\mathrm{2}}K}{\mathrm{9}}}$

Using the same method as Theorem 5.1 in Ref. [17], it is easy to get the upper bound of the number of iterations of the algorithm as

$\lceil \frac{\mathrm{1}+\mathrm{4}K\sqrt[]{n}+\frac{K}{\mathrm{4}}+\frac{\sqrt[]{\mathrm{2}}K}{\mathrm{9}}}{\frac{\mathrm{3}}{\mathrm{4}}-\frac{\mathrm{4}\sqrt[]{\mathrm{2}}}{\mathrm{9}}}\cdot \mathrm{l}\mathrm{o}\mathrm{g}\frac{\left(\frac{\mathrm{1}}{\mathrm{16}}+\frac{\sqrt[]{\mathrm{2}}}{\mathrm{9}}\right)\mathrm{m}\mathrm{a}\mathrm{x}\left\{\mathrm{m}\mathrm{a}\mathrm{x}\left({\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}\right), \mathrm{m}\mathrm{a}\mathrm{x}\left(\mathit{\omega }\right)\right\}+{\Vert {\mathit{x}}^{\mathrm{0}}{\mathit{s}}^{\mathrm{0}}-\mathit{\omega }\Vert }_{}}{\epsilon }\rceil$

This completes the proof.

4 Numerical Examples

This section presents several numerical experiments to show the effectiveness of the algorithm. The numerical results are obtained by using MATLAB 2014b on an Intel Core i5 (3.10 GHz) with 4 GB RAM.

Throughout all experiments, we set the precision parameter $\epsilon ={\mathrm{10}}^{-\mathrm{5}}$. Six kinds of the special wLCPs with different sizes are randomly generated. In detail, we generate a random six matrices $\mathit{A}\in {\mathbb{R}}^{m\times n}$ with full rows rank, a random weighted vectors $\mathit{\omega }>\mathrm{0}$. We take the initial point $({\mathit{x}}^{\mathrm{0}},{\mathit{y}}^{\mathrm{0}},{\mathit{s}}^{\mathrm{0}}) \in F^{\mathrm{0}}$, and $\theta , K$ are defined as in (17). The CPU time in second (Time), the number of iterations (Iter) are shown in Table 1 as follows.

• For the special wLCP of the same scale, the number of iterations and the runtime are positively correlated with the upper bound of $K$;

• When the upper bound of $K$ is fixed, we observe a positive correlation between the number of iterations and the runtime with the scale of the special wLCP, specifically with the problem size parameters $m$ and $n$;

• As the size parameters $m$ and $n$ increase, the number of iterations does not significantly increase, suggesting that the algorithm is well-suited for efficiently solving large-scale the special wLCP problems.

5 Conclusion

In this paper, a full-Newton step IPM for wLCP based on a kernel function is proposed. Applying this function to the central path, new search directions for wLCP are obtained. The analysis of wLCP is more complicated than LCP because of the nonzero weight vector. We prove the feasibility and convergence of Algorithm 1. Numerical results indicate the efficiency of our algorithm.

References