Large-update interior point algorithm for $P_{\ast }$-linear complementarity problem

Abstract

It is well known that each barrier function defines an interior point algorithm and each barrier function is determined by its univariate kernel function. In this paper we present a new large-update primal-dual interior point algorithm for solving $P_{\ast }$-linear complementarity problem (LCP) based on a parametric version of the kernel function in (Bai et al. in SIAM J. Optim. 13:766-782, 2003). We show that the algorithm has $\mathcal{O}((1+2\kappa ){(logp)}^3\sqrt{n}(logn)log\frac{n{\mu }^0}{ϵ})$ iteration complexity, where p is a barrier function parameter and κ is the handicap of the matrix. This is the best known complexity result for such a method.

MSC:90C33, 90C51.

1 Introduction

In this paper, we consider the standard form of LCP as follows:

$$s=Mx+q,xs=0,x\ge 0,s\ge 0,$$

(1.1)

where $x,s,q\in {\mathbf{R}}^n$ and $M\in {\mathbf{R}}^{n\times n}$ is a $P_{\ast }$-matrix and xs denotes the componentwise (Hadamard) product of the vectors x and s.

The matrix M is a $P_{\ast }$-matrix if it is a $P_{\ast }(\kappa )$-matrix for some $\kappa \ge 0$, where $P_{\ast }(\kappa ):=\{M\in {\mathbf{R}}^{n\times n}\mid (1+4\kappa ){\sum }_{i\in I_{+}(\xi )}{[\xi ]}_i{[M\xi ]}_i+{\sum }_{i\in I_{-}(\xi )}{[\xi ]}_i{[M\xi ]}_i\ge 0,\mathrm{\forall }\xi \in {\mathbf{R}}^n\}$, where ${[M\xi ]}_i$ denotes the i th component of the vector Mξ, $I_{+}(\xi )=\{1\le i\le n:{\xi }_i{[M\xi ]}_i\ge 0\}$, $I_{-}(\xi )=\{1\le i\le n:{\xi }_i{[M\xi ]}_i<0\}$. Note that M is a $P_{\ast }(0)$-matrix if and only if M is positive semidefinite.

In the following, we give some examples for $P_{\ast }(\kappa )$-matrices.

Example 1.1 The matrix

$${\mathbf{M}}_{\mathbf{1}}=\left(\begin{array}{cc}0& 2+4\kappa \\ -2& 0\end{array}\right)$$

is $P_{\ast }(\kappa )$, for all $\kappa \ge 0$. Indeed, since $x({\mathbf{M}}_{\mathbf{1}}x)={((2+4\kappa )x_1{x}_2,-2x_1{x}_2)}^T$, for $x_1{x}_2>0$, $I_{+}=\{1\}$ and $I_{-}=\{2\}$. Hence $(1+4\kappa )(2+4\kappa )x_1{x}_2-2x_1{x}_2=4\kappa x_1{x}_2(3+4\kappa )\ge 0$ for all $\kappa \ge 0$. For $x_1{x}_2<0$, $I_{+}=\{2\}$ and $I_{-}=\{1\}$. Then $(1+4\kappa )(-2x_1{x}_2)+(2+4\kappa )x_1{x}_2=-4\kappa x_1{x}_2\ge 0$, for all $\kappa \ge 0$. Thus, ${\mathbf{M}}_{\mathbf{1}}$ is $P_{\ast }(\kappa )$, for all $\kappa \ge 0$.

Example 1.2 For $c\ge 0$, the matrix

$${\mathbf{M}}_{\mathbf{2}}=\left(\begin{array}{ccc}0& 1+4\kappa & 0\\ -1& 0& 0\\ 0& 0& c\end{array}\right)$$

is $P_{\ast }(\kappa )$, for all $\kappa \ge 0$. $x({\mathbf{M}}_{\mathbf{2}}x)={((1+4\kappa )x_1{x}_2,-x_1{x}_2,c{x}_3^2)}^T$. If $x_1{x}_2>0$, $I_{+}=\{1,3\}$ and $I_{-}=\{2\}$. Hence ${(1+4\kappa )}^2{x}_1{x}_2+c(1+4\kappa )x_3^2-x_1{x}_2=8\kappa (1+2\kappa )x_1{x}_2+c(1+4\kappa )x_3^2\ge 0$, for all $\kappa \ge 0$. If $x_1{x}_2<0$, $I_{+}=\{2,3\}$ and $I_{-}=\{1\}$. $(1+4\kappa )(-x_1{x}_2+c{x}_3^2)+(1+4\kappa )x_1{x}_2=c(1+4\kappa )x_3^2\ge 0$, for all $\kappa \ge 0$. Thus, ${\mathbf{M}}_{\mathbf{2}}$ is $P_{\ast }(\kappa )$, for all $\kappa \ge 0$.

Linear complementarity problems (LCPs) have many applications in science, economics and engineering. LCPs include linear and quadratic programming, fixed point problems and sets of piecewise-linear equations, bimatrix equilibrium points and variational inequalities [1]. A large-update interior point method (IPM) is one of the most efficient numerical methods for various optimization problems.

