1 Introduction

Linear optimization (LO) problems have been extensively studied since Karmarkar [19] introduced his well-known projective interior point method (IPM), which enjoyed polynomial complexity. In the last decades several researchers published new methods in this field. The most important results were summarized in the books written by Roos et al. [33], Wright [41] and Ye [42]. Terlaky [36] presented an introduction to the duality theory of LO from the point of view of the IPMs. In spite of the fact that the simplex method introduced by Dantzig [8] proved to be efficient in practice, Gondzio and Terlaky [13] and Andersen et al. [4] established that in several cases, especially when the size of the problem is large, IPMs can perform better. We mention that in the case of the simplex algorithm we usually keep primal or dual feasibility. The criss-cross methods represent other pivoting algorithms where the basic solutions can be both primal and dual infeasible as in the papers published by Klafszky and Terlaky [21] and Terlaky [35]. Illés and Terlaky [14] presented a detailed comparison between the pivot algorithms and IPMs. The determination of the starting point is an important question in the case of the IPMs. In theory, a good starting point can be chosen by using the self-dual embedding model introduced by Jansen et al. [18] and Ye et al. [43].

IPMs can be classified based on the length of the step and the used neighbourhood. In this way the algorithms that generate the new iterates in a smaller neighbourhood of the central path are named short-update methods, and the ones that use a wider neighbourhood are called large-update algorithms. Large-update methods turned out to be more efficient in practice, while the small-update ones have better theoretical complexity. Peng et al. [28] developed the concept of self-regular proximities. Using this notion, they introduced a new class of search directions in order to define polynomial primal–dual IPMs for LO, semidefinite optimization (SDO), and second-order cone optimization (SOCO). Besides, they reduced the above-mentioned gap between the large-update and small-update methods. Later on, Later on, Potra [30] and Ai and Zhang [3] introduced large-update IPMs for linear complementarity problems (LCPs) that have the same complexity as the best small-update IPMs. Li and Terlaky [23] proposed the first IPM for SDO, which works in a wide neighbourhood and has \(O(\sqrt{n}L)\) iteration complexity.

The determination of the search directions plays a key role in case of the IPMs. Therefore, the search directions can be obtained by using barrier functions based on their corresponding kernel functions. Bai et al. [6, 7] proposed a new type of barrier function which has a finite value at the boundary of the feasible region. Beside this, polynomial-time IPMs for convex optimization problems can be obtained by using self-concordant barriers introduced by Nesterov and Nemirovskii [27].

Another method for defining search directions for LO was given by Darvay [9, 10]. The main idea of this approach consisted in considering an algebraic equivalent transformation on the system which characterizes the central path. Firstly, the centering equations were divided by the barrier update parameter. After that the same continuously differentiable and invertible function \(\varphi \) was applied to both sides of the previously modified equation. In this way the equation \(\varphi (v) = \varphi (e)\) was obtained, where v is the variance vector \(v=\sqrt{\frac{xs}{\mu }}\); \(\mu \) is the barrier parameter; and e is the n-dimensional all-one vector (for details see Sect. 4). The new search directions were determined by applying Newton’s method to this equation. Achache [1] generalized this approach to convex quadratic optimization, while Zhang et al. [45] to linearly constrained convex programming problems. Many IPMs were also extended to more general problems, namely to different kind of LCPs. Kojima et al. [22] gave a unified approach to IPMs for LCPs. Potra and Sheng [31, 32] proposed predictor-corrector and infeasible IPMs for \(P^*(\kappa )\)-LCPs. Moreover, Illés et al. [15,16,17] introduced a polynomial-time IPM for general LCPs, which either gives an \(\epsilon \)-solution or it proves that the matrix of the problem does not have \(P^*(\kappa )\) property. Numerical results on LCPs based on Darvay’s technique were reported by Achache [2], Asadi and Mansouri [5], Mansouri and Pirhaji [24], and Kheirfam [20]. It can be observed that these results emphasize the efficiency of this method. Other extensions based on the above-mentioned technique were made to symmetric cone optimization (SCO) problems by Wang and Bai [40], to SDO problems by Wang and Bai [38] and Mansouri et al. [25] and to SOCO by Wang and Bai [39]. Furthermore, Wang [37] generalized this approach to monotone LCPs over symmetric cones.

