1 Introduction

The area of linear optimization (LO) has become very active since Karmarkar’s [27] first interior-point method (IPM) was published on this subject. Later on, a large amount of papers appeared and the most important results were summarized in the monographs written by Roos, Terlaky and Vial [46], Wright [57] and Ye [58]. It turned out that IPMs are more efficient in practice than pivot algorithms in the case of large sparse problems. Illés and Terlaky [26] presented a comparison between the IPMs and pivot methods from practical and theoretical point of view. Nowadays, state-of-the-art implementations of interior-point solvers are available. Lustig et al. [34, 35] as well as Mehrotra [38] made important contributions to this field. Some significant aspects of implementations techniques were presented by Andersen et al. [7], by Mészáros [39] and by Gondzio and Terlaky [18], respectively.

Recently, the algorithms proposed for solving LO problems have been extended to more general optimization problems such as semidefinite optimization (SDO), second-order cone optimization (SOCO), symmetric optimization (SO) and linear complementarity problems (LCPs). Nesterov and Nemirovskii [41] introduced the concept of self-concordant barrier functions in order to define IPMs for solving convex optimization problems. Klerk [30] proposed a general framework for solving SDO problems. Beside this, he studied the concept of self-dual embeddings for SDO. Alizadeh and Goldfarb [6] used Euclidean Jordan algebras in order to investigate the theory of SOCO. Schmieta and Alizadeh [47] extended the commutative class of primal-dual IPMs for SDO proposed by Monteiro and Zhang [40] to SO. Furthermore, Vieira [50] presented different IPMs for SO based on kernel functions.

Some key contributions to the field of LCPs are summarized in the monograph of Cottle et al. [12]. Kojima et al. [31] presented a unified approach to IPMs for LCPs. Kojima, Mizuno and Yoshise [33] proposed an IPM for a class of LCPs with positive semidefinite matrices. Kojima, Megiddo and Ye [32] introduced a new potential reduction algorithm for solving LCPs. Potra and Sheng [44, 45] defined a predictor-corrector algorithm and a large step infeasible IPM for the \(P_*(\kappa )\)-matrix LCPs. Moreover, Illés and Nagy [22] and Potra [43] devised Mizuno-Todd-Ye type algorithms for LCPs. It turned out that LCPs have important applications in the field of economics. One of these is the Arrow-Debreu market equilibrium model. Ye [59] showed that some market equilibrium models are equivalent to LCPs that are not necessarily sufficient. Therefore, Illés, Nagy and Terlaky [23–25] analysed the question of solvability of general LCPs.

It emerged that specifying a proper search direction plays a key role in the analysis of the IPMs. In [42] Peng, Roos and Terlaky introduced the notion of self-regular barriers and they determined new large-update IPMs with better iteration bounds than the long step interior-point algorithms studied before. The first algorithm which works in a wide neighbourhood and enjoys the same complexity as the best known short-update IPMs was presented by Ai and Zhang [5] for monotone LCPs.

In 2002 Darvay introduced a new technique for finding search directions for LO problems [13, 15]. The new technique is based on an equivalent transformation on the centering equations of the central path. The new search directions are obtained by applying Newton’s method to the resulting system. Infeasible IPMs for LO based on this technique were proposed in [4, 17]. In 2006, Achache generalized this method for convex quadratic programming [2]. Many variations of the technique appeared for LCPs. Achache [1] and Wang et al. [55, 56] generalized the weighted-path-following method introduced in [14] to LCPs, monotone mixed LCPs and monotone horizontal LCPs, respectively. Achache [3], Asadi and Mansouri [8, 9], Mansouri and Pirhaji [36] and Kheirfam [29] presented numerical results on LCPs based on this technique. Wang and Bai [52] and Mansouri et al. [37] extended this approach to SDO problems. Furthermore, Bai, Wang and Luo proposed a new method for convex quadratic SDO [11]. Bai, Sun and Chen extended this algorithm to semidefinite LCPs [10]. Wang and Bai presented new full Nesterov-Todd step primal-dual algorithms for SOCO [53] and for SO [54]. Kheirfam introduced an infeasible IPM for SO in [28]. Wang defined a new polynomial interior-point algorithm for the monotone LCPs over symmetric cones with full Nesterov-Todd step [51].

In the above mentioned papers generally the square root function is used to obtain an equivalent form of the central path. The idea of using a new function, namely the difference of the identity and the square root function was raised in [16]. In this paper we analyse the complexity of the algorithm proposed in [16] and we prove its polynomiality. The paper is organized in the following way. In the second section the LO problem and the central path are presented. Section 3 contains the method used for the determination of the search direction. In the fourth section the new primal-dual algorithm is introduced, which is based on the new search direction. The fifth section is about the complexity analysis of the algorithm, where it is proved that the method solves the problem in polynomial time. The sixth section contains some numerical results. Finally, some conclusions are enumerated.