Peng-Roos-Terlaky [2–4] proposed new variants of interior point methods (IPMs) based on self-regular barrier functions and achieved so far the best known complexity for large-update methods with a specific self-regular barrier function. Bai-Ghami-Roos [5] proposed a new primal-dual IPM for linear optimization (LO) problem based on eligible barrier functions and a unified scheme for analyzing the algorithm based on four conditions of the kernel function and Bai-Lesaja-Roos [6] generalized to $P_{\ast }(\kappa )$-LCP. Cho [7] and Cho-Kim [8] extended the complexity analysis for LO problem to $P_{\ast }(\kappa )$-LCP. Amini-Haseli [9] and Amini-Peyghami [10] introduced generalized versions of the kernel functions in [5] and improved the complexity results for large-update methods for LO and $P_{\ast }(\kappa )$-LCP, respectively. Recently, Lesaja-Roos [11] proposed a unified analysis of the IPM for $P_{\ast }(\kappa )$-LCP based on the class of eligible barrier functions which was first introduced by Bai-Ghami-Roos [5] for LO. Wang-Bai [12] generalized interior point algorithm for LO to P-matrix LCP over symmetric cones based on the same kernel function. Wang-Lesaja [13] extended the full NT-step infeasible IPM for symmetric cone LO to the Cartesian $P_{\ast }(\kappa )$-symmetric cone LCP and the algorithm is small-update method.

The most challenging question in this research area is whether or not there exists a kernel function for which the iteration bound for large-update method is the same as or even better than currently best known bound for such methods [5]. Bai-Ghami-Roos [14] proposed a new efficient large-update IPM for LO based on a barrier-type function which is not a barrier function in the usual sense since it has finite value at the boundary of the feasible region. Despite this, they obtained the best known iteration bound. Ghami [15] proposed various versions of interior point algorithms based on kernel functions and showed that the kernel function in [14] seems promising through numerical tests. Wang-Bai [16] proposed a generalized version of the kernel function in [14] which has a parameter in the growth term for $P_{\ast }(\kappa )$-horizontal LCPs and obtained the best known complexity bound when the parameter value equals 1, i.e. the same kernel function in [14]. This implies that the parameter in the growth term does not improve the complexity of the algorithm except 1.

Motivated by this, we introduce a parameter in the barrier term of the kernel function in [14] and obtained the best known complexity result for large-update methods for all parameters. Note that when the parameter in the barrier term grows, the barrier function grows faster when t approaches zero.

The paper is organized as follows: In Section 2, we introduce the generic IPM and give some examples of $P_{\ast }(\kappa )$-matrices. In Section 3, we introduce a class of barrier functions and propose a new large-update interior point algorithm for $P_{\ast }$-LCP. In Section 4, we derive the complexity results for the algorithm. Finally concluding remarks are given in Section 5.

Throughout the paper, ${\mathbf{R}}_{+}^n$ and ${\mathbf{R}}_{++}^n$ denote the set of n-dimensional nonnegative vectors and positive vectors, respectively. For $x\in {\mathbf{R}}^n$, ${[x]}_i$ and $x_1$ denote the i th component and the smallest component of the vector x, respectively. We denote by D the diagonal matrix from a vector d and e, the n-dimensional vector of ones. The index set $I:=\{1,2,\dots ,n\}$. For $g_1(t),g_2(t):{\mathbf{R}}_{++}\to {\mathbf{R}}_{++}$, $g_1(t)=\mathcal{O}(g_2(t))$ if there exists a positive constant $c_1$ such that $g_1(t)\le c_1{g}_2(t)$, for all $t>0$, and $g_1(t)=\mathrm{\Theta }(g_2(t))$ if there exist positive constants $c_2$ and $c_3$ such that $c_2{g}_2(t)\le g_1(t)\le c_3{g}_2(t)$, for all $t>0$. For $a\in \mathbf{R}$, $\lfloor a\rfloor :=max\{m\in \mathbf{Z}\mid m\le a\}$ and $\lceil a\rceil :=min\{n\in \mathbf{Z}\mid n\ge a\}$, where Z is the set of integers. log denotes the natural logarithm.

2 Preliminaries

In this section we recall some basic concepts and introduce the generic interior point algorithm. The basic idea of IPMs for LCP is to replace the second equation in (1.1) by the parameterized equation $xs=\mu \mathbf{e}$, $\mu >0$. Now we consider the following system:

$$s=Mx+q,xs=\mu \mathbf{e},x>0,s>0.$$

(2.1)

Without loss of generality, we assume that (1.1) satisfies the interior point condition (IPC), i.e., there exists a $(x^0,s^0)>0$ such that $s^0=M{x}^0+q$ [17]. Since M is a $P_{\ast }(\kappa )$-matrix for some $\kappa \ge 0$ and (1.1) satisfies the IPC, the system (2.1) has a unique solution for $\mu >0$. We denote the solution of (2.1) by $(x(\mu ),s(\mu ))$ which is called the μ-center for $\mu >0$. The set of μ-centers is called the central path of (1.1). Since the limit of the μ-centers satisfies (1.1) as $\mu \to 0$, it yields the solution for (1.1) [17]. IPMs follow the central path approximately and approach the solution of (1.1) as $\mu \to 0$.