Recently, Zhang and Xu [44] proposed a specific search direction for LO. They considered the equivalent form \(v^2=v\) of the centering equation, and they transformed it into the form \(xs = \mu v\). After that they assumed that the variance vector is fixed and they used Newton’s method.

In this paper we propose a new method for obtaining a class of search directions using a new type of transformation of the centering equations. First, we modify the nonlinear equation \(v^2=v\) by applying componentwise the function \(\varphi \) to both sides of this equation. Then, we apply Newton’s method in order to get the new search directions. It is worth mentioning that by using the map \(\varphi (t)=t\) we do not obtain the direction given in [44], because we do not consider the variance vector as constant. In order to facilitate our analysis we restrict ourselves to the case \(\varphi (t) = t^2\) which yields a new search direction. It turns out that the sum of the scaled directions is \(p_v=\frac{v-v^3}{2v^2-e}\). Therefore, the analysis of the algorithm becomes more difficult, because we have to ensure that the vector \(p_v\) is well defined. For this, during the whole process of the algorithm we have to guarantee a plus condition, namely the inequality \(v>\frac{1}{\sqrt{2}}e\). We establish the equivalence between the new technique and a proper approach based on kernel functions. It can be observed that the corresponding kernel function is not a usual one, because it is defined only on the interval \(\left( \frac{1}{\sqrt{2}},\infty \right) \). In spite of these facts we prove that the complexity of the algorithm coincides with the best known ones of IPMs for LO.

The paper is organized as follows. In the following section the LO problem and the notion of the central path are presented. In Sect. 3 we give an approach for the determination of the search directions based on kernel functions. Section 4 lays out the main idea of the new technique. Besides, the obtained generic algorithm is presented. Section 5 is devoted to the analysis of the complexity of the new method. Section 6 contains numerical results. In the last section some concluding remarks are enumerated.

The authors dedicate this paper to the honour of Tamás Terlaky on the occasion of his 60th birthday and to the memory of his Phd supervisor, Emil Klafszky.

2 The linear optimization problem

Let us consider the following primal problem

figure a

and it’s dual

figure b

where \(A \in \mathbb {R}^{m \times n}, \quad rank(A)=m, c \in \mathbb {R}^n \quad \) and \( b \in \mathbb {R}^m\).

Without loss of generality we can assume that the interior-point condition (IPC) holds for the primal and dual problems, which means that there exists \((x^0,y^0,s^0)\) such that

figure c

An optimal solution of the primal–dual problem is given by the following system:

$$\begin{aligned} \begin{aligned} Ax&= b,\qquad x \ge 0, \\ A^Ty + s&= c,\qquad s \ge 0,\\ xs&= 0. \end{aligned} \end{aligned}$$
(1)

The first two equations of system (1) are called feasibility conditions and they serve for maintaining feasibility. The third equation is named complementarity condition. The primal–dual interior point methods usually replace the complementarity equation with a parameterized equation. Using this, we obtain the following system:

$$\begin{aligned} \begin{aligned} Ax&= b,\qquad x> 0, \\ A^Ty + s&= c,\qquad s > 0,\\ xs&= \mu e, \end{aligned} \end{aligned}$$
(2)

where \(\mu >0\). If the interior-point condition holds, then for a fixed \(\mu >0\) the \(\mu \)-center or analytic center given by Sonnevend [34] is the unique solution of system (2). For the different values of \(\mu \) we obtain the central path, which converges to an optimal solution of the problem, if \(\mu \rightarrow 0\). Let \(v=\sqrt{\frac{xs}{\mu }}\). Using this, the third equation of (2) can be written in the form: \(v = e\).

3 Search directions using kernel functions

Peng et al. [28] introduced the class of self-regular barrier functions and defined large-update IPMs for solving LO problems.