We present some notations used throughout the paper. Let x and s be two n-dimensional vectors. Then, xs denotes the componentwise product of the vectors x and s, i.e. \( x s=[x_1 s_1, x_2 s_2, \ldots , x_n s_n]^T.\) We also use the notation \(\frac{x}{s}=\left[ \frac{x_1}{s_1}, \frac{x_2}{s_2},\ldots ,\frac{x_n}{s_n}\right] ^T\), where \(s_i \ne 0\) for all \(1 \le i \le n\). For an arbitrary univariate function f and a vector x, if each component of x belongs to the domain of f, then we define \(f( x)=\left[ f(x_1), f(x_2), \ldots , f(x_n)\right] ^T\). Thus, if \(x \ge 0\), then \(\sqrt{x}\) is the vector obtained by taking square roots of the components of x. Furthermore, \(e= [1, 1, \ldots , 1]^T\) denotes the n-dimensional all-one vector and let \(\mathbb {R}^+ = \{ x\in \mathbb {R} \mid x\ge 0\}\). Moreover, diag(x) is a diagonal matrix, which contains on his main diagonal the elements of x in the original order. Beside these, \(\Vert x \Vert \) denotes the Euclidean norm, \(\Vert x \Vert _\infty \) the Chebyshev norm, \(\Vert x \Vert _1\) the 1-norm, and \(\min (x)\) the minimal component of x. Finally, if \(f(t) \ge 0\) and \(g(t) \ge 0\) are real valued functions, then \(f(t) = O( g(t) )\) means that there exists a positive constant \(\gamma \) so that \(f(t) \le \gamma g(t)\).

2 The LO problem

In this section we introduce the LO problem. Let us consider the following problem:

where \(A \in \mathbb {R}^{m \times n}\) with \(rank(A)=m\), \(b \in \mathbb {R}^m\) and \(c \in \mathbb {R}^n\). The dual of this problem can be written in the following form:

figure a

We suppose that the interior-point condition (IPC) holds for both problems, which means that there exists \(( x^0, y^0, s^0)\) such that

$$\begin{aligned} A x^0= & {} b,\quad x^0> 0,\\ A^T y^0+ s^0= & {} c,\quad s^0> 0. \end{aligned}$$

Using the self-dual embedding model presented by Ye, Todd and Mizuno [60] and Terlaky [49] we conclude that the IPC can be assumed without loss of generality. In this case the all-one vector can be considered as a starting point.

The optimal solution of the primal-dual pair can be given with the following system of equations:

$$\begin{aligned} A x= & {} b,\quad x \ge 0,\nonumber \\ A^T y+ s= & {} c,\quad s \ge 0,\\ x s= & {} 0.\nonumber \end{aligned}$$
(2.1)

The first two equations of system (2.1) are named feasibility conditions and the last one is called complementarity condition. In IPMs we replace the complementary condition by a parameterized equation. Hence, we obtain the following system of equations:

$$\begin{aligned} A x= & {} b,\quad x\ge 0,\nonumber \\ A^T y+ s= & {} c,\quad s\ge 0,\\ x s= & {} \mu e.\nonumber \end{aligned}$$
(2.2)

If the IPC holds, then for a fixed \(\mu >0\) system (2.2) has unique solution, which is called the \(\mu \) -center or analytic center (Sonnevend [48]). The set of \(\mu \)-centers formes an analytic curve [19, 20], which is called central path. If \(\mu \) tends to zero, then the central path converges to the optimal solution of the problem.

Detailed analysis of the existence and uniqueness of the central path and some important concepts such as the IPC and self-dual embedding can be found in Chapter 2 of [46] and in Chapters 1 and 2 of [21].

3 Search directions

Using [15] we define a method for finding search directions for IPMs. Let us consider the continuously differentiable function \(\varphi :\mathbb {R}^+ \rightarrow \mathbb {R}^+.\) Assume that the inverse function \(\varphi ^{-1}\) exists. Observe that system (2.2) can be written in the following equivalent form:

$$\begin{aligned} A x= & {} b,\quad x\ge 0,\nonumber \\ A^T y+ s= & {} c,\quad s\ge 0,\\ \varphi \left( \frac{ x s}{\mu }\right)= & {} \varphi ( e),\nonumber \end{aligned}$$
(3.1)

and applying Newton’s method yields new search directions. Let

$$\begin{aligned} v=\sqrt{\frac{ x s}{\mu }}, \end{aligned}$$

and assume that we have \(A x= b\), and \(A^T y+ s= c\) for a triple ( x, y, s) such that \( x> 0\) and \( s> 0\). We get

$$\begin{aligned} \begin{array}{c} \displaystyle A\Delta x= 0,\\ \displaystyle A^T\Delta y+\Delta s= 0,\\ \displaystyle \frac{ s}{\mu }\varphi \prime \left( \frac{ x s}{\mu }\right) \Delta x + \frac{ x}{\mu }\varphi \prime \left( \frac{ x s}{\mu }\right) \Delta s =\varphi ( e)-\varphi \left( \frac{ x s}{\mu }\right) . \end{array} \end{aligned}$$
(3.2)

Let

$$\begin{aligned} d_x = \frac{ v\Delta x}{ x},\quad d_s = \frac{ v\Delta s}{ s}. \end{aligned}$$

Then,

$$\begin{aligned} \mu v( d_x + d_s) = s\Delta x+ x\Delta s, \end{aligned}$$
(3.3)

and

$$\begin{aligned} d_x d_s=\frac{\Delta x\Delta s}{\mu }. \end{aligned}$$
(3.4)

Let us introduce the \(\bar{A}=\frac{1}{\mu }Adiag(\frac{ x}{ v})\) notation. Thus, system (3.2) can be written in the form

$$\begin{aligned} \bar{A} d_x= & {} 0,\nonumber \\ \bar{A}^T\Delta y+ d_s= & {} 0,\\ d_x+ d_s= & {} p_v,\nonumber \end{aligned}$$
(3.5)

where