For given $(x,s):=(x^0,s^0)$, by applying Newton’s method to the system (2.1), we have the following Newton system:

$$-M\mathrm{\Delta }x+\mathrm{\Delta }s=0,S\mathrm{\Delta }x+X\mathrm{\Delta }s=\mu \mathbf{e}-xs,$$

(2.2)

where $X:=diag(x)$ and $S:=diag(s)$. By Lemma 4.1 of [17], the system (2.2) has a unique solution $(\mathrm{\Delta }x,\mathrm{\Delta }s)$. By taking a step along the search direction $(\mathrm{\Delta }x,\mathrm{\Delta }s)$, one constructs a new iteration $(x_{+},s_{+})$, where

$$x_{+}:=x+\alpha \mathrm{\Delta }x,s_{+}:=s+\alpha \mathrm{\Delta }s,$$

for some step size $\alpha \ge 0$. For notational convenience, we define the following:

$$v:=\sqrt{\frac{xs}{\mu }},d:=\sqrt{\frac{x}{s}},d_x:=\frac{v\mathrm{\Delta }x}{x},d_s:=\frac{v\mathrm{\Delta }s}{s}.$$

(2.3)

Using (2.3), we can rewrite the system (2.2) as follows:

$$-\overline{M}{d}_x+d_s=0,d_x+d_s=v^{-1}-v,$$

(2.4)

where $\overline{M}:=DMD$ and $D:=diag(d)$. Note that the right-hand side of the second equation in (2.4) equals the negative gradient of the classical logarithmic barrier function ${\mathrm{\Psi }}_l(v)$, i.e.,

$$d_x+d_s=-\mathrm{\nabla }{\mathrm{\Psi }}_l(v),$$

(2.5)

where ${\mathrm{\Psi }}_l(v):={\sum }_{i=1}^n{\psi }_l(v_i)$ and ${\psi }_l(t):=\frac{t^2-1}{2}-logt$, for $t>0$. We call ${\psi }_l$ the kernel function of the classical logarithmic barrier function ${\mathrm{\Psi }}_l(v)$.

Assuming that we are given a strictly feasible point $(x,s)$ which is in a τ-neighborhood of the given μ-center, the generic interior point algorithm works as in Algorithm 1.

Algorithm 1

The generic interior point algorithm

3 New algorithm

Consider a class of kernel functions $\psi (t)$ as follows:

$$\psi (t):=\frac{(logp)(t^2-1)}{2}+\frac{1}{\sigma }(p^{\sigma (1-t)}-1),p\ge e,\sigma \ge 1,t>0.$$

(3.1)

Then we have the first three derivatives of $\psi (t)$ as follows:

$$\begin{array}{r}{\psi }^{\prime }(t)=(logp)(t-p^{\sigma (1-t)}),\\ {\psi }^{″}(t)=(logp)(1+\sigma (logp)p^{\sigma (1-t)}),\\ {\psi }^{(3)}(t)=-{\sigma }^2{(logp)}^3{p}^{\sigma (1-t)}.\end{array}$$

(3.2)

From (3.1) and (3.2), we have for $p\ge e$, $\sigma \ge 1$ and $t>0$,

$${\psi }^{\prime }(1)=\psi (1)=0,{\psi }^{″}(t)>logp,\underset{t\to 0^{+}}{lim}\psi (t)<\mathrm{\infty },\underset{t\to \mathrm{\infty }}{lim}\psi (t)=\mathrm{\infty }.$$

(3.3)

From (3.3), $\psi (t)$ is strictly convex and has a minimum value 0 at $t=1$.

Lemma 3.1 Let $\psi (t)$ be defined as in (3.1). Then for $p\ge e$ and $\sigma \ge 1$,

• (i) $t{\psi }^{″}(t)+{\psi }^{\prime }(t)\ge 0$, $t>\frac{1}{\sigma logp}$,

• (ii) $t{\psi }^{″}(t)-{\psi }^{\prime }(t)\ge 0$, $t>0$,

• (iii) ${\psi }^{(3)}(t)<0$, $t>0$.

Proof For (i), using (3.2) with $t>\frac{1}{\sigma logp}$, we have

$$t{\psi }^{″}(t)+{\psi }^{\prime }(t)=2t(logp)+(\sigma (logp)t-1)(logp)p^{\sigma (1-t)}>0.$$

For (ii), $t{\psi }^{″}(t)-{\psi }^{\prime }(t)=(\sigma (logp)t+1)(logp)p^{\sigma (1-t)}>0$, $t>0$.

For (iii), it is clear from (3.2). □

Corollary 3.2 Let $t_1,t_2\ge \frac{1}{\sigma logp}$. By Lemma  3.1(i) and Lemma  2.1.2 in [4], we have $\psi (\sqrt{t_1{t}_2})\le \frac{1}{2}(\psi (t_1)+\psi (t_2))$, i.e., $\psi (t)$ is exponentially convex, for all $t>\frac{1}{\sigma logp}$.

Remark 3.3 By Lemma 3.1(ii), (iii), and Lemma 2.4 in [5], ${\psi }^{″}(t){\psi }^{\prime }(\beta t)-\beta {\psi }^{\prime }(t){\psi }^{″}(\beta t)>0$, $t>0$, $\beta >1$.