A function \(\psi \) is called kernel function if the following conditions hold:

  1. i.

    \(\psi : \mathbb {R}_{++} \rightarrow \mathbb {R}_+\) is twice continuously differentiable;

  2. ii.

    \(\psi (1) = \psi ^\prime (1) = 0\);

  3. iii.

    \(\psi ^{\prime \prime }(t) > 0\) for all \(t > 0\),

where \(\mathbb {R}_{+}=\{x \in \mathbb {R}| x \ge 0 \}\) and \(\mathbb {R}_{++}=\{x \in \mathbb {R}| x > 0 \}.\) The kernel function is called coercive if

  1. iv.

    \(\lim _{t \downarrow 0} \psi (t) = \lim _{t \rightarrow \infty } \psi (t) = \infty \).

Assuming that x and (y, s) are feasible solutions of the primal–dual pair, we want to define the search directions \((\varDelta x, \varDelta y, \varDelta s)\) in order to get the new vectors determined by the algorithm.

The idea of introducing these new search directions is based on defining a generalized barrier function \(\varPsi (v)\), \(v \in \mathbb {R}_{++}^n\). It should be mentioned that \(\mathbb {R}_{++}^n=\{x \in \mathbb {R}^n| x_i > 0, i=1,\ldots ,n \}.\) We assume that \(\varPsi (v)\) is minimal at \(v = e\), \(\varPsi (e) = 0\) and \(\varPsi \) is a strictly convex differentiable function.

Using a kernel function \(\psi \), we can construct a barrier function in the following form:

$$\begin{aligned} \varPsi (v) = \sum _{i=1}^{n} \psi (v_i), \end{aligned}$$

and we obtain the search directions:

$$\begin{aligned} \begin{aligned} A\varDelta x&= 0,\\ A^T\varDelta y+\varDelta s&= 0,\\ s\varDelta x+x\varDelta s&= -\sqrt{\mu x s} \; \nabla \varPsi \left( \sqrt{\frac{xs}{\mu }}\right) . \end{aligned} \end{aligned}$$
(3)

In the following section we propose another method for introducing search directions.

4 New search directions using an equivalent algebraic transformation

In this section we modify the technique introduced by Darvay [10] in order to get new search directions. Let us consider the function \(\varphi \) defined and continuously differentiable on the interval \((\kappa ^2,\infty )\), where \(0 \le \kappa < 1\), such that \(2t\varphi '(t^2)-\varphi '(t)> 0, \forall t>\kappa ^2\). Using this, system (2) can be written in the following form:

$$\begin{aligned} \begin{aligned} Ax&= b,\qquad x> 0,\\ A^Ty + s&= c,\qquad s > 0,\\ \varphi \left( \frac{xs}{\mu } \right)&=\varphi (e). \end{aligned} \end{aligned}$$
(4)

In this paper we propose a new class of directions starting from a simple equivalence. Using \(v>0\), we get:

$$\begin{aligned} xs=\mu e \Leftrightarrow v^2=e \Leftrightarrow v=e \Leftrightarrow v^2=v. \end{aligned}$$

Then, system (2) can be written in the following form:

$$\begin{aligned} \begin{aligned} Ax&= b,\qquad x> 0, \\ A^Ty + s&= c,\qquad s > 0,\\ \varphi \left( \frac{xs}{\mu }\right)&=\varphi \left( \sqrt{\frac{xs}{\mu }}\right) . \end{aligned} \end{aligned}$$
(5)

If we consider the notation

$$\begin{aligned} f(x,y,s):= & {} \left[ \begin{array}{c} Ax-b \\ A^Ty+s-c \\ \varphi \left( \frac{xs}{\mu }\right) - \varphi \left( \sqrt{\frac{xs}{\mu }}\right) \end{array} \right] , \end{aligned}$$
(6)

then system (5) can be written in the form \(f(x,y,s)=0\). Applying Newton’s method to this system we get

$$\begin{aligned} J_f(x,y,s) \left[ \begin{array}{c} \varDelta x \\ \varDelta y \\ \varDelta s \end{array} \right] = - f(x,y,s), \end{aligned}$$

where \(J_f(x,y,s)\) denotes the Jacobian matrix of f. After some calculations we obtain Newton’s system:

$$\begin{aligned} \begin{aligned} A\varDelta x&= 0,\\ A^T\varDelta y+\varDelta s&= 0,\\ \frac{1}{\mu } \left( s\varDelta x+x\varDelta s\right)&= \frac{-\varphi \left( \frac{xs}{\mu }\right) +\varphi \left( \sqrt{\frac{xs}{\mu }}\right) }{\varphi ' \left( \frac{xs}{\mu }\right) -\frac{1}{2\sqrt{\frac{xs}{\mu }}}\varphi ' \left( \sqrt{\frac{xs}{\mu }}\right) }. \end{aligned} \end{aligned}$$
(7)

We introduce the following notations

$$\begin{aligned} d_x=\frac{v \varDelta x}{x} \end{aligned}$$

and

$$\begin{aligned} d_s=\frac{v \varDelta s}{s}, \end{aligned}$$

hence we obtain

$$\begin{aligned} \mu v(d_x+d_s)=s\varDelta x + x\varDelta s \end{aligned}$$
(8)

and

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

Using these notations we can give the scaled form of system (7):

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

where

$$\begin{aligned} p_v= & {} \frac{2\varphi (v)-2\varphi (v^2)}{2v\varphi ' (v^2)-\varphi ' (v)},\\ \bar{A}= & {} \frac{1}{\mu } A diag \left( \frac{x}{v} \right) . \end{aligned}$$

If we use the function \(\varphi : \left( \frac{1}{2},\infty \right) \rightarrow \mathbb {R}\), \(\varphi (t)=t\), then we have

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

It can be mentioned that the condition \(2t\varphi '(t^2)-\varphi '(t)> 0, \forall t>\kappa ^2\) is satisfied in this case, where \(\kappa =\frac{1}{2}\). Darvay et al [11] considered another equivalent transformation of the system which defines the central path. In system (5) we used the transformation \(\varphi (v^2)=\varphi (e)\). After that, we analysed the case, where \(\varphi (t)=t-\sqrt{t}\). It should be mentioned, that we obtained the same vector \(p_v\) as the one given in (11).

Furthermore, we will consider the case of the function \(\varphi : \left( \frac{1}{\sqrt{2}},\infty \right) \rightarrow \mathbb {R}\), \(\varphi (t)=t^2\), so we obtain

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

Observe that the condition \(2t\varphi '(t^2)-\varphi '(t)> 0, \forall t>\kappa ^2\) is satisfied in this case, where \(\kappa =\frac{1}{\sqrt{2}}\).

We use a proximity measure to the central path

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

Let \(q_v=d_x-d_s\). Then, \(d_x^Td_s=0 \Rightarrow \Vert p_v\Vert =\Vert q_v\Vert \).

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

which implies

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

Observe that if we use the approach based on kernel functions, the third equation of (3) is equivalent to

$$\begin{aligned} d_x+d_s=-\nabla \varPsi (v), \end{aligned}$$

where \(\varPsi \) is the function defined in Sect. 3. Therefore, in case of applying the transformation \(\varphi (v^2)=\varphi (v)\), the appropriate kernel function can be defined as:

$$\begin{aligned} \psi (t)= \int _{1}^{t} \frac{2\varphi (\eta ^2)-2\varphi (\eta )}{2\eta \varphi ' (\eta ^2)-\varphi ' (\eta )} d\eta . \end{aligned}$$

In the case of the function \(\varphi (t)=t^2\) we obtain the following kernel function:

$$\begin{aligned} \psi (t)=\frac{t^2-1}{4}-\frac{\log (2t^2-1)}{8}. \end{aligned}$$

Note that this kernel function is not a usual one, because it is not defined on the whole interval \((0,\infty )\).

Now we are able to define the algorithm, which is given in Fig. 1.

Fig. 1
figure 1

Primal–dual algorithm

Full size image

In the following section we analyse the complexity of the algorithm.

5 Analysis of the algorithm

Let \(x_+=x+\varDelta x\) and \(s_+=s+\varDelta s \) be the generated point after a full-Newton step. Bellow, we give a condition which guarantees the feasibility of these vectors.