$$\begin{aligned} p_v=\frac{\varphi ( e)-\varphi ( v^2)}{ v\varphi \prime ( v^2)}. \end{aligned}$$

For different \(\varphi \) functions we obtain different values for the \(p_v\) vector that lead to new search directions. An alternative approach for determining the \(p_v\) vector could be using self-regular barriers [42]. Let us consider \(p_v\) as a function of v. In all the cases studied in the literature this function is defined on the whole positive orthant. However, if the points generated by the algorithm are perfectly centered, then we have the \(v=e\) equality. Therefore, our goal is to analyse a case where the domain of the above mentioned function is a restriction of the positive orthant, but it contains the e vector. That is why we propose a new \(\varphi \) function, namely \(\varphi (t)=t-\sqrt{t}\), which gives a new search direction.

4 A new primal-dual algorithm

This section presents a new form of the primal-dual interior-point algorithm based on the corresponding search directions, using the function \(\varphi (t)=t-\sqrt{t}\). In this case

$$\begin{aligned} p_v=\frac{2(v-v^2)}{2v-e}. \end{aligned}$$
(4.1)

It should be mentioned that the components of the vector \(p_v\) are defined on the \(\left( \frac{1}{2}, +\infty \right) \) interval. We can give a proximity measure to the central path as follows:

$$\begin{aligned} \delta ( x, s; \mu ) = \frac{\Vert p_v\Vert }{2} = \left\| \frac{v-v^2}{2v-e}\right\| . \end{aligned}$$

Let

$$\begin{aligned} q_v= d_x - d_s. \end{aligned}$$

Considering (3.5) we have \( d_x^T d_s=0\). Thus, the vectors \( d_x\) and \( d_s\) are orthogonal, which implies

$$\begin{aligned} \Vert p_v\Vert =\Vert q_v\Vert . \end{aligned}$$

We mention that as an effect of this relation we can also express the proximity measure using \(q_v\), thus

$$\begin{aligned} \delta ( x, s; \mu ) = \frac{\Vert q_v\Vert }{2}. \end{aligned}$$

Moreover,

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

and we have

$$\begin{aligned} d_x d_s=\frac{ p_v^2- q_v^2}{4}. \end{aligned}$$
(4.2)

Thus, the algorithm can be defined as in Fig. 1.

Fig. 1
figure 1

Primal-dual interior-point algorithm for LO

Full size image

The following section is meant to prove the polynomiality of the algorithm.

5 Convergence analysis

The first lemma will investigate the feasibility of the full-Newton step. We prove that feasibility is accomplished if a condition on the proximity measure holds. Let \( x_+= x+\Delta x\) and \( s_+= s+\Delta s\) be the vectors obtained after a full-Newton step.

Lemma 5.1

Let \(\delta =\delta ( x, s; \mu )<1\) and assume that \(v>\frac{1}{2}e\). Then,

$$\begin{aligned} x_+> 0\quad \text{ and }\quad s_+> 0. \end{aligned}$$

Thus, we conclude that the full-Newton step is strictly feasible.

Proof

For each \(0\le \alpha \le 1\) denote \( x_+(\alpha )= x+\alpha \Delta x\) and \( s_+(\alpha )= s+\alpha \Delta s\). Therefore,

$$\begin{aligned} x_+(\alpha ) s_+(\alpha )= x s+ \alpha ( s\Delta x+ x\Delta s)+\alpha ^2\Delta x\Delta s. \end{aligned}$$

Using (3.3) and (3.4) we get

$$\begin{aligned} \frac{1}{\mu } x_+(\alpha ) s_+(\alpha )= v^2+\alpha v( d_x+ d_s)+\alpha ^2 d_x d_s. \end{aligned}$$
(5.1)

From (3.5) and (4.2) it follows that

$$\begin{aligned} \frac{1}{\mu } x_+(\alpha ) s_+(\alpha )= (1-\alpha ) v^2+\alpha ( v^2+ v p_v)+ \alpha ^2\left( \frac{ p_v^2}{4}- \frac{ q_v^2}{4}\right) . \end{aligned}$$

Moreover, from (4.1) we obtain

$$\begin{aligned} v^2+ v p_v = v^2+\frac{2(v^2-v^3)}{2v-e}= \frac{v^2}{2v-e}, \end{aligned}$$
(5.2)

and for this reason we get

$$\begin{aligned} \frac{1}{\mu } x_+(\alpha ) s_+(\alpha )= (1-\alpha ) v^2+\alpha \left( e+\frac{(v-e)^2}{2v-e}+\alpha \frac{ p_v^2}{4}-\alpha \frac{ q_v^2}{4}\right) . \end{aligned}$$
(5.3)

Using \(v>\frac{1}{2}e\) we obtain

$$\begin{aligned} \frac{(v-e)^2}{2v-e} \ge - \frac{p_v^2}{4}. \end{aligned}$$

Thus,

$$\begin{aligned} \frac{1}{\mu } x_+(\alpha ) s_+(\alpha )\ge (1-\alpha ) v^2+\alpha \left( e-(1-\alpha )\frac{ p_v^2}{4}-\alpha \frac{ q_v^2}{4}\right) . \end{aligned}$$

The inequality \( x_+(\alpha ) s_+(\alpha )> 0\) holds if

$$\begin{aligned} \left\| (1-\alpha )\frac{ p_v^2}{4}+ \alpha \frac{ q_v^2}{4}\right\| _\infty <1. \end{aligned}$$

We have