Lemma 3.4 For $\psi (t)$ as in (3.1), we have

$$\frac{logp}{2}{(t-1)}^2\le \psi (t)\le \frac{1}{2logp}{({\psi }^{\prime }(t))}^2,p\ge e,\sigma \ge 1,t>0.$$

Proof Using (3.3), we have

$$\psi (t)={\int }_1^t{\int }_1^{\xi }{\psi }^{″}(\zeta )d\zeta d\xi \ge {\int }_1^t{\int }_1^{\xi }(logp)d\zeta d\xi =\frac{logp}{2}{(t-1)}^2$$

and

$$\begin{array}{rcl}\psi (t)& =& {\int }_1^t{\int }_1^{\xi }{\psi }^{″}(\zeta )d\zeta d\xi \le \frac{1}{logp}{\int }_1^t{\int }_1^{\xi }{\psi }^{″}(\xi ){\psi }^{″}(\zeta )d\zeta d\xi \\ =& \frac{1}{logp}{\int }_1^t{\psi }^{″}(\xi ){\psi }^{\prime }(\xi )d\xi =\frac{1}{logp}{\int }_1^t{\psi }^{\prime }(\xi )d{\psi }^{\prime }(\xi )=\frac{1}{2logp}{({\psi }^{\prime }(t))}^2.\end{array}$$

 □

Lemma 3.5 Let $\varrho :[0,\mathrm{\infty })\to [1,\mathrm{\infty })$ be the inverse function of $\psi (t)$ for $t\ge 1$. Then we have

$$\varrho (u)\le 1+\sqrt{\frac{2u}{logp}},p\ge e,u\ge 0.$$

Proof Let $u:=\psi (t)$ for $t\ge 1$. Then $\varrho (u)=t$. Using the first inequality in Lemma 3.4, we have $u=\psi (t)\ge \frac{logp}{2}{(t-1)}^2$. Then we have $t=\varrho (u)\le 1+\sqrt{\frac{2u}{logp}}$. □

Lemma 3.6 Let $\rho :[0,\mathrm{\infty })\to (0,1]$ be the inverse function of $-\frac{1}{2}{\psi }^{\prime }(t)$ for $0<t\le 1$. Then $\rho (z)\ge \frac{\sigma (logp)-log(\frac{2z}{logp}+1)}{\sigma logp}$, $p>e$, $\sigma \ge 1$, $z\ge 0$.

Proof Let $z:=-\frac{1}{2}{\psi }^{\prime }(t)$, for $0<t\le 1$. By the definition of ρ, $\rho (z)=t$, for $z\ge 0$ and $2z=-\psi (t)$. By (3.2) and $0<t\le 1$, $p^{\sigma (1-t)}=\frac{2z}{logp}+t\le \frac{2z}{logp}+1$. Hence $t=\rho (z)\ge \frac{\sigma (logp)-log(\frac{2z}{logp}+1)}{\sigma logp}$. □

Define for $\psi (t)$ as in (3.1) and $v\in {\mathbf{R}}_{++}^n$,

$$\mathrm{\Psi }(v):=\mathrm{\Psi }(x,s,\mu ):=\sum _{i=1}^n\psi \left({[v]}_i\right).$$

(3.4)

Since $\mathrm{\Psi }(v)$ is strictly convex and minimal at $v=\mathbf{e}$, we have

$$\mathrm{\Psi }(v)=0\iff v=\mathbf{e}\iff x=x(\mu ),s=s(\mu ).$$

We use $\mathrm{\Psi }(v)$ as the proximity function to measure the distance between the current iteration and corresponding μ-center. Also, we define the norm-based proximity measure $\delta (v)$ as follows:

$$\delta (v):=\frac{1}{2}\parallel \mathrm{\nabla }\mathrm{\Psi }(v)\parallel =\frac{1}{2}\parallel d_x+d_s\parallel .$$

(3.5)

Note that $\delta (v)=0\iff v=\mathbf{e}\iff \mathrm{\Psi }(v)=0$. In this paper, we replace the right-hand side of (2.5), $-\mathrm{\nabla }{\mathrm{\Psi }}_l(v)$, by $-\mathrm{\nabla }\mathrm{\Psi }(v)$ as in (3.4). This defines a new search direction and proximity function.

In the following we compute upper bound of proximity function during an outer iteration.

Lemma 3.7 Let $\delta (v)$ and $\mathrm{\Psi }(v)$ be defined as in (3.5) and (3.4), respectively. Then $\delta (v)\ge \sqrt{\frac{logp}{2}\mathrm{\Psi }(v)}$, $v\in {\mathbf{R}}_{++}^n$, $p\ge e$.

Proof Using (3.5) and the second inequality of Lemma 3.4,

$${\delta }^2(v)=\frac{1}{4}\sum _{i=1}^n{\left({\psi }^{\prime }\left({[v]}_i\right)\right)}^2\ge \frac{logp}{2}\sum _{i=1}^n\psi \left({[v]}_i\right)=\frac{logp}{2}\mathrm{\Psi }(v).$$

Hence we have $\delta (v)\ge \sqrt{\frac{logp}{2}\mathrm{\Psi }(v)}$. □

