A Full-Newton Step Infeasible Interior-Point Method for the Special Weighted Linear Complementarity Problem

Abstract

As an extension of the complementarity problem (CP), the weighted complementarity problem (wCP) is a large class of equilibrium problems with wide applications in science, economics, and engineering. If the weight vector is zero, the wCP reduces to a CP. In this paper, we present a full-Newton step infeasible interior-point method (IIPM) for the special weighted linear complementarity problem over the nonnegative orthant. One iteration of the algorithm consists of one feasibility step followed by a few centering steps. All of them are full-Newton steps, and hence, no calculation of the step size is necessary. The iteration bound of the algorithm is as good as the best-known polynomial complexity of IIPMs for linear optimization.

1 Introduction

In 2012, Potra [22] first introduced the notion of a weighted complementarity problem (wCP), which consists of finding a pair of vectors (x, s) belonging to the intersection of a manifold and a cone, such that the product of the vectors in a certain algebra equals a given weight vector w. If w is the zero vector, wCP reduces to a complementarity problem (CP) [22]. A wCP can be applied to a large variety of equilibrium problems from science, economics, and engineering. For example, the Fisher market equilibrium problem can be reformulated as a weighted linear complementarity problem (wLCP) model and can be solved more efficiently as a wLCP than a nonlinear CP model [22]. The linear programming and weighted centering (LPWC) problem proposed by Anstreicher [2] reduces to a monotone wLCP as well [23]. Moreover, wCP can be used to model equilibrium problems in atmospheric chemistry [1, 6, 16] and multibody dynamics [10, 21, 29].

Potra [22] introduced and analyzed two interior-point methods (IPMs) for the monotone wLCP. In 2016, Potra [23] gave some fundamental results about sufficient wLCP and proposed a corrector–predictor IPM to solve it. Based on a parametric smoothing function, Zhang [31] considered a smoothing Newton algorithm for wLCP. Tang [28] proposed a variant nonmonotone smoothing algorithm with improved numerical results for large-scale wLCP. Chi, Gowda, and Tao [7] established some existence and uniqueness results of the weighted horizontal linear complementarity problem (wHLCP) on a Euclidean Jordan algebra. Asadi et al. [3] presented the first full-Newton step IPM for the monotone wLCP and derived the best iteration bound obtained for these types of problems.

IPMs for linear optimization (LO) were initiated by the work of Karmarkar [13]. These IPMs have polynomial complexity and often perform with high efficiency in practice. One may distinguish between feasible IPMs and infeasible IPMs (IIPMs). IIPMs start with an arbitrary positive point, and their feasibility is reached as optimality is approached. IIPMs were first presented by Lustig [18] and Tanabe [27], respectively. The primal–dual full-Newton step feasible IPM for LO was first analyzed by Roos et al. in [26] and was later extended to IIPM by Roos in [24]. Assuming that an optimal solution exists, it shows that at most O(n) iterations suffice to reduce the duality gap and the residuals by a factor $1-\theta$, where $\theta \in (0,1)$ is a barrier update parameter [24]. In addition, Darvay [8] proposed a new full-Newton step feasible IPM for LO based on the equivalent algebraic transformation of the central path. Subsequently, a series of full-step IPMs are considered for various optimization problems and complementarity problems, see, e.g., LO [5, 9, 11, 25], semidefinite optimization (SDO) [14, 19], symmetric optimization (SO) [12], linear complementarity problems (LCP) [20], horizontal linear complementarity problems (HLCP) [15, 17], and the Cartesian $P_*(\kappa )$-HLCP over symmetric cones (the Cartesian $P_*(\kappa )$-SCHLCP) [4].

Motivated by the recent work of Potra and Roos [22, 24], in this paper, we present a full-Newton step IIPM for the special wLCP that can start from an arbitrary “large" positive point. The algorithm is based on only using full-Newton steps, and hence, there is no need for a line search at each iteration. The iteration bound of the algorithm is as good as the best-known polynomial complexity of IIPMs for LO.

Conventions. Let ${\mathbf {R}}, {\mathbf {R}}_{+}$ and ${\mathbf {R}}_{++}$ denote the set of real, nonnegative real, and positive real numbers, respectively. The 2-norm and the infinity norm are denoted by $\Vert \cdot \Vert$ and $\Vert \cdot \Vert _{\infty },$ respectively. The symbol e represents the vector of all-ones with dimension n. $\log _{2}\varrho$ is the logarithm of $\varrho ,$ with 2 as the base. We denote the componentwise operations on vectors by the usual notation for real numbers. Thus, if $x,s\in {\mathbf {R}}^{n},$ xs,  $\dfrac{x}{s},$ etc., will denote the vectors with components $x_{i}s_{i},$ $\dfrac{x_{i}}{s_{i}},$ etc., respectively, for $i=1,2,\ldots ,n.$ For a vector $u\in {\mathbf {R}}^{n},$ we denote by $\min u=\min \{u_{i}:i=1,\ldots ,n\}.$

2 Special wLCP

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