$$\begin{aligned} \left\| (1-\alpha )\frac{ p_v^2}{4}+ \alpha \frac{ q_v^2}{4}\right\| _\infty\le & {} (1-\alpha )\frac{\Vert p_v^2\Vert _\infty }{4}+ \alpha \frac{\Vert q_v^2\Vert _\infty }{4} \\\le & {} (1-\alpha )\frac{\Vert p_v\Vert ^2}{4}+ \alpha \frac{\Vert q_v\Vert ^2}{4}=\delta ^2<1. \end{aligned}$$

Thus, we obtain that for each \(0\le \alpha \le 1\) the \( x_+(\alpha ) s_+(\alpha )> 0\) inequality holds, which means that the linear functions of \(\alpha \), \( x_+(\alpha )\) and \( s_+(\alpha )\) do not change sign on the interval [0, 1]. Consequently, \( x_+(0)= x> 0\) and \( s_+(0)= s> 0\) yields \( x_+(1)= x_+> 0\) and \( s_+(1)= s_+> 0\). \(\square \)

The following lemma will be used in the next part of the analysis.

Lemma 5.2

Let \(f{:}D \rightarrow \left( 0, +\infty \right) \) be a decreasing function, where \(D=[d,+\infty ]\), \(d>0\). Furthermore, let us consider the vector \(v \in \mathbb {R}_+^{n}\) such that \(\min (v)>d\). Then,

$$\begin{aligned} \left\| f(v) \cdot ( e - v^2)\right\| \le f(\min (v)) \cdot \Vert e - v^2 \Vert \le f(d) \cdot \Vert e - v^2\Vert . \end{aligned}$$

Proof

We have

$$\begin{aligned} \left\| f(v) \cdot (e- v^2)\right\|= & {} \sqrt{\sum _{i=1}^{n} \big (f(v_i)\big )^2 \big (1 -v_i^{2}\big )^2 } \\\le & {} f(\min (v)) \cdot \sqrt{\sum _{i=1}^{n}\big (1 -v_i^{2}\big )^2} \\= & {} f(\min (v)) \cdot \Vert e - v^2\Vert \\\le & {} f(d) \cdot \Vert e - v^2\Vert . \end{aligned}$$

\(\square \)

The second lemma is meant to analyse the conditions under which the Newton process is quadratically convergent.

Lemma 5.3

Suppose that \(\delta =\delta ( x, s; \mu )<\frac{1}{2}\) and \(v> \frac{1}{2}e\). Then, \(v_+>\frac{1}{2}e\) and

$$\begin{aligned} \delta ( x_+, s_+; \mu )\le \frac{3-3\delta ^2-3\sqrt{1-\delta ^2}(1-2\delta ^2)}{3-4\delta ^2} . \end{aligned}$$
(5.4)

In addition,

$$\begin{aligned} \delta (x_+,s_+;\mu )< \frac{9-3\sqrt{3}}{2}\delta ^2, \end{aligned}$$
(5.5)

which means that the full-Newton step ensures local quadratic convergence of the proximity measure.

Proof

We know from Lemma 5.1 that \( x_+> 0\) and \( s_+> 0\). Considering the notation

$$\begin{aligned} v_+=\sqrt{\frac{ x_+ s_+}{\mu }} \end{aligned}$$

and the substitution \(\alpha =1\) in (5.3), after some reductions we obtain

$$\begin{aligned} v_+^2= e- \frac{e-2v-v^2}{v^2}\cdot \frac{p_v^2}{4}-\frac{ q_v^2}{4}. \end{aligned}$$
(5.6)

From the condition \(v>\frac{1}{2}e\) we get \(v^2+2v-e>0\) and this implies \(v_+^2 \ge e - \frac{q_v^2}{4}\). Consequently,

$$\begin{aligned} \min ( v_+)\ge \sqrt{1-\frac{1}{4}\Vert q_v^2\Vert _\infty }\ge \sqrt{1-\frac{\Vert q_v\Vert ^2}{4}}=\sqrt{1-\delta ^2}. \end{aligned}$$
(5.7)

From \(\delta <\frac{1}{2} \) it follows that \(min(v_+) > \frac{\sqrt{3}}{2}\), hence \(v_+ > \frac{1}{2}e\). Moreover, we have

$$\begin{aligned} \delta (x_+,s_+;\mu )=\left\| \frac{v_+-v_+^2}{2v_+-e}\right\| =\left\| \frac{v_+}{(2v_+-e)(e+v_+)}\cdot (e-v_+^2)\right\| . \end{aligned}$$