Lemma 3.8 Let $L\ge 8$ and $\mathrm{\Psi }(v)\le L$. If $\sigma \ge 1+2log(1+L)$ and $p\ge e$, then $v_1\ge \frac{3}{2\sigma logp}$.

Proof If $v_1\ge 1$, then $v_1\ge 1>\frac{3}{2\sigma logp}$. Suppose that $v_1<1$. Let $t:=v_1$. Since $\mathrm{\Psi }(v)\le L$, $\psi (t)\le L$, i.e., $\frac{(logp)(t^2-1)}{2}+\frac{1}{\sigma }(p^{\sigma (1-t)}-1)\le L$. This implies that $\frac{1}{\sigma }(p^{\sigma (1-t)}-1)\le L+\frac{(logp)(1-t^2)}{2}\le L+\frac{logp}{2}$, $p^{1-\sigma t}\le \frac{1+\sigma (L+\frac{logp}{2})}{p^{\sigma -1}}$. Let $g_1(\sigma ):=\frac{1+\sigma (L+\frac{logp}{2})}{p^{\sigma -1}}$. Then $g_1(\sigma )$ is monotone decreasing in σ. Since $\sigma \ge 1+2log(1+L)$ and $p\ge e$, $p^{1-\sigma t}\le \frac{1+(1+2log(1+L))(L+\frac{logp}{2})}{p^{2log(1+L)}}\le \frac{1+(1+2log(1+L))(L+\frac{logp}{2})}{e^{2log(1+L)}}=\frac{1+(1+2log(1+L))(L+\frac{logp}{2})}{{(1+L)}^2}$.

Let $g_2(L):=\frac{1+(1+2log(1+L))(L+\frac{logp}{2})}{{(1+L)}^2}$. Then $p^{1-\sigma t}\le g_2(L)$ and hence $t\ge \frac{1}{\sigma logp}log\frac{p}{g_2(L)}$. Let $g_3(p,L):=\frac{p}{g_2(L)}:=\frac{p{(1+L)}^2}{1+(1+2log(1+L))(L+\frac{logp}{2})}$. $g_3(p,L)$ is monotone increasing in p and L, respectively. Since $p\ge e$ and $L\ge 8$, $g_3(p,L)\ge \frac{81e}{1+8.5(1+4log3)}\ge 4.6$. Hence $t\ge \frac{log(4.6)}{\sigma logp}\ge \frac{3}{2\sigma logp}$. □

4 Complexity analysis

In this section we give the iteration complexity of the algorithm for large-update methods. For complexity analysis of the algorithm we follow a similar framework to the one defined in [5] for LO problems. In the following we compute the bound of the growth of the barrier function during an outer iteration of the algorithm.

Using Lemma 3.1(ii), (iii), and Theorem 3.2 in [5], we obtain the following lemma.

Lemma 4.1 Let ϱ be defined as in Lemma  3.5. If $\mathrm{\Psi }(v)\le \tau$, then

$$\mathrm{\Psi }(\beta v)\le n\psi \left(\beta \varrho \left(\frac{\tau }{n}\right)\right),v\in {\mathbf{R}}_{++}^n,\beta \ge 1.$$

(4.1)

In the following we compute the upper bounds of $\mathrm{\Psi }(v)$ when we update the barrier parameter μ.

Theorem 4.2 Let $0<\theta <1$ and $v_{+}:=\frac{v}{\sqrt{1-\theta }}$. If $\mathrm{\Psi }(v)\le \tau$, then we have

$$\mathrm{\Psi }(v_{+})\le \frac{\theta (logp)n+2\sqrt{2\tau (logp)n}+2\tau }{2(1-\theta )},p\ge e.$$

Proof Define ${\psi }_b(t):=\frac{1}{\sigma }(p^{\sigma (1-t)}-1)$. Then $\psi (t)=\frac{(logp)(t^2-1)}{2}+{\psi }_b(t)$ and ${\psi }_b^{\prime }(t)=-(logp)p^{\sigma (1-t)}<0$ and ${\psi }_b(1)=0$. Hence, we have

$$\psi (t)\le \frac{(logp)(t^2-1)}{2},t\ge 1,p\ge e.$$

(4.2)

Using Lemma 4.1, (4.2), and Lemma 3.5, we have

$$\begin{array}{rcl}\mathrm{\Psi }(v_{+})& \le & n\psi \left(\frac{1}{\sqrt{1-\theta }}\varrho \left(\frac{\tau }{n}\right)\right)\le \frac{nlogp}{2}(\frac{{\varrho }^2(\frac{\tau }{n})}{1-\theta }-1)\\ \le & \frac{nlogp}{2}(\frac{{(1+\sqrt{\frac{2\tau }{nlogp}})}^2}{1-\theta }-1)\\ =& \frac{\theta (logp)n+2\sqrt{2\tau (logp)n}+2\tau }{2(1-\theta )}.\end{array}$$

 □

Define

$${\overline{\mathrm{\Psi }}}_0:=\frac{\theta (logp)n+2\sqrt{2\tau (logp)n}+2\tau }{2(1-\theta )}.$$

(4.3)

We will use ${\overline{\mathrm{\Psi }}}_0$ for the upper bounds of $\mathrm{\Psi }(v)$ for large-update methods.