Lemma 1

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

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

which means that the full-Newton step is strictly feasible.

Proof

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

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

From Eqs. (8) and (9), we obtain

$$\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}$$
(14)

Also using (10) and (13) we can write

$$\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}$$
(15)

Moreover, from (12) we obtain

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

On the other hand, \((v^2-e)^2 \ge 0\) implies

$$\begin{aligned} \frac{v^4}{2v^2-e} \ge e, \end{aligned}$$

and for this reason

$$\begin{aligned} v^2+ v p_v \ge e. \end{aligned}$$
(17)

Using these, we may write

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

If \(\left\| (1-\alpha )\frac{ p_v^2}{4}+ \alpha \frac{ q_v^2}{4}\right\| _\infty <1,\) then the inequality \( x_+(\alpha ) s_+(\alpha )> 0\) holds, where \(\Vert \cdot \Vert _\infty \) marks the Chebychev norm (or \(l_\infty \) norm). In this way

$$\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}$$

Hence, for each \(0\le \alpha \le 1\) the inequality \( x_+(\alpha ) s_+(\alpha )> 0\) holds. This 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\) yield \( x_+(1)= x_+> 0\) and \( s_+(1)= s_+> 0\). This means that the full-Newton step is strictly feasible.\(\square \)

In the following lemma we analyse the conditions under which the Newton process is quadratically convergent.

Lemma 2

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

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

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

Proof

We know from Lemma 1 that \( x_+> 0\) and \( s_+> 0\). We introduce the following notation

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

Also we know from (16) that \(v^2+ v p_v = \frac{v^4}{2v^2-e}\), which implies

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

We consider the substitution \(\alpha =1\) in (15) and we obtain

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

Using (12) and (19) we may write

$$\begin{aligned} v_+^2= & {} e + \frac{(v^2-e)^2}{2v^2-e} + \frac{(v-v^3)^2}{4 (2v^2-e)^2} - \frac{q_v^2}{4} \nonumber \\= & {} e + \frac{(v^2-e)^2}{2v^2-e} \left( e+\frac{v^2}{4 (2v^2-e)} \right) - \frac{q_v^2}{4} \nonumber \\= & {} e+\frac{(v^2-e)^2 (9v^2-4e)}{4 (2v^2-e)^2} - \frac{q_v^2}{4}. \end{aligned}$$
(21)

From (12) and (21) we obtain

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

We have \(\frac{9v^2-4e}{v^2} < 9 e\), for all \(v>\frac{1}{\sqrt{2}}e\). Thus,

$$\begin{aligned} \left\| e-v_+^2 \right\| \le \left\| \frac{q_v^2}{4}\right\| +\left\| \frac{9v^2-4e}{v^2}\cdot \frac{p_v^2}{4} \right\| < \frac{\Vert q_v\Vert ^2}{4}+9\frac{\Vert p_v\Vert ^2}{4}=10 \delta ^2. \end{aligned}$$
(23)

Beside these, we know that \(\frac{p_v^2}{4} >0 \) and we also have from (17) that \(v^2+vp_v \ge e \), so these imply that

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

Therefore,

$$\begin{aligned} \min (v_+) \ge \sqrt{1-\delta ^2}. \end{aligned}$$
(24)

Using \(\delta > \frac{1}{\sqrt{2}}\) we have \(\sqrt{1-\delta ^2} > \frac{1}{\sqrt{2}}\). From (24) and this we have \(v_+ > \frac{1}{\sqrt{2}}\), which plays a key role, because during the whole process of the algorithm we have to ensure that the variance vector v satisfies this condition. We have

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