Let us consider the function \(f(t)=\frac{t}{(2t-1)(1+t)}>0\) for all \(t>\frac{1}{2}\). From \(f'(t)<0\) it follows that f is decreasing, therefore using (5.7) and Lemma 5.2 we obtain

$$\begin{aligned} \delta (x_+,s_+;\mu ) \le \frac{\sqrt{1-\delta ^2}}{2(1-\delta ^2)+\sqrt{1-\delta ^2}-1}\cdot \Vert e-v_+^2\Vert . \end{aligned}$$
(5.8)

We write f(t) in the following way:

$$\begin{aligned} f(t) = \frac{t(2t+1)(1-t)}{(4t^2-1)(1-t^2)}. \end{aligned}$$

Substituting \(\sqrt{1-\delta ^2}\) and making some elementary reductions we obtain

$$\begin{aligned} f\left( \sqrt{1-\delta ^2}\right) = \frac{1-\delta ^2-\sqrt{1-\delta ^2}(1-2\delta ^2)}{\delta ^2(3-4\delta ^2)}. \end{aligned}$$
(5.9)

We have \(1<\frac{t^2+2t-1}{t^2}\le 2\) for all \(t > \frac{1}{2}\) and

$$\begin{aligned} e-v_+^2= \frac{e-2v-v^2}{v^2}\cdot \frac{p_v^2}{4}+\frac{q_v^2}{4}. \end{aligned}$$

Thus,

$$\begin{aligned} \Vert e-v_+^2\Vert \le 2\left\| -\frac{p_v^2}{4}\right\| +\left\| \frac{q_v^2}{4}\right\| \le 2\delta ^2+\delta ^2=3\delta ^2, \end{aligned}$$
(5.10)

and using (5.8) and (5.9) we get (5.4), which proves the first part of the lemma. Moreover, we have

$$\begin{aligned} \delta (x_+,s_+;\mu ) \le \frac{3\left( 1-\sqrt{1-\delta ^2}\right) }{3-4\delta ^2} + \frac{3\delta ^2\left( -1+2\sqrt{1-\delta ^2}\right) }{3-4\delta ^2}. \end{aligned}$$

Let

$$\begin{aligned} \phi _1(\delta ) :=\frac{3\left( 1-\sqrt{1-\delta ^2}\right) }{3-4\delta ^2}\quad \text{ and }\quad \phi _2(\delta ) := \frac{3\delta ^2\left( -1+2\sqrt{1-\delta ^2}\right) }{3-4\delta ^2}. \end{aligned}$$

From \(\delta < \frac{1}{2}\) it follows that \(1+\sqrt{1-\delta ^2} > \frac{2+\sqrt{3}}{2} \). We get

$$\begin{aligned} \frac{1}{1+\sqrt{1-\delta ^2}}<4-2\sqrt{3}, \end{aligned}$$

and

$$\begin{aligned} \frac{1}{3}\phi _1(\delta )< \frac{4-2\sqrt{3}}{3-4\delta ^2}\delta ^2. \end{aligned}$$

Furthermore, if \(\delta <\frac{1}{2}\), then \(4\delta ^2 < 1\). Thus, \( \frac{1}{3-4\delta ^2} < \frac{1}{2}\) and we obtain

$$\begin{aligned} \frac{1}{3}\phi _1(\delta ) < \frac{4-2\sqrt{3}}{2}\delta ^2. \end{aligned}$$
(5.11)

A simple calculus yields

$$\begin{aligned} \frac{1}{3}\phi _2(\delta ) = \frac{\delta ^2}{1+2\sqrt{1-\delta ^2}}. \end{aligned}$$

We have \(\frac{1}{1+2\sqrt{1-\delta ^2}} <\frac{\sqrt{3}-1}{2}\) and

$$\begin{aligned} \frac{1}{3}\phi _2(\delta ) < \frac{\sqrt{3}-1}{2}\delta ^2. \end{aligned}$$
(5.12)

From (5.11) and (5.12) we obtain

$$\begin{aligned} \frac{1}{3}\big (\phi _1(\delta )+\phi _2(\delta )\big )<\frac{4-2\sqrt{3}+\sqrt{3}-1}{2}\delta ^2 = \frac{3-\sqrt{3}}{2}\delta ^2, \end{aligned}$$

and this results in (5.5), which proves the lemma. \(\square \)

The next lemma examines what is the effect of the full-Newton step on the duality gap.

Lemma 5.4

Let \(\delta =\delta ( x, s;\mu )\) and suppose that the vectors \( x_+\) and \( s_+\) are obtained using a full-Newton step, thus \( x_+= x+\Delta x\) and \( s_+= s+\Delta s\). We have

$$\begin{aligned} ( x_+)^T s_+ \le \mu (n+\delta ^2), \end{aligned}$$

and if \(\delta <\frac{1}{2}\), then \(( x_+)^T s_+<\mu \left( n+\frac{1}{4} \right) \).

Proof

Substituting \(\alpha =1\) in (5.1) and using (3.5) we have

$$\begin{aligned} \frac{1}{\mu } x_+ s_+= v^2+vp_v+d_xd_s. \end{aligned}$$

Using (4.1) and (5.2) we deduce

$$\begin{aligned} \frac{1}{\mu } x_+ s_+\le e+\frac{ p_v^2}{4}+d_xd_s. \end{aligned}$$

Therefore, using the orthogonality of the vectors \(d_x\) and \(d_s\) we obtain

$$\begin{aligned} ( x_+)^T s_+= & {} e^T( x_+ s_+) \,\le \, \mu ( e^T e+\frac{ e^T p_v^2}{4}+e^Td_xd_s)\,=\, \mu (n+\frac{\Vert p_v\Vert ^2}{4}+d_x^Td_s)\\= & {} \mu (n+\delta ^2). \end{aligned}$$

This completes the first part of the lemma. From \(\delta <\frac{1}{2}\) we have \(\delta ^2<\frac{1}{4}\). Using this we obtain

$$\begin{aligned} ( x_+)^T s_+ < \mu \left( n+\frac{1}{4} \right) , \end{aligned}$$

which proves the second statement of the lemma.

In the next lemma we analyse the effect which a Newton step followed by an update of the parameter \(\mu \) has on the proximity measure. Suppose that \(\mu \) is reduced by the factor \((1-\theta )\) in every iteration.

Lemma 5.5

Let \(\delta =\delta ( x, s; \mu )<\frac{1}{2}\), \(v>\frac{1}{2}e\), \(\mu _+=(1-\theta )\mu \), \(v_\sharp =\sqrt{\frac{x_+s_+}{\mu _+}}\) and \(\eta =\sqrt{1-\theta }\), where \(0<\theta <1\). Then \(v_\sharp >\frac{1}{2}e\) and

$$\begin{aligned} \delta ( x_+, s_+; \mu _+)\le \frac{\sqrt{3}(\theta \sqrt{n}+3\delta ^2)}{-2\eta ^3+\sqrt{3}\eta ^2+3\eta }. \end{aligned}$$

Moreover, if \(\theta =\frac{1}{27\sqrt{n}}\) and \(n\ge 4\), then we have \(\delta ( x_+, s_+; \mu _+)<\frac{1}{2}\).

Proof

We have \(v_\sharp =\frac{1}{\eta }v_+\). Using Lemma 5.3 we obtain \(v_+>\frac{1}{2}e\), which yields \(v_\sharp >\frac{1}{2}e\). Hence, we get

$$\begin{aligned} \frac{v_\sharp -v_\sharp ^2}{2v_\sharp -e}=\frac{\frac{1}{\eta }v_+-\frac{1}{\eta ^2}v_+^2}{\frac{2}{\eta }v_+-e}=\frac{\frac{1}{\eta ^2}v_+(\eta e-v_+)}{\frac{1}{\eta }(2v_+-\eta e)}=\frac{v_+(\eta ^2 e- v_+^2)}{\eta (2v_+-\eta e)(\eta e+v_+)}. \end{aligned}$$

Let us consider the function \(h(t)=\frac{t}{(2t-\eta )(\eta +t)}\) for all \(t>\frac{\eta }{2}\). Thus, we may write

$$\begin{aligned} \frac{v_\sharp -v_\sharp ^2}{2v_\sharp -e}=\frac{1}{\eta }h(v_+)(\eta ^2 e-v_+^2). \end{aligned}$$

From \(h'(t)<0\) it follows that h is a decreasing function. Then, similar to the proof of Lemma 5.2 using (5.7) we get

$$\begin{aligned} \delta ( x_+, s_+; \mu _+)\le & {} \frac{\min (v_+)}{\eta (2 \min (v_+)-\eta )(\eta +\min (v_+))}\Vert \eta ^2e-v_+^2\Vert \\\le & {} \frac{1}{\eta }h\left( \sqrt{1-\delta ^2}\right) \Vert \eta ^2 e-v_+^2\Vert . \end{aligned}$$

Using \(\delta <\frac{1}{2}\) we have \(\sqrt{1-\delta ^2}>\frac{\sqrt{3}}{2}\) and \(h\left( \sqrt{1-\delta ^2}\right) <h\left( \frac{\sqrt{3}}{2}\right) \). From \(h\left( \frac{\sqrt{3}}{2}\right) =\frac{\sqrt{3}}{-2\eta ^2+\sqrt{3}\eta +3}\), it follows that

$$\begin{aligned} \delta ( x_+, s_+; \mu _+)<\frac{\sqrt{3}}{-2\eta ^3+\sqrt{3}\eta ^2+3\eta }\Vert \eta ^2e-v_+^2\Vert . \end{aligned}$$

Using (5.10) we have

$$\begin{aligned} \Vert \eta ^2 e-v_+^2\Vert =\Vert (1-\theta )e-v_+^2\Vert \le \Vert -\theta e\Vert +\Vert e-v_+^2\Vert <\theta \sqrt{n}+3\delta ^2, \end{aligned}$$

so we may write

$$\begin{aligned} \delta ( x_+, s_+; \mu _+)\le \frac{\sqrt{3}(\theta \sqrt{n}+3\delta ^2)}{-2\eta ^3+\sqrt{3}\eta ^2+3\eta }. \end{aligned}$$

Using the function \(g(\eta )=\frac{1}{-2\eta ^3+\sqrt{3}\eta ^2+3\eta }\) for all \(0 < \eta <1\) we have

$$\begin{aligned} g'(\eta )=\frac{6\eta ^2-2\sqrt{3}\eta -3}{(-2\eta ^3+\sqrt{3}\eta ^2+3\eta )^2}<0, \quad \text{ for } \text{ all } \quad 0<\eta <1 . \end{aligned}$$

This implies that g is decreasing on the interval (0, 1). Now suppose that \(n\ge 4\) and \(\theta =\frac{1}{27\sqrt{n}}\). Then, we obtain \(\eta \ge \sqrt{\frac{53}{54}}\). From \(\delta <\frac{1}{2}\) we get

$$\begin{aligned} \delta (x_+,s_+;\mu _+) < \sqrt{3}\left( \frac{1}{27}+\frac{3}{4}\right) g\left( \sqrt{\frac{53}{54}}\right) , \end{aligned}$$

and a simple calculus gives \(\delta ( x_+, s_+; \mu _+)<\frac{1}{2}\). \(\square \)

Lemma 5.5 shows that the algorithm is well defined, more exactly that the conditions \(x > 0\), \(s > 0\), \(\delta ( x, s;\mu )<\frac{1}{2}\) and \(v > \frac{1}{2}e\) hold throughout the algorithm. The following lemma investigates the question of the bound on the number of iterations.

Lemma 5.6

We assume that the pair \(( x^0, s^0)\) is strictly feasible, \(\mu ^0=\frac{\left( x^0 \right) ^T s^0}{n}\) and \(\delta ( x^0, s^0;\mu ^0)<\frac{1}{2}\). Let \( x^k\) and \( s^k\) be the two vectors obtained by the algorithm given in Fig. 1 after k iterations. Then, for

$$\begin{aligned} k\ge \left\lceil \frac{1}{\theta } \log \frac{\mu ^0\left( n+\frac{1}{4}\right) }{\epsilon }\right\rceil \end{aligned}$$

we have \(\left( x^k \right) ^T s^k < \epsilon \).

Proof

From Lemma 5.4 we get

$$\begin{aligned} \left( x^k \right) ^T s^k < \mu ^k\left( n+\frac{1}{4}\right) = (1-\theta )^k\mu ^0\left( n+\frac{1}{4}\right) . \end{aligned}$$

This implies that \(\left( x^k\right) ^T s^k < \epsilon \) holds if

$$\begin{aligned} (1-\theta )^k\mu ^0\left( n+\frac{1}{4}\right) \le \epsilon . \end{aligned}$$

Taking logarithms, we may write

$$\begin{aligned} k\log (1-\theta )+\log \left( \mu ^0\left( n+\frac{1}{4}\right) \right) \le \log \epsilon . \end{aligned}$$

As \(-\log (1-\theta )\ge \theta \) we see that the inequality is valid only if

$$\begin{aligned} k\theta \ge \log \left( \mu ^0\left( n+\frac{1}{4}\right) \right) -\log \epsilon = \log \frac{\mu ^0\left( n+\frac{1}{4}\right) }{\epsilon }. \end{aligned}$$

This proves the lemma. \(\square \)

As the self-dual embedding allows us to assume without loss of generality, that \( x^0= s^0= e\), we have \(\mu ^0=1\). This question leads us to the next lemma.

Theorem 5.7

Suppose that \( x^0= s^0= e\). If we consider the default values for \(\theta \) and \(\tau \) we obtain that the algorithm given in Fig. 1 requires no more than

$$\begin{aligned} O\left( \sqrt{n}\log \frac{n}{\epsilon }\right) , \end{aligned}$$

interior-point iterations. The resulting vectors satisfy \( x^T s < \epsilon \).

6 Numerical results

We implemented the algorithm given in Fig. 1 in the \(C++\) programming language in order to analyse its efficiency for different \(\varphi \) functions. We considered the search directions obtained by using the following three \(\varphi \) functions: the identity, the square root map and the difference between the square root and the identity functions. The algorithm performed only full-Newton steps and the barrier update parameter \(\mu \) was reduced by the factor \(1-\theta \). We used for the update parameter \(\theta \) each constant from the set \(\{0.1,\; 0.2,\; 0.3,\; 0.7,\; 0.8,\; 0.9 \}\). In all cases the accuracy parameter had the value \(\epsilon = 10^{-5}\).

Hereafter, we present three problems for which we tested the different versions of the algorithm. It should be mentioned that for all the problems the starting points \(x^0\), \(y^0\) and \(s^0\) satisfy the following condition: \(\sqrt{\frac{x^0s^0}{\mu ^0}}>\frac{e}{2}\), where \(\mu ^0=\frac{\left( x^0 \right) ^T s^0}{n}\).

6.1 Problem 1

We consider the primal-dual pair (P)–(D), where

$$\begin{aligned} A=\left[ \begin{array}{ccccccc} 7 &{} \quad 2 &{} \quad 3 &{} \quad 1 &{} \; -1 &{} \; -2 &{} \quad 4 \\ -4 &{} \; -5 &{} \; -2 &{} \quad 3 &{} \; -5 &{} \quad 9 &{} \quad 6 \\ 2 &{} \quad 7 &{} \; -6 &{} \quad 7 &{} \; -3 &{} \quad 4 &{} \quad 2 \\ 6 &{} \; -6 &{} \; -1 &{} \quad 7 &{} \quad 5 &{} \; -5 &{} \quad 3 \end{array}\right] , \quad b=\left[ \begin{array}{c} 37 \\ 36\\ 97 \\ -59 \end{array}\right] , \quad c=\left[ \begin{array}{c} -42 \\ 26 \\ -59 \\ 71 \\ -86 \\ 143 \\ 68 \end{array}\right] . \end{aligned}$$

The used starting points are the following: \(x^0= \left[ 1,\; 11,\; 4,\; 1,\; 7,\; 11,\; 6 \right] ^T\), \(y^0=\left[ -1,\; 10,\; 8,\; -3 \right] ^T\) and \(s^0= \left[ 7,\; 4,\; 9,\; 7,\; 2,\; 4,\; 5 \right] ^T.\)

In Table 1 we summarize the obtained numbers of iterations for the different search directions and the used update parameters.

Table 1 Number of iterations for Problem 1
Full size table

6.2 Problem 2

Let

$$\begin{aligned} A=\left[ \begin{array}{cccccccccc} 3 &{} \; -5 &{} \quad 2 &{} \; -8 &{} \; -5 &{} \quad 2 &{} \quad 6 &{} \quad 10 &{} \quad 5 &{} \quad 2\\ 2 &{} \; -8 &{} \; -6 &{} \; -7 &{} \quad 6 &{} \quad 5 &{} \quad 5 &{} \quad 6 &{} \; -9 &{} \; -8 \\ 6 &{} \quad 1 &{} \quad 9 &{} \quad 5 &{} \; -2 &{} \quad 3 &{} \quad 10 &{} \; -5 &{} \quad 6 &{} \; -7 \\ 6 &{} \quad 3 &{} \; -2 &{} \quad 1 &{} \; -4 &{} \quad 7 &{} \; -8 &{} \quad 10 &{} \quad 8 &{} \quad 4 \\ 1 &{} \; -3 &{} \; -1 &{} \quad 5 &{} \; -8 &{} \; -4 &{} \quad 4 &{}\quad 1 &{}\quad 4 &{} \; -2 \\ 4 &{} \; -1 &{} \quad 3 &{} \; -2 &{} \quad 5 &{} \; -8 &{} \quad 4 &{} \quad 1 &{} \; -6 &{} \quad 0 \\ 4 &{} \; -2 &{} \quad 6 &{} \; -8 &{} \quad 8 &{} \quad 8 &{} \; -2 &{} \; -1 &{} \quad 6 &{} \quad 7 \\ 8 &{} \quad 0 &{} \; -9 &{} \; -5 &{} \quad 5 &{} \quad 4 &{} \; -8 &{} \; -6 &{} \quad 5 &{} \quad 5 \end{array}\right] , \quad b=\left[ \begin{array}{c} 49 \\ 0 \\ 22 \\ 84 \\ -42 \\ -14 \\ 108\\ 15 \end{array}\right] , \quad c=\left[ \begin{array}{c} 103 \\ -39 \\ -131 \\ -140 \\ 236 \\ 134 \\ -164 \\ 7 \\ -49 \\ 70 \end{array}\right] . \end{aligned}$$

We consider the following starting points: \(x^0= \left[ 1,\; 2,\; 2,\; 1,\; 4,\; 5,\; 2,\; 4,\; 2,\; 4 \right] ^T\), \(y^0=\left[ -9,\; 10,\; -6,\; 5,\; 0,\; 3,\; 10,\; 7 \right] ^T\) and \(s^0= \left[ 8,\; 10,\; 5,\; 4,\; 9,\; 1,\; 4,\; 6,\; 5,\; 1 \right] ^T.\)

Table 2 contains the obtained results that refer to Problem 2.

Table 2 Number of iterations for Problem 2
Full size table

6.3 Problem 3

Let us consider

$$\begin{aligned} A=\left[ \begin{array}{ccccccccc} 1 &{} \; -4 &{} \; -3 &{} \quad 7 &{} \quad 9 &{} \quad 3 &{} \; -1 &{} \quad 7 &{} \; -5 \\ -9 &{} \quad 1 &{} \quad 5 &{} \; -5 &{} \quad 10 &{} \; -8 &{} \quad 10 &{} \; -7 &{} \quad 3 \\ 0 &{} \quad 2 &{} \; -3 &{} \quad 5 &{} \; -1 &{} \; -6 &{} \quad 2 &{} \; -3 &{} \; -9 \\ 0 &{} \quad 4 &{} \quad 8 &{} \quad 7 &{} \quad 8 &{} \; -2 &{} \quad 1 &{} \; -6 &{} \quad 0 \\ -7 &{} \quad 6 &{} \; -7 &{} \quad 0 &{} \; -5 &{} \quad 8 &{} \quad 8 &{} \quad 6 &{} \; -4 \\ -9 &{} \quad 10 &{} \; -4 &{} \; -9 &{} \quad 0 &{} \quad 8 &{} \; -5 &{} \quad 3 &{} \; -9 \\ 7 &{} \; -6 &{} \quad 0 &{} \quad 8 &{} \; -3 &{} \; -4 &{} \; -1 &{} \quad 1 &{} \; -3 \end{array}\right] ,\quad b=\left[ \begin{array}{c} -19 \\ 75\\ -86 \\ 118 \\ -4 \\ -55 \\ -65 \end{array}\right] ,\quad c=\left[ \begin{array}{c} -156 \\ 139 \\ 5 \\ -49 \\ 34 \\ 71 \\ 115 \\ -3 \\ -41 \end{array}\right] . \end{aligned}$$

We used the following starting points: \(x^0= \left[ 5,\; 9,\; 6,\; 1,\; 5,\; 3,\; 5,\; 2,\; 8 \right] ^T\), \(y^0=\left[ -3,\; 6,\; -3,\; 6,\; 10,\; 6,\; 3 \right] ^T\) and \(s^0= \left[ 4,\; 1,\; 3,\; 5,\; 9,\; 6,\; 5,\; 6,\; 2 \right] ^T.\)

The obtained numbers of iterations for the different cases are presented in Table 3.

Table 3 Number of iterations for Problem 3
Full size table

It can be observed that for the selected problems the algorithm which uses the proposed search direction gives better results than the two other studied methods. The used problems are small-sized and dense. Therefore, as a further research the effieciency of our algorithm could be analysed for large, sparse problems as well.

7 Conclusion

In this paper we used the method introduced in [15] to obtain a new search direction for IPMs. This approach is based on applying Newton’s method on an equivalent form of the central path (2.2). We used the function \(\varphi (t)=t-\sqrt{t}\) in order to define a new primal-dual IPM. Because of the specific character of this function we had to ensure that in each iteration of the algorithm the components of the vectors in the v-space are greater than \(\frac{1}{2}\). Therefore, the complexity analysis turned out to be more difficult than in the usual case. We proved that this short-update algorithm has the iteration bound \(O(\sqrt{n}\log \frac{n}{\epsilon })\). Moreover, we provided some numerical experiments that demonstrate the efficiency of the proposed algorithm.