$$\begin{aligned} \left\{ \begin{array}{ll} Ax=b, \quad x\ge 0,\\ A^{T}y+s=c, \quad s\ge 0,\\ xs=w. \end{array} \right. \end{aligned}$$

(1)

Here, $A\in {\mathbf {R}}^{m\times n}$ is a given matrix, $b\in {\mathbf {R}}^{m}$ and $c\in {\mathbf {R}}^{n}$ are given vectors, and $w\in {\mathbf {R}}^{n}_{+}$ is a given weight vector (the data of the problem). Systems of the type (1) have appeared in IPMs for LO.

The special wLCP (1) is called feasible (or strictly feasible) if ${\mathcal {F}}\ne \emptyset$ (or ${\mathcal {F}}^{0}\ne \emptyset$ ), where

$$\begin{aligned} {\mathcal {F}}=\{z=(x,s,y)\in {\mathbf {R}}^{n}_{+}\times {\mathbf {R}}^{n}_{+}\times {\mathbf {R}}^{m}: Ax=b,\, A^{T}y+s=c\}, \end{aligned}$$

and

$$\begin{aligned} {\mathcal {F}}^{0}=\{z=(x,s,y)\in {\mathbf {R}}^{n}_{++}\times {\mathbf {R}}^{n}_{++}\times {\mathbf {R}}^{m}: Ax=b,\, A^{T}y+s=c\}. \end{aligned}$$

The solution set of the special wLCP (1) is given by

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

Throughout this paper, we make the following assumptions:

(i) ${\mathcal {F}}^{0}\ne \emptyset ;$

(ii) the matrix A has full row rank.

Let

$$\begin{aligned} P=\left( \begin{array}{c} A\\ 0 \end{array}\right) ,\quad Q=\left( \begin{array}{c} 0\\ I \end{array}\right) ,\quad R=\left( \begin{array}{c} 0\\ A^{T} \end{array}\right) ,\quad a=\left( \begin{array}{c} b\\ c \end{array}\right) . \end{aligned}$$

Then, (1) can be written as the following wHLCP

$$\begin{aligned} \left\{ \begin{array}{ll} Px+Qs+Ry=a,\\ xs=w,\\ x\ge 0,\quad s\ge 0, \end{array} \right. \end{aligned}$$

(2)

with a given weight vector $w\in {\mathbf {R}}^{n}_{+}$. Since the triplet (P, Q, R) is skew-symmetric [22] and wLCP (2) is strictly feasible by assumption (i), it follows from Theorem 4 in [23] that the special wLCP (1) is solvable.

3 Full-Newton Step IIPM for the Special wLCP

Choose an arbitrary starting point $z^{0}:=(x^{0},s^{0},y^{0})$ with $x^{0}>0,$ $s^{0}>0,$ such that $x^{0}s^{0}=w^{0}$ for some vector $w^{0}>0.$ Let

$$\begin{aligned} t_{0}= & {} \frac{(x^{0})^{T}(s^{0})}{n}, \end{aligned}$$

(3)

$$\begin{aligned} w(t)= & {} \left( 1-\frac{t}{t_{0}}\right) w+\frac{t}{t_{0}}w^{0},\quad t\in (0,t_{0}]. \end{aligned}$$

(4)

Replacing the weighted complementarity condition $xs=w$ by a centering condition in the special wLCP (1) yields

$$\begin{aligned} \left\{ \begin{array}{ll} Ax=b, \quad x\ge 0,\\ A^{T}y+s=c, \quad s\ge 0,\\ xs=w(t), \end{array} \right. \end{aligned}$$

(5)

where w(t) is given by (4) with $t\in (0,t_{0}].$ The solution of (5) is called the $t-$center of the special wLCP (1), and the set of all the $t-$centers is called the central path of the special wLCP (1). Since the algorithm under consideration is an IIPM, we apply Newton’s method to the perturbed problem of (5) and find approximate solutions of the special wLCP (1).

Denote the initial residual vectors $r^{0}_{b}$ and $r^{0}_{c}$, respectively, as

$$\begin{aligned} \begin{array}{l} r^{0}_{b}:=b-Ax^{0},\\ r^{0}_{c}:=c-A^{T}y^{0}-s^{0}. \end{array} \end{aligned}$$

For any $0<\nu \le 1,$ we consider the perturbed problem ($\hbox {wLCP}_{\nu }$) of the special wLCP (1) as follows

$$\begin{aligned} \left\{ \begin{array}{ll} b-Ax=\nu r^{0}_{b}, &{}x\ge 0,\\ c-A^{T}y-s=\nu r^{0}_{c},&{}s\ge 0,\\ xs=w. \end{array} \right. \end{aligned}$$

(6)

Lemma 3.1

The original wLCP (1) is feasible, i.e., ${\mathcal {F}}\ne \emptyset ,$ if and only if for any $\nu$ satisfying $0<\nu \le 1$ the perturbed problem $\hbox {wLCP}_{\nu }$ (6) satisfies the interior-point condition (IPC), i.e., $\hbox {wLCP}_{\nu }$ (6) has a feasible solution $(x(\nu ),s(\nu ),y(\nu ))$ with $x(\nu )>0$ and $s(\nu )>0.$

Proof

Using the same argument as Theorem 5.13 in [30], we obtain the desired result. $\square$

We define the infeasible central path of $\hbox {wLCP}_{\nu }$ (6) emanating from $z^{0}$ as the set of all points $(t,z)=(t,x,s,y)$ with $t\in (0,t_{0}]$, satisfying

$$\begin{aligned} \left\{ \begin{array}{ll} b-Ax=\nu r^{0}_{b}, &{}x\ge 0,\\ c-A^{T}y-s=\nu r^{0}_{c},&{}s\ge 0,\\ xs=w(t). \end{array} \right. \end{aligned}$$

(7)

By Proposition 3 in [23] and Lemma 3.1, (7) is strictly feasible with the skew-symmetric triplet (P, Q, R) and has a unique solution $(x(t,\nu ),s(t,\nu ),y(t,\nu ))$ for any $t\in (0,t_{0}].$

Note that since $x^{0}s^{0}=w^{0}=w(t_{0}),$ $z^{0}=(x^{0},s^{0},y^{0})$ is the $t_{0}-$center of the perturbed problem $\hbox {wLCP}_{1}$ (6), i.e., $(x(t_{0},1),s(t_{0},1),y(t_{0},1))=(x^{0},s^{0},y^{0}).$ In the following analysis, the parameters t and $\nu$ always satisfy $t=\nu t_{0}.$

To measure proximity of iterate (x, s, y) to the $t-$center of $\hbox {wLCP}_{\nu }$, we define the norm-based proximity measure as follows

$$\begin{aligned} \delta (x,s;t):=\delta (v):=\frac{1}{2}\Vert v-v^{-1}\Vert , \quad \text {where} \quad v:=\sqrt{\frac{xs}{w(t)}}. \end{aligned}$$

(8)

It is obvious that $\delta (x^{0},s^{0};t_{0})=0$ at the start of the algorithm.

By extending the feasibility step for LO [24], we obtain the following linear system in the search direction $({\varDelta }^{f}x, {\varDelta }^{f}s, {\varDelta }^{f}y)$ for the special wLCP (1):

$$\begin{aligned} \left\{ \begin{array}{ll} A{\varDelta }^{f} x=\theta \nu r^{0}_{b}, \quad x\ge 0,\\ A^{T}{\varDelta }^{f} y+{\varDelta }^{f} s=\theta \nu r^{0}_{c}, \quad s\ge 0,\\ s{\varDelta }^{f} x+x{\varDelta }^{f} s=w(t)-xs, \end{array} \right. \end{aligned}$$

(9)

with $\theta \in (0,1).$ Since A has full row rank, the system (9) uniquely defines $({\varDelta }^{f}x, {\varDelta }^{f}s, {\varDelta }^{f}y)$ for any $x>0$ and $s>0.$ The iterate after the feasibility step is given by

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

(10)

which satisfy the first two equations of the system (7), with $\nu$ replaced by $\nu _{+}=(1-\theta )\nu .$

In a centering step, the search direction $({\varDelta } x, {\varDelta } s, {\varDelta } y)$ is (uniquely) defined by

$$\begin{aligned} \left\{ \begin{array}{l} A{\varDelta } x=0, \quad x\ge 0,\\ A^{T}{\varDelta } y+{\varDelta } s=0, \quad s\ge 0,\\ s{\varDelta } x+x{\varDelta } s=w(t)-xs, \end{array} \right. \end{aligned}$$

(11)

which is the usual Newton search direction for feasible primal–dual IPMs. The new iterate after a centering step is given by

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

(12)

Now, we outline one main iteration of the full-Newton step IIPM. Suppose that for some $t\in (0, t_{0}]$ and a threshold parameter $\tau \in (0,1)$, we have an iterate (x, s, y) satisfying the feasibility conditions, i.e., the first two equations in (6) for $\nu = t/t_{0}$, and such that $\Vert w(t)-w\Vert =\nu \Vert x^{0}s^{0}-w\Vert$ and $\delta (x,s;t)\le \tau$. We reduce both t and $\nu$ by a barrier parameter $\theta \in (0,1),$ i.e., $t_{+}=(1-\theta )t$ and $\nu _{+}=(1-\theta )\nu =t_{+}/t_{0}$. Then, we find a new iterate $(x^{+},s^{+},y^{+})$ that satisfies the first two equations in (6), with $\nu$ replaced by $\nu _{+}$, and such that $\Vert w(t_{+})-w\Vert =\nu _{+}\Vert x^{0}s^{0}-w\Vert$ and $\delta (x^{+},s^{+};t_{+})\le \tau$.

More precisely, each main iteration consists of a feasibility step followed by several centering steps. The feasibility step moves from $\hbox {wLCP}_{\nu }$ to $\hbox {wLCP}_{\nu _{+}}$, which is strictly feasible for $\hbox {wLCP}_{\nu _{+}}$ and close to its $t_{+}$-center $(x(t_{+},\nu _{+}),s(t_{+},$ $\nu _{+}),y(t_{+},\nu _{+}))$. In fact, the feasibility step $(x^{f},s^{f},y^{f})$ is designed in such a way that $\delta (x^{f},s^{f};t_{+})\le \frac{1}{\sqrt{2}}$, i.e., $(x^{f},s^{f},y^{f})$ belongs to the quadratic convergence neighborhood with respect to the $t_{+}$-center of $\hbox {wLCP}_{\nu _{+}}$ (see Lemma 3.2). The centering steps are then performed in $\hbox {wLCP}_{\nu _{+}}$ starting from $(x^{f},s^{f},y^{f})$ until the $\tau$-neighborhood is reached, i.e., we can get a new iterate $(x^{+},s^{+},y^{+})$ that is strictly feasible for $\hbox {wLCP}_{\nu _{+}}$ and satisfies $\delta (x^{+},s^{+};t_{+})\le \tau <\frac{1}{\sqrt{2}}$. An algorithmic description of our method is given in Fig. 1.

Fig. 1

The algorithm

The following lemma describes the effect on $\delta (x,s;t)$ of a centering step, which will play an important role in the analysis of Algorithm 3.1. Its proof is similar to the proof of Theorem II.50 in [26].

Lemma 3.2

If $\delta :=\delta (x,s;t)\le 1,$ then the primal–dual Newton step is feasible, i.e., $x^{+}$ and $s^{+}$ are nonnegative. Moreover, if $\delta :=\delta (x,s;t)\le \dfrac{1}{\sqrt{2}},$ then $\delta (x^{+},s^{+};t)\le \delta ^{2}.$

In fact, the feasibility step is designed such that $\delta (x^{f},s^{f};t_{+})\le \dfrac{1}{\sqrt{2}},$ i.e., the iterate $(x^{f},s^{f},y^{f})$ is within the region where the Newton process targeting at the $t_{+}-$center of $\hbox {wLCP}_{\nu _{+}}$ is quadratically convergent. After k centering steps, we will have feasible iterate $(x^{+},s^{+};t_{+})$ for $\hbox {wLCP}_{\nu _{+}}$ satisfying

$$\begin{aligned} \delta (x^{+},s^{+};t_{+})\le \left( \frac{1}{\sqrt{2}}\right) ^{2^{k}}\le \tau , \end{aligned}$$

which implies

$$\begin{aligned} k\ge \log _{2}\left( \log _{2}\frac{1}{\tau ^{2}}\right) . \end{aligned}$$

Assuming $\tau =\dfrac{1}{8},$ each main iteration consists of at most

$$\begin{aligned} \left( \log _{2}\frac{1}{\tau ^{2}}\right) +1=\log _{2}(\log _{2}64)+1\le 4 \end{aligned}$$

(13)

inner iterations.

Remark 3.1

Since in each iteration all the residuals $\Vert w(t)-w\Vert ,\Vert b-Ax\Vert$ and $\Vert c-A^{T}y-s\Vert$ are reduced by the same rate $1-\theta$, we expect that we can get iterate (x, s, y; t) such that

$$\begin{aligned} \max \{\Vert w(t)-w\Vert ,\Vert b-Ax\Vert ,\Vert c-A^{T}y-s\Vert \}\le \varepsilon . \end{aligned}$$

If $\delta (x,s;t)>\varepsilon$ still holds, then after one feasibility step and one update of t and $\nu$, we have $\delta (x^{f},s^{f};t_{+})\le \dfrac{1}{\sqrt{2}}.$ It follows from Lemma 3.2 that by performing a few centering steps starting from $(x^{f},s^{f},y^{f})$ until $\delta (x^{+},s^{+};t_{+})\le \varepsilon ,$ Algorithm 3.1 finds an $\varepsilon -$solution of the special wLCP (1).

4 Analysis of the Algorithm

In this section, we first analyze the feasibility of the full-Newton step. Then, we establish an upper bound for $\omega (v)$ defined by (16). Finally, the polynomial complexity of Algorithm 3.1 is derived.

4.1 Analysis of the Feasibility Step

At the beginning of the feasibility step, we have an iterate (x, s, y) that is strictly feasible for $\hbox {wLCP}_{\nu }$ (6), with $\nu = t/t_{0}$, such that $\Vert w(t)-w\Vert =\nu \Vert x^{0}s^{0}-w\Vert$ and $\delta (x,s;t)\le \tau <\frac{1}{\sqrt{2}}$. We reduce t and $\nu$ to $t_{+}=(1-\theta )t$ and $\nu _{+}=(1-\theta )\nu$, respectively, with $\theta \in (0,1)$. As we established in Sect. 3, the feasibility step produces a new iterate $(x^{f},s^{f},y^{f})$, which satisfies $\Vert w(t_{+})-w\Vert =\nu _{+}\Vert x^{0}s^{0}-w\Vert$ and is feasible for $\hbox {wLCP}_{\nu _{+}}$, except possibly the nonnegative constraints. The crucial element in the analysis is to show that with a proper choice of the values of the parameter $\theta$, both $x^{f}$ and $s^{f}$ are positive such that $\delta (x^{f},s^{f};t_{+})\le \frac{1}{\sqrt{2}}$.

Define

$$\begin{aligned} d_{x}:=\dfrac{v{\varDelta }^{f}x}{x}, \quad d_{s}:=\dfrac{v{\varDelta }^{f}s}{s}. \end{aligned}$$

(14)

By (8), (9), (10) and (14), we have

$$\begin{aligned} \begin{array}{rl} x^{f}s^{f}&{}=(x+{\varDelta }^{f}x)(s+{\varDelta }^{f}s)\\ &{}=xs+(s{\varDelta }^{f}x+x{\varDelta }^{f}s)+{\varDelta }^{f}x{\varDelta }^{f}s\\ &{}=w(t)+\dfrac{xs}{v^{2}}d_{x}d_{s}\\ &{}=w(t)(e+d_{x}d_{s}). \end{array} \end{aligned}$$

(15)

The following lemma provides the sufficient and necessary condition for the strict feasibility of the new iterate $(x^{f},s^{f},y^{f})$.

Lemma 4.1

(Lemma 4.1 in [24]) The iterate $(x^{f},s^{f},y^{f})$ is strictly feasible if and only if $e+d_{x}d_{s}>0.$

From Lemma 4.1, we can easily obtain the following corollary, which yields a sufficient condition for the strict feasibility of the new iterate $(x^{f},s^{f},y^{f})$.

Corollary 4.1

The iterate $(x^{f},s^{f},y^{f})$ is strictly feasible if $\Vert d_{x}d_{s}\Vert _{\infty }<1.$

Let

$$\begin{aligned} \omega (v):=\frac{1}{2}\sqrt{\Vert d_{x}\Vert ^{2}+\Vert d_{s}\Vert ^{2}}. \end{aligned}$$

(16)

Then, we have $\Vert d_{x}\Vert \le 2\omega (v),$ $\Vert d_{s}\Vert \le 2\omega (v),$ and

$$\begin{aligned}&d_{x}^{T}d_{s}\le \Vert d_{x}\Vert \Vert d_{s}\Vert \le 2\omega (v)^{2}, \end{aligned}$$

(17)

$$\begin{aligned}&\Vert d_{x}d_{s}\Vert _{\infty }\le \Vert d_{x}\Vert \Vert d_{s}\Vert \le 2\omega (v)^{2}. \end{aligned}$$

(18)

From Corollary 4.1 and (18), we obtain another sufficient condition, which depends on $\omega (v)$, for the strict feasibility of the new iterate $(x^{f},s^{f},y^{f})$.

Lemma 4.2

If $\omega (v)<\dfrac{1}{\sqrt{2}},$ then the iterate $(x^{f},s^{f},y^{f})$ is strictly feasible.

Since $t_{+}=(1-\theta )t,$ it follows from (4) that

$$\begin{aligned} \begin{array}{rl} w(t_{+})&{}=[1-{t(1-\theta )}/{t_{0}}]w+[{t(1-\theta )}/{t_{0}}]w^{0}-\theta w+\theta w\\ &{}=(1-\theta )w(t)+\theta w. \end{array} \end{aligned}$$

(19)

Using (8), we get

$$\begin{aligned} \delta (x^{f},s^{f};t_{+}):=\delta (v^{f}):=\frac{1}{2}\Vert v^{f}-\frac{e}{v^{f}}\Vert , \quad \text {where} \quad v^{f}:=\sqrt{\frac{x^{f}s^{f}}{w(t_{+})}}. \end{aligned}$$

(20)

Due to Lemma 4.2, the assumption $\omega (v)<\dfrac{1}{\sqrt{2}}$ guarantees strict feasibility of the iterate $(x^{f},s^{f},y^{f})$. Now, we derive an upper bound for $\delta (x^{f},s^{f};t_{+}).$

Lemma 4.3

If $\omega (v)<\dfrac{1}{\sqrt{2}},$ then the following inequality holds

$$\begin{aligned} 4\delta (v^{f})^{2} \le \dfrac{2\omega (v)^{2}}{1-\theta }+(1-\theta ) {\varOmega } +\theta E {\varOmega } +\theta ^{2}n G, \end{aligned}$$

(21)

where

$$\begin{aligned} {\varOmega }:= & {} \dfrac{2\omega (v)^{2}}{1-2\omega (v)^{2}}, \end{aligned}$$

(22)

$$\begin{aligned} E:= & {} \max \limits _{1\le i\le n}\left\{ 1,\dfrac{w_{i}}{w^{0}_{i}}\right\} , \end{aligned}$$

(23)

$$\begin{aligned} F:= & {} \max \limits _{1\le i\le n}\left\{ \left( \dfrac{w^{0}_{i}}{w_{i}}-1\right) ^{2},\left( 1-\dfrac{w_{i}}{w^{0}_{i}}\right) ^{2}, \dfrac{1}{1-\theta }\right\} . \end{aligned}$$

(24)

Proof

See Appendix. $\square$

By choosing the suitable parameter $\theta$, the following lemma guarantees that the new iterate $(x^{f},s^{f},y^{f})$ is strictly feasible and satisfies $\delta (v^{f})\le \dfrac{1}{\sqrt{2}}$.

Lemma 4.4

If $\omega (v)\le \dfrac{1}{2}$ and

$$\begin{aligned} 0\le \theta \le {\overline{\theta }}:=\frac{1}{\sqrt{(E-1)^{2}+2Fn+1}+E}\le \frac{1}{2}, \end{aligned}$$

(25)

where E is given by (23) and

$$\begin{aligned} F:= & {} \max \limits _{1\le i\le n}\left\{ \left( \frac{w^{0}_{i}}{w_{i}}-1\right) ^{2},\left( 1-\frac{w_{i}}{w^{0}_{i}}\right) ^{2}, 1\right\} , \end{aligned}$$

(26)

satisfying $Fn-E+1>0$, then the iterate $(x^{f},s^{f},y^{f})$ is strictly feasible and $\delta (v^{f})\le \dfrac{1}{\sqrt{2}}.$ Particularly, if $E=1$, then

$$\begin{aligned} 0<\theta <{\overline{\theta }}:=\frac{1}{\sqrt{2Fn+1}+1}. \end{aligned}$$

(27)

Proof

Since $\omega (v)\le \dfrac{1}{2}<\dfrac{1}{\sqrt{2}},$ it follows from Lemma 4.2 that the iterate $(x^{f},s^{f},y^{f})$ is strictly feasible. By (23), (26) and Lemma 4.3, $\delta (v^{f})\le \dfrac{1}{\sqrt{2}}$ holds if

$$\begin{aligned}&4\delta (v^{f})^{2}\le \dfrac{2\omega (v)^{2}}{1-\theta }+(1-\theta )\dfrac{2\omega (v)^{2}}{1-2\omega (v)^{2}} +\theta \max \limits _{1\le i\le n}\left\{ 1,\dfrac{w_{i}}{w^{0}_{i}}\right\} \dfrac{2\omega (v)^{2}}{1-2\omega (v)^{2}}\\&\qquad +\theta ^{2}n\max \limits _{1\le i\le n}\left\{ \left( \dfrac{w^{0}_{i}}{w_{i}}-1\right) ^{2}, \left( 1-\dfrac{w_{i}}{w^{0}_{i}}\right) ^{2},\dfrac{1}{1-\theta }\right\} \\&\quad \le \frac{1}{2(1-\theta )}+(1-\theta ) +\theta \max \limits _{1\le i\le n}\left\{ 1,\frac{w_{i}}{w^{0}_{i}}\right\} \\&\qquad +\frac{\theta ^{2}n}{1-\theta }\max \limits _{1\le i\le n}\left\{ \left( \frac{w^{0}_{i}}{w_{i}}-1\right) ^{2},\left( 1-\frac{w_{i}}{w^{0}_{i}}\right) ^{2},1\right\} \\&\quad \le \dfrac{1}{2(1-\theta )}+(1-\theta )+E\theta +\dfrac{Fn\theta ^{2}}{1-\theta }\\&\quad \le 2 \end{aligned}$$

for some $\theta \in (0,\frac{1}{2}].$ Then, it is sufficient to show that

$$\begin{aligned}&\dfrac{1}{2(1-\theta )}+(1-\theta )+E\theta +\dfrac{Fn\theta ^{2}}{1-\theta }\le 2\nonumber \\&\quad \Leftrightarrow 1+2(1-\theta )^{2}+2E\theta (1-\theta )+2Fn\theta ^{2}\le 4(1-\theta )\nonumber \\&\quad \Leftrightarrow 3-4\theta +2\theta ^{2}+2E\theta -2E\theta ^{2}+2Fn\theta ^{2}\le 4-4\theta \nonumber \\&\quad \Leftrightarrow 2(Fn-E+1)\theta ^{2}+2E\theta -1\le 0. \end{aligned}$$

(28)

By (23) and (26), we get $E\ge 1$, $F\ge 1$. Next, we only consider the case when $Fn-E+1>0$. Since

$$\begin{aligned} {\varDelta }=4E^{2}+8(Fn-E+1) =4(E-1)^{2}+8Fn+4>0, \end{aligned}$$

we have

$$\begin{aligned} \theta _{i}=\dfrac{-2E+(-1)^{i}\sqrt{{\varDelta }}}{4(Fn-E+1)}=\dfrac{-E+(-1)^{i}\sqrt{(E-1)^{2}+2Fn+1}}{2(Fn-E+1)} \end{aligned}$$

for $i=1,2,$ and (28) is equivalent to

$$\begin{aligned} \dfrac{-E-\sqrt{(E-1)^{2}+2Fn+1}}{2(Fn-E+1)}\le \theta \le \dfrac{-E+\sqrt{(E-1)^{2}+2Fn+1}}{2(Fn-E+1)}. \end{aligned}$$

Taking into account the fact that $\theta \in (0,1),$ we obtain

$$\begin{aligned} 0<\theta \le {\overline{\theta }}:= & {} \dfrac{-E+\sqrt{(E-1)^{2}+2Fn+1}}{2(Fn-E+1)}\\= & {} \dfrac{1}{\sqrt{(E-1)^{2}+2Fn+1}+E}\le \dfrac{1}{2}, \end{aligned}$$

which finishes the proof. $\square$

4.2 An Upper Bound for $\omega (v)$

To obtain an upper bound for $\omega (v)$, we consider the vectors $d_{x}$ and $d_{s}$. It follows from (8) and (14) that the system (9), which defines the search direction $({\varDelta }^{f}x, {\varDelta }^{f}s,$ ${\varDelta }^{f}y)$, can be expressed in terms of the scaled search directions $d_{x}$ and $d_{s}$ as follows

$$\begin{aligned} \left\{ \begin{array}{l} {\overline{A}}d_{x}=\theta \nu r^{0}_{b},\\ W(t)^{-1}{\overline{A}}^{T}{\varDelta }^{f}y+d_{s}=\theta \nu vs^{-1} r^{0}_{c},\\ d_{x}+d_{s}=v^{-1}-v, \end{array} \right. \end{aligned}$$

(29)

where $\theta \in (0,1)$ and

$$\begin{aligned} {\overline{A}}:=AV^{-1}X,\quad V:=\text {diag}(v),\quad X:=\text {diag}(x),\quad W(t):=\text {diag}(w(t)). \end{aligned}$$

By the above definition of ${\overline{A}}$, we have ${\overline{A}}=AD\sqrt{W(t)},$ where

$$\begin{aligned} D:=\text {diag}\left( \frac{x{{v}^{-1}}}{\sqrt{w(t)}}\right) =\text {diag}\left( \sqrt{\frac{x}{s}}\right) =\text {diag}\left( \sqrt{w(t)}v{{s}^{-1}}\right) . \end{aligned}$$

Then, the system (29) could be reformulated as

$$\begin{aligned} \left\{ \begin{array}{l} AD\sqrt{W(t)}d_{x}=\theta \nu r^{0}_{b},\\ (\sqrt{W(t)})^{-1}DA^{T}{\varDelta }^{f}y+d_{s}=\theta \nu vs^{-1} r^{0}_{c},\\ d_{x}+d_{s}=v^{-1}-v. \end{array} \right. \end{aligned}$$

(30)

Now, the orthogonality of the scaled search directions $\widetilde{d_{x}}$ and $\widetilde{d_{s}}$ defined by (31) immediately follows.

Lemma 4.5

Let $(\widetilde{d_{x}},\widetilde{d_{s}},\widetilde{{\varDelta }^{f}y})$ be the solution of the system

$$\begin{aligned} \left\{ \begin{array}{l} AD\sqrt{W(t)}\widetilde{d_{x}}=0,\\ (\sqrt{W(t)})^{-1}DA^{T}\widetilde{{\varDelta }^{f}y}+\widetilde{d_{s}}=0,\\ \widetilde{d_{x}}+\widetilde{d_{s}}={\widetilde{r}}, \end{array} \right. \end{aligned}$$

(31)

with ${\widetilde{r}}\in {\mathbf {R}}^{n}.$ Then, $\widetilde{d_{x}}^{T}\widetilde{d_{s}}=0.$

Proof

Let ${\widetilde{\xi }}:=-\widetilde{{\varDelta }^{f}y}.$ By eliminating $\widetilde{d_{s}}$ from the second relation in (31), we get

$$\begin{aligned} (\sqrt{W(t)})^{-1}DA^{T}{\widetilde{\xi }}+\widetilde{d_{x}}={\widetilde{r}}. \end{aligned}$$

(32)

Multiplying both sides of (32) from the left with $AD\sqrt{W(t)},$ it follows from the first relation in (31) that

$$\begin{aligned} AD^{2}A^{T}{\widetilde{\xi }}=AD\sqrt{W(t)}{\widetilde{r}}. \end{aligned}$$

Therefore,

$$\begin{aligned} {\widetilde{\xi }}=(AD^{2}A^{T})^{-1}AD\sqrt{W(t)}{\widetilde{r}}. \end{aligned}$$

Substituting it into (32) yields

$$\begin{aligned} \widetilde{d_{x}}={\widetilde{r}}-(\sqrt{W(t)})^{-1}DA^{T}(AD^{2}A^{T})^{-1}AD\sqrt{W(t)}{\widetilde{r}}=(I-P){\widetilde{r}}, \end{aligned}$$

(33)

where

$$\begin{aligned} P:=(\sqrt{W(t)})^{-1}DA^{T}(AD^{2}A^{T})^{-1}AD\sqrt{W(t)}. \end{aligned}$$

By (31) and (33), we have

$$\begin{aligned} \widetilde{d_{s}}={\widetilde{r}}-\widetilde{d_{x}}=P{\widetilde{r}}. \end{aligned}$$

(34)

It follows from the definition of P that

$$\begin{aligned} P(I-P)=P-\left[ (\sqrt{W(t)})^{-1}DA^{T}(AD^{2}A^{T})^{-1}AD\sqrt{W(t)}\right] ^{2}=O, \end{aligned}$$

which together with (33) and (34) implies $\widetilde{d_{x}}^{T}\widetilde{d_{s}}=0.$ This completes the proof. $\square$

Let

$$\begin{aligned} {\mathcal {L}}:=\{\eta \in {\mathbf {R}}^{n}: {\overline{A}}\eta =0\}. \end{aligned}$$

Then, the affine space $\{\eta \in {\mathbf {R}}^{n}: {\overline{A}}\eta =\theta \nu r^{0}_{b}\}$ equals $d_{x}+{\mathcal {L}}.$ It follows from Lemma 4.5, (29) and (30) that $d_{s}\in \theta \nu vs^{-1} r^{0}_{c}+{\mathcal {L}}^{\bot }.$ Since ${\mathcal {L}}\bigcap {\mathcal {L}}^{\bot }=\{0\},$ suppose that q is the unique solution of the system

$$\begin{aligned} \left\{ \begin{array}{ll} {\overline{A}}q=\theta \nu r^{0}_{b},\\ W(t)^{-1}{\overline{A}}^{T}\xi +q=\theta \nu vs^{-1} r^{0}_{c}. \end{array} \right. \end{aligned}$$

The following lemma provides an upper bound for $\omega (v)$ depending on $\Vert q\Vert$ and $\delta (v)$.

Lemma 4.6

(Lemma 4.6 in [24]) Let q be the unique point in the intersection of the affine spaces $d_{x}+{\mathcal {L}}$ and $d_{s}+{\mathcal {L}}^{\bot }.$ Then,

$$\begin{aligned} 2\omega (v)\le \sqrt{\Vert q\Vert ^{2}+(\Vert q\Vert +2\delta (v))^{2}}. \end{aligned}$$

Now, we derive an upper bound for $\Vert q\Vert .$ Suppose that $w>0$ in the following analysis.

Let $\zeta >0$ be a constant such that $\max \{\Vert x^{*}\Vert _{\infty }, \Vert s^{*}\Vert _{\infty }\}\le \zeta$ for some optimal solution $(x^{*},s^{*},y^{*})$ of the special wLCP (1), which implies

$$\begin{aligned} \zeta ^{2}\ge x^{*}_{i}s^{*}_{i}=w_{i}>0,\quad \text {for}\quad i=1,\ldots ,n. \end{aligned}$$

We start the algorithm with the specified initial point

$$\begin{aligned} x^{0}=s^{0}=\zeta e,\quad y^{0}=0. \end{aligned}$$

Then,

$$\begin{aligned} w^{0}=x^{0}s^{0}=\zeta ^{2}e>w,\quad t_{0}=\frac{(x^{0})^{T}(s^{0})}{n}=\zeta ^{2}, \end{aligned}$$

and

$$\begin{aligned} 0\le x^{0}-x^{*}\le x^{0}=\zeta e,\quad 0\le s^{0}-s^{*}\le s^{0}=\zeta e. \end{aligned}$$

Therefore, we obtain from (4), (23) and (26) that

$$\begin{aligned} \min w(t)= & {} \min \left[ \left( 1-\frac{t}{t_{0}}\right) w_{i}+\frac{t}{t_{0}}\zeta ^{2}\right] \ge \min w>0, \end{aligned}$$

(35)

$$\begin{aligned} w(\nu t_{0})= & {} \left( 1-\frac{\nu t_{0}}{t_{0}}\right) w+\frac{\nu t_{0}}{t_{0}}\zeta ^{2}e=(1-\nu )w+\nu \zeta ^{2}e, \end{aligned}$$

(36)

$$\begin{aligned} E= & {} \max \limits _{1\le i\le n}\left\{ 1,\frac{w_{i}}{\zeta ^{2}}\right\} =1, \end{aligned}$$

(37)

$$\begin{aligned} F= & {} \max \limits _{1\le i\le n}\left\{ \left( \frac{\zeta ^{2}}{w_{i}}-1\right) ^{2},\left( 1-\frac{w_{i}}{\zeta ^{2}}\right) ^{2}, 1\right\} =\max \limits _{1\le i\le n}\left\{ \left( \frac{\zeta ^{2}}{w_{i}}-1\right) ^{2}, 1\right\} . \nonumber \\ \end{aligned}$$

(38)

The following lemma provides an upper bound for $\Vert q\Vert$, which is important in the complexity analysis of Algorithm 3.1.

Lemma 4.7

The following inequality holds

$$\begin{aligned} \Vert q\Vert \le \theta \nu \zeta \sqrt{e^{T}\left( \dfrac{x}{sw(t)}+\dfrac{s}{xw(t)}\right) }. \end{aligned}$$

(39)

Proof

By following the proof of Lemma 4.7 in [24], we obtain the desired result. $\square$

Let $\tau =\dfrac{1}{8}$ and $\delta (v)\le \tau$ at the start of an iteration. By Corollary A.10 [24], we have

$$\begin{aligned} \sqrt{\frac{x}{s}}\le \sqrt{2}\frac{x(t,\nu )}{\sqrt{w(t)}},\quad \sqrt{\frac{s}{x}}\le \sqrt{2}\frac{s(t,\nu )}{\sqrt{w(t)}}. \end{aligned}$$

(40)

Substituting (40) into (39) yields

$$\begin{aligned} \Vert q\Vert \le \theta \nu \zeta \sqrt{2e^{T}\left( \frac{x(t,\nu )^{2}+s(t,\nu )^{2}}{w(t)^{2}}\right) }. \end{aligned}$$

(41)

By (27) and (37), we have

$$\begin{aligned} \theta =\dfrac{\alpha }{\sqrt{2Fn+1}+1} \le {\overline{\theta }}=\dfrac{1}{\sqrt{2Fn+1}+1} \end{aligned}$$

(42)

with $0<\alpha \le 1.$ Then, it follows from (35), (41) and (42) that

$$\begin{aligned} \Vert q\Vert&\le \dfrac{\theta \nu \zeta \sqrt{2e^{T}\left( x(t,\nu )^{2}+s(t,\nu )^{2}\right) }}{\min \limits _{ }w(t)}\nonumber \\&\le \dfrac{\alpha \nu \zeta \sqrt{2e^{T}\left( x(t,\nu )^{2}+s(t,\nu )^{2}\right) }}{(\sqrt{2Fn+1}+1)\min \limits _{ }w}\nonumber \\&=\dfrac{\alpha \nu \zeta \sqrt{2(\Vert x(t,\nu )\Vert ^{2}+\Vert s(t,\nu )\Vert ^{2})}}{(\sqrt{2Fn+1}+1)\min \limits _{}w}. \end{aligned}$$

(43)

Notice that $(x(t,\nu ),s(t,\nu ),y(t,\nu ))\in {\mathbf {R}}^{n}\times {\mathbf {R}}^{n}\times {\mathbf {R}}^{m}$ is the unique solution of the system

$$\begin{aligned} \left\{ \begin{array}{ll} b-Ax=\nu (b-A\zeta e), \quad x\ge 0,\\ c-A^{T}y-s=\nu (c-\zeta e), \quad s\ge 0,\\ xs=w(\nu t_{0}), \end{array} \right. \end{aligned}$$

where $w(\nu t_{0})$ is defined by (36) with $0<\nu \le 1.$ Then, by following the proof for the LO case in [24], we obtain $\Vert x(t,\nu )\Vert _{1}+\Vert s(t,\nu )\Vert _{1}\le \dfrac{2n\zeta }{\nu }.$ Combining the last inequality and (43) gives

$$\begin{aligned} \Vert q\Vert&\le \dfrac{\alpha \nu \zeta \sqrt{2(\Vert x(t,\nu )\Vert ^{2}+\Vert s(t,\nu )\Vert ^{2})}}{(\sqrt{2Fn+1}+1)\min \limits _{ }w}\nonumber \\&\le \dfrac{\sqrt{2}\alpha \nu \zeta (\Vert x(t,\nu )\Vert _{1}+\Vert s(t,\nu )\Vert _{1})}{(\sqrt{2Fn+1}+1)\min \limits _{ }w}\nonumber \\&\le \dfrac{2\sqrt{2}\alpha n\zeta ^{2}}{(\sqrt{2Fn+1}+1)\min \limits _{ }w}\nonumber \\&=\sqrt{2}\alpha \rho (\zeta ), \end{aligned}$$

(44)

where

$$\begin{aligned} \rho (\zeta ):=\frac{2n\zeta ^{2}}{(\sqrt{2Fn+1}+1)\min w}. \end{aligned}$$

(45)

4.3 Complexity Analysis

Recall from Lemma 4.4 that in order to guarantee that $\delta (v^{f})\le \dfrac{1}{\sqrt{2}},$ we want to have $\omega (v)\le \dfrac{1}{2}.$ By Lemma 4.6, this will be satisfied if

$$\begin{aligned} \Vert q\Vert ^{2}+(\Vert q\Vert +2\delta (v))^{2}\le 1. \end{aligned}$$

Taking into account the fact that $\delta (v)\le \tau =\dfrac{1}{8},$ we have $\delta (v^{f})\le \dfrac{1}{\sqrt{2}}$ if $\Vert q\Vert \le \dfrac{1}{2}.$ It follows from (44) that the latter inequality certainly holds if we take

$$\begin{aligned} \alpha :=\frac{1}{2\sqrt{2}\rho (\zeta )}. \end{aligned}$$

By (38), (42) and (45), direct calculations yield

$$\begin{aligned} \theta&=\dfrac{\alpha }{\sqrt{2Fn+1}+1}=\dfrac{1}{2\sqrt{2}(\sqrt{2Fn+1}+1)\rho (\zeta )}\\&=\dfrac{\min w}{4\sqrt{2}n\zeta ^{2}}\le \dfrac{1}{4\sqrt{2F}n}\\&<{\overline{\theta }}:=\dfrac{1}{\sqrt{2Fn+1}+1}, \end{aligned}$$

and

$$\begin{aligned} \frac{1}{\theta }:=\frac{4\sqrt{2}n\zeta ^{2}}{\min w}. \end{aligned}$$

(46)

The above discussion leads to the following main result, which provides an upper bound on the number of iterations for Algorithm 3.1.

Theorem 4.1

Assume that the special wLCP (1) is strictly feasible with $w>0,$ and A has full row rank. If $\zeta >0$ and $\max \{\Vert x^{*}\Vert _{\infty },$ $\Vert s^{*}\Vert _{\infty }\}\le \zeta$ for some optimal solution $(x^{*},s^{*},y^{*})$ of the special wLCP (1), then after at most

$$\begin{aligned} \left\lceil \frac{16\sqrt{2}n\zeta ^{2}}{\min w}\log \frac{\max \{\Vert \zeta ^{2}e-w\Vert ,\Vert r_{b}^{0}\Vert ,\Vert r_{c}^{0}\Vert \}}{\varepsilon }\right\rceil +\left\lceil \log _{2}\left( \log _{2}\frac{1}{\varepsilon ^{2}}\right) \right\rceil +1 \end{aligned}$$

(47)

iterations, Algorithm 3.1 finds an $\varepsilon -$solution of the special wLCP (1).

Proof

From (4), we have

$$\begin{aligned} \Vert w(t_{+})-w\Vert =\frac{t_{+}}{t_{0}}\Vert w^{0}-w\Vert =(1-\theta )\frac{t}{t_{0}}\Vert \zeta ^{2}e-w\Vert . \end{aligned}$$

Since at each iteration the norms of the residual vectors are also reduced by the factor $1-\theta ,$ we can find a solution such that $\max \{\Vert w(t)-w\Vert ,\Vert b-Ax\Vert ,\Vert c-A^{T}y-s\Vert \}\le \varepsilon$ after at most

$$\begin{aligned} \dfrac{1}{\theta }\log \dfrac{\max \left\{ \Vert \zeta ^{2}e-w\Vert ,\Vert r_{b}^{0}\Vert ,\Vert r_{c}^{0}\Vert \right\} }{\varepsilon } \end{aligned}$$

main iterations. It follows from (13) and (46) that the number of the inner iterations is bounded above by

$$\begin{aligned} \left\lceil \frac{16\sqrt{2}n\zeta ^{2}}{\min w}\log \frac{\max \{\Vert \zeta ^{2}e-w\Vert ,\Vert r_{b}^{0}\Vert ,\Vert r_{c}^{0}\Vert \}}{\varepsilon }\right\rceil . \end{aligned}$$

If $\delta (x,s;t)>\varepsilon$ still holds, after one feasibility step and k centering steps we have iterate $(x^{+},s^{+};t_{+})$ such that

$$\begin{aligned} \delta (x^{+},s^{+};t_{+})\le \left( \frac{1}{\sqrt{2}}\right) ^{2^{k}}\le \varepsilon , \end{aligned}$$

which gives the smallest integer

$$\begin{aligned} k:=\left\lceil \log _{2}\left( \log _{2}\frac{1}{\varepsilon ^{2}}\right) \right\rceil \ge \log _{2}\left( \log _{2}\frac{1}{\varepsilon ^{2}}\right) . \end{aligned}$$

Therefore, we obtain the desired complexity result (47). $\square$

Before starting Algorithm 3.1, it is important to choose the number $\zeta >0$ to determine the initial point $x^{0}=s^{0}=\zeta e, y^{0}=0.$ If the special wLCP (1) is solvable, there exists a binary input size L such that any optimal solution $(x^{*},s^{*},y^{*})$ of the special wLCP (1) satisfies $\max \{\Vert x^{*}\Vert _{\infty }, \Vert s^{*}\Vert _{\infty }\}\le 2^{L}.$ Thus, when starting the algorithm with $\zeta =2^{L},$ Algorithm 3.1 can find an $\varepsilon -$solution of the special wLCP (1) after at most

$$\begin{aligned} \left\lceil \frac{4^{L+2}\sqrt{2}n}{\min w}\log \dfrac{\max \left\{ \Vert 4^{L}e-w\Vert ,\Vert b-2^{L}Ae\Vert ,\Vert c-2^{L}e\Vert \right\} }{\varepsilon }\right\rceil +\left\lceil \log _{2}\left( \log _{2}\dfrac{1}{\varepsilon ^{2}}\right) \right\rceil +1 \end{aligned}$$

iterations.

5 Conclusions

We have proposed a full-Newton step IIPM for the special wLCP, which is a notion first introduced by Potra [22]. The algorithm generalizes the full-Newton step IIPM of Roos for LO [24] and possesses the following good properties. First, the algorithm can start from an arbitrary “large" positive point, without having to use another method to achieve a better-centered starting point. Second, we reduce the parameters t in the definition of the central path and $\nu$ in the definition of the feasibility residuals at the same rate for wLCP. Third, under suitable assumptions, the iterates always lie in the quadratic convergence neighborhood of the central path. Finally, the iteration bound of the algorithm is as good as the best-known result of IIPM for LO.

Proof of Lemma 4.3

By (15), (19) and (20), we have

$$\begin{aligned} (v^{f})^{2}=\frac{w(t)(e+d_{x}d_{s})}{w(t_{+})}=\frac{w(t)(e+d_{x}d_{s})}{(1-\theta )w(t)+\theta w}. \end{aligned}$$

Since $\omega (v)<\dfrac{1}{\sqrt{2}},$ we obtain from (18) that $\Vert d_{x}d_{s}\Vert _{\infty }\le 2\omega (v)^{2}<1,$ and hence $e+d_{x}d_{s}>0.$ By letting $u:=\sqrt{e+d_{x}d_{s}},$ we have $v^{f}=\sqrt{\dfrac{w(t)}{(1-\theta )w(t)+\theta w}}u.$ Then, from (20),

$$\begin{aligned} 4\delta (v^{f})^{2}= & {} \left\| \sqrt{\dfrac{w(t)}{(1-\theta )w(t)+\theta w}}u-\sqrt{\dfrac{(1-\theta )w(t)+\theta w}{w(t)}}u^{-1}\right\| ^{2}\\= & {} \left\| \dfrac{\theta (w(t)-w)}{\sqrt{w(t)[(1-\theta )w(t)+\theta w]}}u+\sqrt{\dfrac{(1-\theta )w(t)+\theta w}{w(t)}}(u-u^{-1})\right\| ^{2}\\= & {} \theta ^{2}e^{T}\left[ \dfrac{(w(t)-w)^{2}}{w(t)((1-\theta )w(t)+\theta w)}u^{2}\right] +e^{T}\left[ \dfrac{((1-\theta )w(t)+\theta w)}{w(t)}(u-u^{-1})^{2}\right] \\&+2\theta e^{T}\left[ \dfrac{(w(t)-w)}{w(t)}u(u-u^{-1})\right] . \end{aligned}$$

Taking into account the fact that $u^{2}=e+d_{x}d_{s},$ the three terms in the last relation can be written, respectively, as follows:

$$\begin{aligned}&\theta ^{2}e^{T}\left[ \dfrac{(w(t)-w)^{2}}{w(t)((1-\theta )w(t)+\theta w)}u^{2}\right] =\theta ^{2}e^{T}\left[ \dfrac{(w(t)-w)^{2}}{w(t)((1-\theta )w(t)+\theta w)}(e+d_{x}d_{s})\right] \\&\quad =\theta ^{2}e^{T}\left[ \dfrac{(w(t)-w)^{2}}{w(t)((1-\theta )w(t)+\theta w)}\right] +\theta ^{2}e^{T}\left[ \dfrac{(w(t)-w)^{2}}{w(t)((1-\theta )w(t)+\theta w)}d_{x}d_{s}\right] ,\\&e^{T}\left[ \dfrac{((1-\theta )w(t)+\theta w)}{w(t)}(u-u^{-1})^{2}\right] \\&\quad =e^{T}\left[ \dfrac{((1-\theta )w(t)+\theta w)}{w(t)}(u^{2}+u^{-2}-2e)\right] \\&\quad =e^{T}\left[ \dfrac{((1-\theta )w(t)+\theta w)}{w(t)}(d_{x}d_{s}+\dfrac{e}{e+d_{x}d_{s}}-e)\right] \\&\quad =e^{T}\left[ \dfrac{((1-\theta )w(t)+\theta w)}{w(t)}d_{x}d_{s}\right] +e^{T}\left[ \dfrac{((1-\theta )w(t)+\theta w)}{w(t)}\cdot \dfrac{e}{e+d_{x}d_{s}}\right] \\&\qquad -e^{T}\left[ \dfrac{(1-\theta )w(t)+\theta w}{w(t)}\right] , \end{aligned}$$

and

$$\begin{aligned}&2\theta e^{T}\left[ \dfrac{(w(t)-w)}{w(t)}u(u-u^{-1})\right] \\&\quad =2\theta e^{T}\left[ \dfrac{(w(t)-w)}{w(t)}u^{2}\right] -2\theta e^{T}\left[ \dfrac{w(t)-w}{w(t)}\right] \\&\quad =2\theta e^{T}(eu^{2})-2\theta e^{T}\left[ \dfrac{w}{w(t)}u^{2}\right] -2\theta e^{T}e+2\theta e^{T}\left[ \dfrac{w}{w(t)}\right] \\&\quad =2\theta e^{T}(e+d_{x}d_{s})-2\theta e^{T}\left[ \dfrac{w}{w(t)}(e+d_{x}d_{s})\right] -2\theta n+2\theta e^{T}\left[ \dfrac{w}{w(t)}\right] \\&\quad =2\theta n+2\theta d_{x}^{T}d_{s}-2\theta e^{T}\left[ \dfrac{w}{w(t)}\right] -2\theta e^{T}\left[ \dfrac{w}{w(t)}d_{x}d_{s}\right] -2\theta n+2\theta e^{T}\left[ \dfrac{w}{w(t)}\right] \\&\quad =2\theta e^{T}\left[ \dfrac{(w(t)-w)}{w(t)}d_{x}d_{s}\right] . \end{aligned}$$

Substitution yields

$$\begin{aligned} 4\delta (v^{f})^{2}= & {} \theta ^{2}e^{T}\left[ \dfrac{(w(t)-w)^{2}}{w(t)((1-\theta )w(t)+\theta w)}\right] +\theta ^{2}e^{T}\left[ \dfrac{(w(t)-w)^{2}}{w(t)((1-\theta )w(t)+\theta w)}d_{x}d_{s}\right] \\&+e^{T}\left[ \dfrac{((1-\theta )w(t)+\theta w)}{w(t)}d_{x}d_{s}\right] +e^{T}\left[ \dfrac{((1-\theta )w(t)+\theta w)}{w(t)}\cdot \dfrac{e}{e+d_{x}d_{s}}\right] \\&-e^{T}\left[ \dfrac{((1-\theta )w(t)+\theta w)}{w(t)}\right] +2\theta e^{T}\left[ \dfrac{(w(t)-w)}{w(t)}d_{x}d_{s}\right] \\= & {} e^{T}\left\{ \left[ \dfrac{\theta ^{2}(w(t)-w)^{2}}{w(t)((1-\theta )w(t)+\theta w)} +\dfrac{(1+\theta )w(t)-\theta w}{w(t)}\right] d_{x}d_{s}\right\} \\&+e^{T}\left[ \dfrac{\theta ^{2}(w(t)-w)^{2}}{w(t)((1-\theta )w(t)+\theta w)} -\dfrac{(1-\theta )w(t)+\theta w}{w(t)}\right] \\&+e^{T}\left\{ \left[ (1-\theta )e+\theta \dfrac{w}{w(t)}\right] \dfrac{e}{e+d_{x}d_{s}}\right\} . \end{aligned}$$

Since

$$\begin{aligned}&\dfrac{\theta ^{2}(w(t)-w)^{2}}{w(t)((1-\theta )w(t)+\theta w)} +\dfrac{(1+\theta )w(t)-\theta w}{w(t)}\\&\quad =\dfrac{\theta ^{2}(w(t)^{2}+w^{2}-2w(t)w)+((1+\theta )w(t)-\theta w)((1-\theta )w(t)+\theta w)}{w(t)((1-\theta )w(t)+\theta w)}\\&\quad =\dfrac{\theta ^{2}w(t)^{2}+\theta ^{2}w^{2}-2\theta ^{2}w(t)w+(1-\theta ^{2})w(t)^{2}-\theta ^{2}w^{2}+2\theta ^{2}w(t)w}{w(t)((1-\theta )w(t)+\theta w)}\\&\quad =\dfrac{w(t)}{(1-\theta )w(t)+\theta w} \end{aligned}$$

and

$$\begin{aligned}&\dfrac{\theta ^{2}(w(t)-w)^{2}}{w(t)((1-\theta )w(t)+\theta w)} -\dfrac{(1-\theta )w(t)+\theta w}{w(t)}\\&\quad =\dfrac{\theta ^{2}(w(t)-w)^{2}-((1-\theta )w(t)+\theta w)^{2}}{w(t)((1-\theta )w(t)+\theta w)}\\&\quad =\dfrac{[\theta (w(t)-w)+(1-\theta )w(t)+\theta w][\theta (w(t)-w)-(1-\theta )w(t)-\theta w]}{w(t)((1-\theta )w(t)+\theta w)}\\&\quad =\dfrac{\theta (w(t)-w)-(1-\theta )w(t)-\theta w}{(1-\theta )w(t)+\theta w}\\&\quad =\dfrac{\theta (w(t)-w)}{(1-\theta )w(t)+\theta w}-e, \end{aligned}$$

we have

$$\begin{aligned} 4\delta (v^{f})^{2}= & {} e^{T}\left[ \dfrac{w(t)}{(1-\theta )w(t)+\theta w}d_{x}d_{s}\right] +e^{T}\left[ \dfrac{\theta (w(t)-w)}{(1-\theta )w(t)+\theta w}-e\right] \\&+e^{T}\left\{ \left[ (1-\theta )e+\theta \dfrac{ w}{w(t)}\right] \dfrac{e}{e+d_{x}d_{s}}\right\} \\= & {} e^{T}\left[ \dfrac{w(t)}{(1-\theta )w(t)+\theta w}d_{x}d_{s}\right] +e^{T}\left[ \dfrac{\theta (w(t)-w)}{(1-\theta )w(t)+\theta w}-e\right] \\&-e^{T}\left\{ \left[ (1-\theta )e+\theta \dfrac{ w}{w(t)}\right] \dfrac{d_{x}d_{s}}{e+d_{x}d_{s}}\right\} +e^{T}\left[ (1-\theta )e+\theta \dfrac{ w}{w(t)}\right] \\= & {} e^{T}\left[ \dfrac{w(t)}{(1-\theta )w(t)+\theta w}d_{x}d_{s}\right] +e^{T}\left[ \frac{\theta (w(t)-w)}{(1-\theta )w(t)+\theta w}+\theta \frac{w}{w(t)}-\theta e\right] \\&-(1-\theta )e^{T}\left( \dfrac{d_{x}d_{s}}{e+d_{x}d_{s}}\right) -\theta e^{T}\left[ \dfrac{w}{w(t)}\cdot \dfrac{d_{x}d_{s}}{e+d_{x}d_{s}}\right] \\= & {} e^{T}\left[ \dfrac{w(t)}{(1-\theta )w(t)+\theta w}d_{x}d_{s}\right] +\theta ^{2} e^{T}\left[ \dfrac{(w(t)-w)^{2}}{w(t)((1-\theta )w(t)+\theta w)}\right] \\&-(1-\theta )e^{T}\left( \dfrac{d_{x}d_{s}}{e+d_{x}d_{s}}\right) -\theta e^{T}\left[ \dfrac{w}{w(t)}\cdot \dfrac{d_{x}d_{s}}{e+d_{x}d_{s}}\right] . \end{aligned}$$

Hence, it follows from (4), (17) and (18) that

$$\begin{aligned} 4\delta (v^{f})^{2}\le & {} \dfrac{1}{1-\theta }\sum \limits _{i=1}^{n}|d_{x_{i}}d_{s_{i}}|+(1-\theta )\dfrac{\sum \limits _{i=1}^{n}|d_{x_{i}}d_{s_{i}}|}{1-2\omega (v)^{2}} +\theta \sum \limits _{i=1}^{n}\dfrac{w_{i}}{w_{i}(t)}\cdot \dfrac{|d_{x_{i}}d_{s_{i}}|}{1-2\omega (v)^{2}}\\&+\theta ^{2}\sum \limits _{i=1}^{n}\left( \dfrac{t}{t_{0}}\right) ^{2}\cdot \dfrac{(w^{0}_{i}-w_{i})^{2}}{w_{i}(t)((1-\theta )w_{i}(t)+\theta w_{i})}\\\le & {} \dfrac{2\omega (v)^{2}}{1-\theta }+(1-\theta )\dfrac{2\omega (v)^{2}}{1-2\omega (v)^{2}} +\theta \max \limits _{1\le i\le n}\left\{ 1,\dfrac{w_{i}}{w^{0}_{i}}\right\} \dfrac{2\omega (v)^{2}}{1-2\omega (v)^{2}}\\&+\theta ^{2}n\max \limits _{1\le i\le n}\left\{ \left( \dfrac{w^{0}_{i}}{w_{i}}-1\right) ^{2},\left( 1-\dfrac{w_{i}}{w^{0}_{i}}\right) ^{2},\dfrac{1}{1-\theta }\right\} . \end{aligned}$$

Moreover, in the case of $w_{i}=0$ for some i,  we have

$$\begin{aligned} \left( \dfrac{t}{t_{0}}\right) ^{2}\cdot \dfrac{(w^{0}_{i}-w_{i})^{2}}{w_{i}(t)((1-\theta )w_{i}(t)+\theta w_{i})} =\left( \dfrac{t}{t_{0}}\right) ^{2}\cdot \dfrac{(w^{0}_{i})^{2}}{(1-\theta )\cdot \left( \dfrac{t}{t_{0}}w^{0}_{i}\right) ^{2}}=\dfrac{1}{1-\theta }, \end{aligned}$$

which implies that relation (21) holds for $w\ge 0.$ $\square$