Let us consider the function \(g(t)=\frac{t}{2t^2-1}\) for all \(t>\frac{1}{\sqrt{2}}\). Because \(g'(t)<0\) we obtain that the function g is a decreasing one for all \(t>\frac{1}{\sqrt{2}}\). Using this and (24) and (23) we get

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

This proves the lemma.\(\square \)

The next lemma shows how the full-Newton step effects the duality gap.

Lemma 3

Let \(\delta =\delta ( x, s;\mu )\). Then,

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

Proof

We know from (16) that

$$\begin{aligned} v^2+vp_v= & {} \frac{v^4}{2v^2-e}=e+\frac{(v^2-e)^2}{2v^2-e} \nonumber \\= & {} e+\frac{4(2v^2-e)}{v^2} \cdot \frac{v^2(e-v^2)^2}{4(2v^2-e)^2} \nonumber \\= & {} e+\left( 8-\frac{4e}{v^2}\right) \cdot \frac{p_v^2}{4} \le e+8\frac{p_v^2}{4}. \end{aligned}$$
(25)

This implies

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

which proves the lemma.\(\square \)

The fourth lemma shows that the algorithm is well defined.

Lemma 4

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

$$\begin{aligned} \delta (v_\sharp )=\delta ( x_+, s_+; \mu _+) < \frac{\sqrt{1-\delta ^2}}{2\sqrt{1-\theta }(1-2\delta ^2+\theta )}(\theta \sqrt{n}+10\delta ^2). \end{aligned}$$

If \(\delta < \frac{1}{10}\) and \(\theta = \frac{1}{12 \sqrt{n}}\), then \(\delta ( x_+, s_+; \mu _+) < \frac{1}{10}\).

Proof

Using Lemma 2 we have \(v_+>\frac{1}{\sqrt{2}}e\). From \(v_\sharp =\sqrt{\frac{x_+s_+}{\mu _+}}\) it follows that \(v_\sharp =\frac{1}{\sqrt{1-\theta }} v_+\), \(v_\sharp ^2=\frac{1}{1-\theta } v_+^2\) and \(v_\sharp > \frac{1}{\sqrt{2}}e\). Besides these, from the definition of the \(\delta \) we may write

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

Then,

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

and

$$\begin{aligned} v_\sharp -v_\sharp ^3= & {} v_\sharp (e-v_\sharp ^2)=\frac{1}{\sqrt{1-\theta }} v_+ \left( e-\frac{1}{1-\theta } v_+^2 \right) \nonumber \\= & {} \frac{v_+}{(1-\theta )\sqrt{1-\theta }}\left[ (1-\theta )e-v_+^2 \right] . \end{aligned}$$
(28)

From (27) and (28) it follows that

$$\begin{aligned} \left\| \frac{v_\sharp -v_\sharp ^3}{2v_\sharp ^2-e} \right\|= & {} \frac{v_+}{(1-\theta )\sqrt{1-\theta }}\left[ (1-\theta )e-v_+^2 \right] \frac{1-\theta }{2v_+^2-(1-\theta )e} \nonumber \\= & {} \frac{1}{\sqrt{1-\theta }} \cdot \frac{v_+}{2v_+^2-(1-\theta )e} \cdot \left[ (1-\theta )e - v_+^2 \right] . \end{aligned}$$
(29)

Besides, \(\frac{t}{2t^2-(1-\theta )}\) is a decreasing function of t, for all \(t > \frac{1}{\sqrt{2}}\). Using this and (29) it follows that

$$\begin{aligned} \delta (x_+, s_+;\mu _+)=\frac{1}{2} \left\| \frac{v_\sharp -v_\sharp ^3}{2v_\sharp ^2-e} \right\| \le \frac{\sqrt{1-\delta ^2}}{2\sqrt{1-\theta }(1-2\delta ^2+\theta )} \Vert (1-\theta )e-v_+^2\Vert . \end{aligned}$$
(30)

Using (23) we may write

$$\begin{aligned} \Vert (1-\theta )e-v_+^2\Vert \le \Vert -\theta e\Vert + \Vert e-v_+^2\Vert < \theta \sqrt{n} +10 \delta ^2. \end{aligned}$$
(31)

From (30) and (31) it follows that

$$\begin{aligned} \delta (v_\sharp )=\delta ( x_+, s_+; \mu _+) < \frac{\sqrt{1-\delta ^2}}{2\sqrt{1-\theta }(1-2\delta ^2+\theta )}(\theta \sqrt{n}+10\delta ^2), \end{aligned}$$

which proves the first part of the lemma. For the proof of the second part suppose that \(\delta < \frac{1}{10}\) and \(\theta = \frac{1}{12\sqrt{n}}\). Using these and the inequalities \(\sqrt{1-\delta ^2}<1\) and \(\theta > 0\) we obtain \(\delta (v_\sharp )< \frac{\theta \sqrt{n}+10\delta ^2}{2\sqrt{1-\theta }(1-2\delta ^2)} < \frac{1}{2\sqrt{1-\theta }} \frac{50}{49}\left( \frac{1}{12}+\frac{1}{10} \right) \). Using \(n \ge 1\) we get \(2\sqrt{1-\theta } \ge \sqrt{\frac{11}{3}}\). Taking all these inequalities into consideration we conclude \(\delta ( x_+, s_+; \mu _+)< \frac{5 \sqrt{33}}{294} < \frac{1}{10}\). This proves the lemma.\(\square \)

The next lemma gives a bound on the number of iterations.

Lemma 5

We suppose that \((x^0,s^0)\) are strictly feasible, \(\mu ^0=\frac{(x^0)^T s^0}{n}\) and \(\delta (x^0, s^0;\mu ^0) < \frac{1}{\sqrt{2}}\). Let \(x^k\) and \(s^k\) be the vectors obtained after k iterations. Then, for every

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

we get \((x^k)^Ts^k\le \epsilon \).

Proof

From Lemma 3 and from \(\delta (x, s; \mu ) < \frac{1}{\sqrt{2}}\) we get

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

In this way \(( x^k)^T s^k\le \epsilon \) stands if

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

We take logarithms, so we may write

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

We know that \(-\log (1-\theta )\ge \theta \), so the inequality stands only if

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

This proves the lemma.\(\square \)

Theorem 1

We assume that \(x^0=s^0=e\). Using the default values for \(\theta \) and \(\tau \) we obtain that the algorithm given in Fig. 1 demands no more then

$$\begin{aligned} O\left( \frac{1}{\theta }log\frac{n+4}{\epsilon }\right) \end{aligned}$$

interior-point iterations.

Now we give a consequence of the previous lemmas when \(\tau = \frac{1}{10}\) and \(\theta = \frac{1}{12 \sqrt{n}}\). Note that (x, y, s) is an \(\epsilon \)-solution of the primal–dual pair if the following inequality holds

$$\begin{aligned} max(x^T s,\Vert b-Ax\Vert ,\Vert c-A^Ty-s\Vert ) \le \epsilon . \end{aligned}$$

Corollary 1

Let \(x^0=s^0=e\). If \(\tau = \frac{1}{10}\) and \(\theta = \frac{1}{12 \sqrt{n}}\), then after at most

$$\begin{aligned} \left\lceil 12 \sqrt{n}log\frac{n+4}{\epsilon } \right\rceil \end{aligned}$$

interior-point iterations the algorithm finds an \(\epsilon \)-solution for (P) and (D). The resulting vectors satisfy \(x^Ts\le \epsilon \).

6 Numerical results

In order to compare the efficiency of the algorithm to other methods, we implemented the algorithm given in Fig. 1 in the \(C++\) programming language. We analysed the algorithm for five different search directions, including ours. Let SD1 be the method working with the search direction introduced by us in this paper. Furthermore, we denote by SD2 the algorithm which uses the classical search direction proposed by Roos, Terlaky and Vial [33]. Let SD3 and SD4 be the algorithms that are based on the search directions given in [10] and [11], respectively. Moreover, we denote by SD5 the method which works with the trigonometric search direction introduced by Peyghami and Hafshejani [29].

In each step we reduce the value of the barrier update parameter \(\mu \) by the factor \(1-\theta \). We considered the following different values for the update parameter \(\theta \): 0.1, 0.2, 0.3, 0.4. We set the value for the accuracy parameter \(\epsilon \) to \(10^{-4}\).

We analysed two small-sized feasible problems where the starting points were already given. After that, we solved the problem AFIRO from the Netlib test collection [12]. Hereafter, we present the results obtained by solving these three problems.

Table 1 Number of iterations for Problem 1
Full size table

6.1 Problem 1

Let us consider the problems proposed in this paper, where

$$\begin{aligned} A=\left[ \begin{array}{ccccccc} -8 &{} \; -2 &{} \; -8 &{} \quad 6 &{} \; -3 &{} \; -1 &{} \quad 7 \\ -5 &{} \quad 10 &{} \; -2 &{} \; -9 &{} \quad 4 &{} \; -4 &{} \; -5 \\ -8 &{} \quad 1 &{} \; -1 &{} \; -3 &{} \; -8 &{} \; -6 &{} \; -6 \\ 9 &{} \quad 2 &{} \quad 7 &{} \quad 1 &{} \quad 5 &{} \; -4 &{} \; -7 \\ -4 &{} \; -3 &{} \; -4 &{} \; -2 &{} \quad 6 &{} \; -3 &{} \; -1 \\ \end{array}\right] , \; b=\left[ \begin{array}{c} -78 \\ 5\\ -137 \\ 121\\ -54 \end{array}\right] , \; c=\left[ \begin{array}{c} -22 \\ -15 \\ 0 \\ 57 \\ -64 \\ -4 \\ 22 \end{array}\right] . \end{aligned}$$

We consider the following starting points: \(x^0= \left[ 9,\; 9,\; 1,\; 5,\; 5,\; 2,\; 1 \right] ^T\),

\(y^0=\left[ 5,\; -3,\; 4,\; 2,\; -4 \right] ^T\) and \(s^0= \left[ 1,\; 5,\; 8,\; 2,\; 9,\; 9,\; 6 \right] ^T.\)

In Table 1 we summarize the obtained number of iterations for the specified search directions and update parameters.

6.2 Problem 2

Let us consider:

$$\begin{aligned} A=\left[ \begin{array}{ccccccc} 3 &{} \quad 4 &{} \quad 8 &{} \quad 0 &{} \quad -7 &{} \quad -4 &{} \quad -4 \\ -3 &{} \quad 0 &{} \quad 9 &{} \quad 0 &{} \quad 5 &{} \quad 5 &{} \quad 3 \\ -9 &{} \quad 5 &{} \quad -5 &{} \quad 8 &{} \quad -9 &{} \quad 0 &{} \quad 8 \\ -3 &{} \quad 2 &{} \quad -1 &{} \quad -1 &{} \quad -5 &{} \quad 9 &{} \quad -8 \\ 9 &{} \quad 10 &{} \quad 10 &{} \quad 9 &{} \quad 3 &{} \quad 8 &{} \quad 9 \\ -1 &{} \quad 3 &{} \quad -7 &{} \quad -7 &{} \quad -4 &{} \quad -8 &{} \quad -2 \end{array}\right] , \; b=\left[ \begin{array}{c} 23 \\ 119 \\ -23 \\ 56 \\ 380 \\ -170 \end{array}\right] , \; c=\left[ \begin{array}{c} 53 \\ 169 \\ 90 \\ 201 \\ -141 \\ 21 \\ 124 \end{array}\right] . \end{aligned}$$

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

In Table 2 we present the obtained number of iterations that refer to Problem 2.

Table 2 Number of iterations for Problem 2
Full size table

6.3 Problem AFIRO

In this case for the choice of the initial points we used Mehrotra’s heuristic method [26].

Table 3 contains the obtained results for the different cases.

Table 3 Number of iterations for Problem AFIRO
Full size table

We conclude that in some cases the proposed method solves the linear optimization problem more efficiently than the one using other search directions presented in the literature.

7 Conclusion

We proposed an IPM for LO based on a new method for defining search directions. Using the variance vector v we found out that the centering equation is equivalent to \(v^2=v\) and we applied componentwise the function \(\varphi (t)=t^2\) to both sides of this equation. After that, we used Newton’s method in order to get the search directions. We showed that the obtained algorithm solves the problem in polynomial time and has the same complexity as the best known IPMs for LO. Moreover, we presented some numerical results that prove the efficiency of the proposed method.