Remark 4.3 Let $L:={\overline{\mathrm{\Psi }}}_0$. Without loss of generality, we can assume that $L\ge 8$. Indeed, when $p\ge e$, $\tau \ge 1$ and $n\ge 2$, $L\ge \frac{\theta n+2\sqrt{2\tau n}+2\tau }{2(1-\theta )}\ge \frac{\theta n+2\sqrt{2n}+2}{2(1-\theta )}\ge \frac{\theta +3}{1-\theta }>8$ if $\theta >\frac{5}{9}$. In the algorithm we take $\sigma :=1+2log(1+L)$.

Remark 4.4 For large-update method with $\tau =\mathcal{O}(n)$ and $\theta =\mathrm{\Theta }(1)$, we have ${\overline{\mathrm{\Psi }}}_0=\mathcal{O}((logp)n)$ and $\sigma =\mathcal{O}(log((logp)n))$.

In the following we compute a default step size which keeps the iterates strictly feasible and decreases the value of barrier function during inner iterations. For fixed μ, if we take a step size α, then we have new iterations $x_{+}:=x+\alpha \mathrm{\Delta }x$, $s_{+}:=s+\alpha \mathrm{\Delta }s$. Using (2.3), we have

$$\begin{array}{c}{x}_{+}=x(e+\alpha \frac{\mathrm{\Delta }x}{x})=x(e+\alpha \frac{d_x}{v})=\frac{x}{v}(v+\alpha d_x),\hfill \\ s_{+}=s(e+\alpha \frac{\mathrm{\Delta }s}{s})=s(e+\alpha \frac{d_s}{v})=\frac{s}{v}(v+\alpha d_s).\hfill \end{array}$$

Thus we have

$$v_{+}:=\sqrt{\frac{x_{+}{s}_{+}}{\mu }}=\sqrt{(v+\alpha d_x)(v+\alpha d_s)}.$$

Define for $\alpha >0$,

$$f(\alpha ):=\mathrm{\Psi }(v_{+})-\mathrm{\Psi }(v).$$

(4.4)

Then $f(\alpha )$ is the difference of proximities between a new iteration and a current iteration for fixed μ. Assume that for some $\alpha \ge 0$, ${[v]}_i+\alpha {[d_x]}_i>\frac{1}{\sigma logq}$ and ${[v]}_i+\alpha {[d_s]}_i>\frac{1}{\sigma logq}$, for all $i\in I$. By Corollary 3.2,

$$\mathrm{\Psi }(v_{+})=\mathrm{\Psi }\left(\sqrt{(v+\alpha d_x)(v+\alpha d_s)}\right)\le \frac{1}{2}(\mathrm{\Psi }(v+\alpha d_x)+\mathrm{\Psi }(v+\alpha d_s)).$$

Define

$$f_1(\alpha ):=\frac{1}{2}(\mathrm{\Psi }(v+\alpha d_x)+\mathrm{\Psi }(v+\alpha d_s))-\mathrm{\Psi }(v).$$

Then we have $f(\alpha )\le f_1(\alpha )$ and $f(0)=f_1(0)=0$. By taking the derivative of $f_1(\alpha )$ with respect to α, we have

$$f_1^{\prime }(\alpha )=\frac{1}{2}\sum _{i=1}^n({\psi }^{\prime }({[v]}_i+\alpha {[d_x]}_i){[d_x]}_i+{\psi }^{\prime }({[v]}_i+\alpha {[d_s]}_i){[d_s]}_i).$$

Using (2.5) and (3.5), we have

$$f_1^{\prime }(0)=\frac{1}{2}\mathrm{\nabla }\mathrm{\Psi }{(v)}^T(d_x+d_s)=-\frac{1}{2}\mathrm{\nabla }\mathrm{\Psi }{(v)}^T\mathrm{\nabla }\mathrm{\Psi }(v)=-2{\delta }^2(v).$$

(4.5)

Differentiating $f_1^{\prime }(\alpha )$ with respect to α, we have

$$f_1^{″}(\alpha )=\frac{1}{2}\sum _{i=1}^n({\psi }^{″}({[v]}_i+\alpha {[d_x]}_i){[d_x]}_i^2+{\psi }^{″}({[v]}_i+\alpha {[d_s]}_i){[d_s]}_i^2).$$

Since $f_1^{″}(\alpha )>0$, $f_1(\alpha )$ is strictly convex in α unless $d_x=d_s=0$. Since M is a $P_{\ast }(\kappa )$-matrix and $M\mathrm{\Delta }x=\mathrm{\Delta }s$ from (2.2), for $\mathrm{\Delta }x\in {\mathbf{R}}^n$,

$$(1+4\kappa )\sum _{i\in I_{+}}{[\mathrm{\Delta }x]}_i{[\mathrm{\Delta }s]}_i+\sum _{i\in I_{-}}{[\mathrm{\Delta }x]}_i{[\mathrm{\Delta }s]}_i\ge 0,$$

where $I_{+}=\{i\in I:{[\mathrm{\Delta }x]}_i{[\mathrm{\Delta }s]}_i\ge 0\}$ and $I_{-}=I-I_{+}$. Since $d_x{d}_s=\frac{v^2\mathrm{\Delta }x\mathrm{\Delta }s}{xs}=\frac{\mathrm{\Delta }x\mathrm{\Delta }s}{\mu }$ and $\mu >0$, we have

