\(^{\ast }\)Laboratoire de Mathématiques Fondamentales et Numériques LMFN, Département de Mathématiques, Faculté des Sciences, Université Sétif-1, Algérie, e-mail: dj_benterki@yahoo.fr.

\(^{\S }\)LabCAV, Laboratoire de Contrôle Avancé, Département de Mathématiques, Faculté des Mathématiques et de l’Informatique et des Sciences de la Matière, Université de Guelma, Algérie, e-mail: mousaab84@yahoo.fr.

1 Introduction

Karmarkar’s algorithm for solving linear optimization problems [ 1 ] is the first truly efficient algorithm that solves these problems in polynomial time. The ellipsoid method also works in polynomial time, but it is ineffective in practice. Using a potential function shows that the Karmarkar’s algorithm converges after a number \(O\left( nq\text{\ }+\text{ }n\log n\right) \) iterations for a displacement step \(\alpha _{K}=\frac{1}{4}\). Since then, many researchers are interested in this algorithm in order to more improve its numerical behavior. The two covered basic elements covered are the direction of displacement that dominates the cost computation at each iteration and the displacement step which plays an important role in the speed of convergence. Indeed, by changing the analytical form of the potential function, Padberg [ 2 ] was able to reduce the number of iterations to \({\mathcal O}\left( nq\right) \) for a displacement step \(\alpha _{P}=\frac{1}{2}\). For its part, Schrijver [ 7 ] , keeping the same Karmarkar’s potential function has been shown that the algorithm converges after \(\frac{n}{1-\log \left( 2\right) }\log \big( \frac{c^{t}e_{n}}{\varepsilon }\big) \) iterations for a displacement step \(\alpha _{S}=\frac{1}{1+nr}\).

Our work falls within this framework, where drawing works of Karmarkar [ 1 ] and Shrijver [ 7 ] , we propose a new displacement step to improve the numerical behavior of the algorithm of Karmarkar.

The paper is organized as follows. In Section 2, we present the linear program treated by Karmarkar. Section 3 is the main objective of our work. At first, we propose a new displacement step and then we show that it is better than that of Schrijver. On the other hand, we give an improved polynomial convergence result compared to the Schrijver’s one. In Section 4, we present some computational results. Finally, a conclusion is provided in Section 5.

2 Linear programming problem treated by Karmarkar

In his article [ 1 ] , Karmarkar treats the linear programming problem in the following reduced form:

where \(c\in \mathbb {R} ^{n},\ A\in \mathbb {R} ^{m\times n}\) is a matrix of full rank \(\left( \operatorname {rank}\left( A\right) =m{\lt}n\ \right) \) and \(\ e_{n}=\left( 1,1,....,1\right) ^{t}\in \mathbb {R} ^{n}.\)

The vector \(x^{0}=\frac{e_{n}}{n}\in S_{n},\) is the center of the simplex \(S_{n}\).

2.1 Karmarkar’s Transformation on \(S_{n}\)

The Karmarkar’s transformation is defined at each iteration by:

such that \(D_{k}=\operatorname {diag}\left( x^{k}\right) \) is the \(n\times n\) diagonal matrix with the components of \(x^{k}\) as the diagonal entries.

Similarly, the transformation \(T_{k}\) is invertible and we have:

The transformed problem of \(\left( PK\right) \) by the transformation \(T_{k}\) is the linear programming problem:

which can be written as:

The transformed problem \(\left( PKT\right) \) is placed in the reduced form of Karmarkar, and the transformation \(T_{k}\) can bring the iterated point \(x^{k}\) in the center of the simplex \(S_{n},\) i.e., \(T_{k}\left( x^{k}\right) =\frac{e_{n}}{n}.\)

Before applying the optimality conditions, Karmarkar [ 1 ] relaxes the problem \(\left( PKT\right) \) by replacing the condition \(y\geq 0\ \)by the sphere \(s\left( \frac{e_{n}}{n},\alpha r\right) \), (it is easily shown in [ 2 ] that if\(\ y\in s\left( \frac{e_{n}}{n},\alpha r\right) \) then \(y\geq 0\)) with \(\ r=\frac{1}{\sqrt{n\left( n-1\right) }}\) and \(0{\lt}\alpha {\lt}1\).

The problem \(\left( PKT\right) \) becomes:

Using the optimality conditions, the optimal solution of the problem \(\left( PKT\right) _{r}\) is given by:

where \(d_{k}\) \(=\frac{P_{k}}{\left\Vert P_{k}\right\Vert }\), such that \(P_{k} \) is the projection of the vector \(D_{k}c\) on the kernel of the constraint matrix \(AD_{k}.\)

Returning by the inverse transform \(T_{k}^{-1},\) a feasible solution \(x^{k+1} \) is obtained of the original problem \(\left( PK\right) \) such that \(x^{k+1}=T_{k}^{-1}\left( y^{k}\right) =\frac{D_{k}y^{k}}{e_{n}^{t}D_{k}y^{k}}.\)

2.2 Convergence of Karmarkar’s algorithm

To study the polynomial convergence of the algorithm, Karmarkar used (in case \(z^{\ast }=0\)) the following potential function:

defined on the set

In the next section, we propose a new value of displacement step \(\alpha _{B} \) better than Schrijver’s one, whose aim is to improve further the speed of convergence of Karmarkar’s algorithm.

3 Improving convergence of Karmarkar’s algorithm

In this section, we propose a new displacement step \(\alpha _{B}\) better than the one which was introduced by Schrijver, in order to reduce the number of iterations and accelerate the convergence of Karmarkar’s algorithm and then, we give the corresponding results of the algorithm’s complexity. Before that, we present some lemmas below, in order to help the reader to understand the results that we have established.

More Generally, Keraghel [ 2 ] showed the following Lemma:

Based on the previous lemmas, we present the following results.

a) \(\alpha _{B}{\gt}\alpha _{S},\)

b) \(\psi _{1}\left( -\alpha _{B}nr^{2}\right) {\gt}\frac{1}{5}\alpha _{B}n^{2}r^{4},\)

c) \(\Delta \geq \psi _{1}\left( \frac{1}{5}nr\left( 5+nr^{2}\right) \right) .\)

a) Since \(5+nr^{2}{\gt}5,\) then

which gives:

b) By definition, we have:

Since \(\log (1-x){\lt}-x-\frac{x^{2}}{2}\) for \(0{\lt}x{\lt}1\) then:

because:

so:

c) By Lemma 8 and since \(\frac{1}{R}=nr\) we have:

for \(\alpha =\alpha _{B}=\frac{5+nr^{2}}{5+(5+nr^{2})nr}\) and by b) we get:

Hence:

3.1 Improved displacement step

Recall that for \(\alpha _{S}=\frac{1}{1+nr}\), Schrijver [ 7 ] showed that the algorithm converges after \(\frac{n}{1-\log \left( 2\right) }\log \big( \frac{c^{t}e_{n}}{\varepsilon }\big) \) iterations.

In this section, based on the previous Lemmas, we show in the following theorem that the new displacement step \(\alpha _{B}\) reduces the number of iterations required for the convergence of Karmarkar’s algorithm.

By Lemma 9 c) we have:

such as \(nr{\gt}1\) and \(\psi _{1}\) is increasing, then

and since \(\log (1+x)\leq x,\) we have:

So from (3.1), we get:

Also from Lemma 7, we have:

using (3.2) we get:

accordingly:

which gives:

then:

such that:

so:

by Lemma 5 and (3.3), we have:

Recall that the algorithm converges when \(c^{t}x^{k}\) is less than \(\varepsilon \) (\(\varepsilon {\gt}0\) small enough). So, it returns to search \(k\) which satisfies:

which can be done:

Finally \(c^{t}x^{k}\leq \varepsilon \) when \(k\) satisfies the inequality (3.4), hence the result.

4 Numerical experiments

In this part, we present a comparative tests on different numerical examples of linear programming problem taken from the literature [ 3 ] . We tested the Ye-Lustig’s approach of Karmarkar’s algorithm (case \(z^{\ast }\) is unknown) using differently two alternatives, once the displacement step \(\alpha _{S}\) of (Schrijver) and again the displacement step \(\alpha _{B}\) of (Bouafia & Benterki). The precision \(\varepsilon \) is taken between \(10^{-4} \) and \(10^{-6}.\)

In each case, \(k\) denotes the number of iterations required for the optimality.

5 Conclusion

This study shows that the new displacement step \(\alpha _{B}\) has introduced an improvement in the polynomial convergence results, and a small reduction in the number of iterations.

Note that when the dimension of the problem becomes important, the displacement step \(\alpha _{B}\) and \(\alpha _{S}\) converge to \(\frac{1}{2}\). It will probably be interesting to focus much more on the analytical form of the potential function while preserving all of its good properties, in order to obtain a best complexity results.