$$(1+4\kappa )\sum _{i\in I_{+}}{[d_x]}_i{[d_s]}_i+\sum _{i\in I_{-}}{[d_x]}_i{[d_s]}_i\ge 0.$$

For notational convenience, we denote $\delta :=\delta (v)$, $\mathrm{\Psi }:=\mathrm{\Psi }(v)$, ${\sigma }_{+}:={\sum }_{i\in I_{+}}{[d_x]}_i{[d_s]}_i$ and ${\sigma }_{-}:=-{\sum }_{i\in I_{-}}{[d_x]}_i{[d_s]}_i$. To estimate the bound for $\parallel d_x\parallel$ and $\parallel d_s\parallel$, we need the following technical lemma.

Lemma 4.5 (Modification of Lemma 4.1 in [8])

${\sigma }_{+}\le {\delta }^2$ and ${\sigma }_{-}\le (1+4\kappa ){\delta }^2$.

Lemma 4.6 (Modification of Lemma 4.2 in [8])

${\sum }_{i=1}^n({[d_x]}_i^2+{[d_s]}_i^2)\le 4(1+2\kappa ){\delta }^2$, $\parallel d_x\parallel \le 2\delta \sqrt{1+2\kappa }$ and $\parallel d_s\parallel \le 2\delta \sqrt{1+2\kappa }$.

Using (4.5) and Lemma 4.6, we have the following lemma.

Lemma 4.7 (Modification of Lemma 4.3 in [8])

Let δ be defined as in (3.5). Then we have

$$f_1^{″}(\alpha )\le 2(1+2\kappa ){\delta }^2{\psi }^{″}(v_1-2\alpha \delta \sqrt{1+2\kappa }).$$

Using (4.5) and Lemma 4.7, we have the following lemma.

Lemma 4.8 (Modification of Lemma 4.4 in [8])

If the step size α satisfies the inequality

$$-{\psi }^{\prime }(v_1-2\alpha \delta \sqrt{1+2\kappa })+{\psi }^{\prime }(v_1)\le \frac{2\delta }{\sqrt{1+2\kappa }},$$

(4.6)

then $f_1^{\prime }(\alpha )\le 0$.

Lemma 4.9 (Modification of Lemma 4.5 in [8])

Let ρ be defined as in Lemma  3.6 and $a:=1+\frac{1}{\sqrt{1+2\kappa }}$. Then, in the worst case, the largest step size α satisfying (4.6) is given by

$$\overline{\alpha }:=\frac{1}{2\delta \sqrt{1+2\kappa }}(\rho (\delta )-\rho (a\delta )).$$

(4.7)

Lemma 4.10 (Modification of Lemma 4.6 in [8])

Let ρ and $\overline{\alpha }$ be defined as in Lemma  4.9. Then

$$\overline{\alpha }\ge \frac{1}{(1+2\kappa ){\psi }^{″}(\rho (a\delta ))}.$$

Let

$$\tilde{\alpha }:=\frac{1}{(1+2\kappa ){\psi }^{″}(\rho (a\delta ))}.$$

(4.8)

Letting $t:=\rho (a\delta )$, we have $0<t\le 1$ and $-{\psi }^{\prime }(t)=2a\delta$. By (3.2) and $1\le a\le 2$, we have

$$(logp)p^{\sigma (1-t)}\le (logp)+4\delta .$$

(4.9)

By (4.8) with (3.2) and $\sigma \ge 1$, (4.9), Lemma 3.7 with $\mathrm{\Psi }\ge \tau \ge 1$ and $p\ge e$,

$$\begin{array}{rcl}\tilde{\alpha }& \ge & \frac{1}{\sigma (1+2\kappa )(logp)(1+p^{\sigma (1-t)}logp)}\ge \frac{1}{\sigma (1+2\kappa )(logp)(1+4\delta +logp)}\\ \ge & \frac{1}{\sigma \delta (1+2\kappa )(logp)(\sqrt{2}+4+\sqrt{2}logp)}\ge \frac{1}{2\sigma \delta (1+2\kappa ){(logp)}^2(2+\sqrt{2})}.\end{array}$$

Define the default step size $\hat{\alpha }$ as follows:

$$\hat{\alpha }:=\frac{1}{2\sigma \delta (1+2\kappa ){(logp)}^2(2+\sqrt{2})}.$$

(4.10)

Using Lemma 4.6, Lemma 3.8, and (4.10), ${[v]}_i+\overline{\alpha }{[d_x]}_i$ ≥ $v_1-2\overline{\alpha }\sqrt{1+2\kappa }\delta$ ≥ $\frac{3}{2\sigma logp}-\frac{1}{\sigma \sqrt{1+2\kappa }{(logp)}^2(2+\sqrt{2})}$ ≥ $(\frac{3}{2}-\frac{1}{(2+\sqrt{2})logp})\frac{1}{\sigma logp}$ ≥ $(\frac{3}{2}-\frac{1}{2+\sqrt{2}})\frac{1}{\sigma logp}$ > $\frac{1}{\sigma logp}$, for all $i\in I$. In the same way, ${[v]}_i+\overline{\alpha }{[d_x]}_i>\frac{1}{\sigma logp}$, for all $i\in I$. Hence we can use the exponential convexity of $\psi (t)$.

Lemma 4.11 (Lemma 1.3.3 in [4])

Let a function h be twice differentiable and convex with $h(0)=0$, $h^{\prime }(0)<0$ and let h attain its (global) minimum at $t^{\ast }>0$. If $h^{″}(t)$ is monotonically increasing on $t\in [0,t^{\ast }]$, then

$$h(t)\le \frac{t{h}^{\prime }(0)}{2},0\le t\le t^{\ast }.$$

Using $f_1(0)=0$, (4.5), ${\psi }^{‴}<0$, and Lemma 4.11, we have the following lemma.

Lemma 4.12 Let $\overline{\alpha }$ be defined as in (4.7). If the step size α is such that $\alpha \le \overline{\alpha }$, then

$$f(\alpha )\le -\alpha {\delta }^2.$$

Using Lemma 4.12, (4.10), and Lemma 3.7, we have the following theorem.

Theorem 4.13 For $\hat{\alpha }$ as in (4.10), $f(\hat{\alpha })\le -\frac{{\mathrm{\Psi }}^{\frac{1}{2}}}{4(1+\sqrt{2})(1+2\kappa )\sigma {(logp)}^{\frac{3}{2}}}$.

Proposition 4.14 (Proposition 1.3.2 in [4])

Let $t_0,t_1,\dots ,t_{\overline{K}}$ be a sequence of positive numbers such that

$$t_{k+1}\le t_k-\lambda t_k^{1-\gamma },k=0,1,\dots ,\overline{K}-1,$$

where $\lambda >0$ and $0<\gamma \le 1$. Then $\overline{K}\le \lfloor \frac{t_0^{\gamma }}{\lambda \gamma }\rfloor$.

We define the value of $\mathrm{\Psi }(v)$ after the μ-update as ${\mathrm{\Psi }}_0$ and the subsequent values in the same outer iteration are denoted as ${\mathrm{\Psi }}_k$, $k=1,2,\dots$ . Then we have ${\mathrm{\Psi }}_0\le {\overline{\mathrm{\Psi }}}_0$. If we let K be the number of inner iterations per an outer iteration, then we have ${\mathrm{\Psi }}_{K-1}>\tau$, $0\le {\mathrm{\Psi }}_K\le \tau$. In the following theorem we give the bound for the total number of iterations.

Theorem 4.15 Let a $P_{\ast }(\kappa )$-LCP be given. If $\tau \ge 1$, then the total number of iterations of the algorithm to get an ϵ-approximate solution is bounded by

$$\lceil \frac{8(1+\sqrt{2})(1+2\kappa )\sigma {(logp)}^{\frac{3}{2}}{\overline{\mathrm{\Psi }}}_0^{\frac{1}{2}}}{\theta }log\frac{n{\mu }^0}{ϵ}\rceil .$$

(4.11)

Proof Using Proposition 4.14 with $\gamma :=\frac{1}{2}$ and $\lambda :=\frac{1}{4(1+\sqrt{2})(1+2\kappa )\sigma {(logp)}^{\frac{3}{2}}}$, we obtain the number of inner iterations $4\sqrt{2}(2+\sqrt{2})(1+2\kappa )\sigma {(logp)}^{\frac{3}{2}}{\overline{\mathrm{\Psi }}}_0^{\frac{1}{2}}$. If the central path parameter μ has the initial value ${\mu }^0>0$ and is updated by multiplying $1-\theta$, $0<\theta <1$, then after at most $\lceil \frac{1}{\theta }log\frac{n{\mu }^0}{ϵ}\rceil$ iterations we have $n\mu <ϵ$ [18]. For the total number of iterations, we multiply the number of inner iterations by that of the outer iterations. Hence the total number of iterations is bounded by $\lceil \frac{8(1+\sqrt{2})(1+2\kappa )\sigma {(logp)}^{\frac{3}{2}}{\overline{\mathrm{\Psi }}}_0^{\frac{1}{2}}}{\theta }log\frac{n{\mu }^0}{ϵ}\rceil$. □

5 Concluding remarks

Wang-Bai [16] defined a parametric version of the kernel function in [14], the parameter is in the growth term of the kernel function, and generalized the algorithm for LO to $P_{\ast }(\kappa )$-LCPs based on this kernel function. Ghami-Roos-Steihaug [19] extended the algorithm for LO to semidefinite optimization based on the kernel function in [16]. However, they obtained the best known complexity bound for large-update methods when the kernel function takes the form in [14].

Motivated by this, we consider a parametric version of the kernel function in [14] with parameters in the barrier term of the kernel function. For large-update methods, by taking $\tau =\mathcal{O}(n)$ and $\theta =\mathrm{\Theta }(1)$, we obtained $\mathcal{O}((1+2\kappa ){(logp)}^3\sqrt{n}(logn)log\frac{n{\mu }^0}{ϵ})$, for $p\ge e$, which is the best known complexity bound for such a method.

Further research will be concerned with a numerical test and extension to general problems.