Return to Article Details Improving complexity of Karmarkar's approach for linear programming

IMPROVING COMPLEXITY OF KARMARKAR’S APPROACH FOR LINEAR PROGRAMMING

DJAMEL BENTERKI $^{*}$ MOUSAAB BOUAFIA $^{§}$

November 2, 2014.
Published online: January 23, 2015.

$^{*}$ 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.

$^{§}$ 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.

In this paper, we are interested in the performance of Karmarkar’s projective algorithm for linear programming. Based on the work of Schrijver, we offer a new displacement step better than Schrijver’s one which led to a moderate improvement in the behavior of the algorithm shift. We show later that the algorithm converges after $\frac{n}{1 - \log (2) + (\frac{n r^{2}}{10})} \log (\frac{c^{t} e_{n}}{ε})$ iterations.

This purpose is confirmed by numerical experiments showing the efficiency of the obtained algorithm, which are presented in the last of paper.

MSC. 90C05, 65K05

Keywords. Linear programming, interior point method, potential function.

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 (n q \ + n \log n)$ iterations for a displacement step $α_{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 $O (n q)$ for a displacement step $α_{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 (2)} \log (\frac{c^{t} e_{n}}{ε})$ iterations for a displacement step $α_{S} = \frac{1}{1 + n r}$ .

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:

(P K) {\begin{cases} min c^{t} x = z^{*} = 0 \\ A x = 0 \\ x \in S_{n} = {x \in R_{+}^{n}, e_{n}^{t} x = 1}, \end{cases}

where $c \in R^{n}, A \in R^{m \times n}$ is a matrix of full rank $(rank (A) = m < n)$ and $e_{n} = {(1, 1, . . . ., 1)}^{t} \in 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:

\begin{aligned} T_{k} : S_{n} ⟶ S_{n} \\ x \mapsto y = & T_{k} (x) = \frac{D_{k}^{- 1} x}{e_{n}^{t} D_{k}^{- 1} x} \end{aligned}

such that $D_{k} = diag (x^{k})$ 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:

x = T_{k}^{- 1} (y) = \frac{D_{k} y}{e_{n}^{t} D_{k} y} .

The transformed problem of $(P K)$ by the transformation $T_{k}$ is the linear programming problem:

(P K T) {\begin{cases} min {(D_{k} c)}^{t} y \\ A D_{k} y = 0 \\ y \in S_{n} = {y \in R_{+}^{n} : e_{n}^{t} y = 1}, \end{cases}

which can be written as:

(P K T) {\begin{cases} min {(D_{k} c)}^{t} y \\ [\begin{array}{c} A D_{k} \\ e_{n}^{t} \end{array}] y = [\begin{array}{c} 0 \\ 1 \end{array}] \\ y \geq 0. \end{cases}

The transformed problem $(P K T)$ 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} (x^{k}) = \frac{e_{n}}{n} .$

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

The problem $(P K T)$ becomes:

{(P K T)}_{r} {\begin{cases} min {(D_{k} c)}^{t} y \\ [\begin{array}{c} A D_{k} \\ e_{n}^{t} \end{array}] y = [\begin{array}{c} 0 \\ 1 \end{array}] \\ {‖ y - \frac{e_{n}}{n} ‖}^{2} \leq {(α r)}^{2} . \end{cases}

Using the optimality conditions, the optimal solution of the problem ${(P K T)}_{r}$ is given by:

y = \frac{e_{n}}{n} - α r d_{k},

where $d_{k}$ $= \frac{P_{k}}{‖ P_{k} ‖}$ , such that $P_{k}$ is the projection of the vector $D_{k} c$ on the kernel of the constraint matrix $A D_{k} .$

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

Remark 1

Initially, Karmarkar has taken the displacement step $α$ between $0$ and $1$ . This ensures that all iterates remain inside the simplex and show the polynomial convergence of the algorithm. In numerical terms, it appears that more the displacement step $α$ is large more the algorithm converges faster. For this reason, several researchers suggest to use variable displacement step through the line search method. Unfortunately, the procedure is expensive and there are no convergence results. Our aim is to improve the theoretical results given by Karmarkar, by using short step that depend on the size of the considered problem. This idea is inspired by the work of R. Naseri & A. Valinejad [ 5 ] and Schrijver [ 7 ] . For the moment, we give the polynomial convergence theorem of Karmarkar’s algorithm.â–¡

2.2 Convergence of Karmarkar’s algorithm

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

f (x) = n \log c^{t} x - \sum_{i = 1}^{n} \log x_{i}

defined on the set

D_{x} = {x \in R^{n} : x > 0, A x = 0, e_{n}^{t} x = 1} .

Theorem 2 Karmarkar’s convergence theorem

[ 1 ]

If $0 < α_{K} \leq \frac{1}{4}$ , then starting from $x^{0} = \frac{e_{n}}{n},$ after $O (n q +$ $n \log n)$ iterations, the algorithm finds a feasible point $x^{*}$ such that:

(1) $c^{t} x^{*} = 0$

(2) $\frac{c^{t} x^{*}}{c^{t} x^{0}} \leq 2^{- q},$ where $q$ is a fixed precision.

Remark 3

In his work, Padberg [ 2 ] was able to improve the convergence of the classical algorithm of Karmarkar by replacing Karmarkar’s potential function as follows:

h (x) = \frac{c^{t} x}{(\prod_{i = 1}^{n} x_{i})^{\frac{1}{n}}}

defined on the set

D_{x} = {x \in R^{n} : x > 0, A x = 0, e_{n}^{t} x = 1}

and showed that for a displacement step $α_{P} = \frac{1}{2}$ , the algorithm converges after $O (n q)$ iterations. In the same direction regardless of Padberg, Schrijver [ 7 ] has shown that for a displacement step $α_{S} = \frac{1}{1 + n r},$ the algorithm converges after $\frac{n}{1 - \log 2} \log \frac{c^{t} e_{n}}{ε}$ iterations.â–¡

In the next section, we propose a new value of displacement step $α_{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 $α_{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.

Lemma 4

[ 6 ] Let $ψ_{n}$ be a function defined by:

ψ_{n} : {] - 1, + \infty [}^{n} \to R_{+}

x \mapsto ψ_{n} (x) = e_{n}^{t} x - \sum_{i = 1}^{n} \log (1 + x_{i})

then for $‖ x ‖ < 1$ we have:

ψ_{1} (- ‖ x ‖) \geq ψ_{n} (- x) .

Lemma 5

[ 6 ] If $x \in D_{x}$ then:

c^{t} x \leq \exp (\frac{f (x)}{n})

where $f$ is the Karmarkar’s potential function.

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

Lemma 6

[ 2 ] Let $x^{k}$ be the $k - t h$ iterate of Karmarkar’s algorithm, then:

\frac{c^{t} x^{k}}{c^{t} x^{0}} \leq {(\exp [f (x^{k}) - f (x^{0})])}^{\frac{1}{n}},

where

x^{0} = \frac{e_{n}}{n} .

Lemma 7

[ 6 ] At each iteration $k,$ the potential function decreases from the following quantity:

f (x^{k + 1}) - f (x^{k}) = - Δ,

such that:

x^{k + 1} = T_{k}^{- 1} (y^{k}) and Δ = n \log \frac{c^{t} D_{k} e_{n}}{c^{t} D_{k} y^{k}} + \sum_{i = 1}^{n} \log y_{i}^{k}

Lemma 8

[ 6 ] If $0 < α < \frac{1}{n r}$ then:

Δ \geq α n^{2} r^{2} + n ψ_{1} (- α \frac{r}{R}) - ψ_{1} (- α n r),

where $R = \sqrt{\frac{n - 1}{n}}$

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

Lemma 9

For $α_{B} = \frac{5 + n r^{2}}{5 + (5 + n r^{2}) n r}$ and $α_{S} = \frac{1}{1 + n r},$ we have:

a) $α_{B} > α_{S},$

b) $ψ_{1} (- α_{B} n r^{2}) > \frac{1}{5} α_{B} n^{2} r^{4},$

c) $Δ \geq ψ_{1} (\frac{1}{5} n r (5 + n r^{2})) .$

Proof â–¼

a) Since $5 + n r^{2} > 5,$ then

(5 + n r^{2}) (1 + n r) > 5 + (5 + n r^{2}) n r \Leftrightarrow \frac{(5 + n r^{2})}{5 + (5 + n r^{2}) n r} > \frac{1}{1 + n r}

which gives:

α_{B} > α_{S} .

b) By definition, we have:

\begin{aligned} ψ_{1} (- α_{B} n r^{2}) & = - α_{B} n r^{2} - \log (1 - α_{B} n r^{2}), \end{aligned}

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

\begin{aligned} ψ_{1} (- α_{B} n r^{2}) & > - α_{B} n r^{2} + α_{B} n r^{2} + \frac{α_{B}^{2} n^{2} r^{4}}{2} \\ > \frac{α_{B} n^{2} r^{4}}{2} α_{S} > \frac{1}{5} α_{B} n^{2} r^{4} \end{aligned}

because:

α_{S} = \frac{1}{1 + n r} \geq \frac{1}{1 + \sqrt{2}} > \frac{2}{5}

so:

ψ_{1} (- α_{B} n r^{2}) > \frac{1}{5} α_{B} n^{2} r^{4} .

c) By Lemma 8 and since $\frac{1}{R} = n r$ we have:

Δ \geq α n^{2} r^{2} + n ψ_{1} (- α n r^{2}) - ψ_{1} (- α n r), with 0 < α < \frac{1}{n r},

for $α = α_{B} = \frac{5 + n r^{2}}{5 + (5 + n r^{2}) n r}$ and by b) we get:

\begin{aligned} Δ & > α_{B} n^{2} r^{2} + n (\frac{1}{5} α_{B} n^{2} r^{4}) - ψ_{1} (- α_{B} n r) \\ > α_{B} n^{2} r^{2} + \frac{1}{5} n r^{2} (α_{B} n^{2} r^{2}) + α_{B} n r + \log (1 - α_{B} n r) \\ > (n^{2} r^{2} + \frac{1}{5} n r^{2} (n^{2} r^{2}) + n r) α_{B} + \log (1 - α_{B} n r) \\ > \frac{1}{5} (5 n^{2} r^{2} + n r^{2} (n^{2} r^{2}) + 5 n r) \frac{5 + n r^{2}}{5 + (5 + n r^{2}) n r} + \log (1 - \frac{5 + n r^{2}}{5 + (5 + n r^{2}) n r} n r) \\ > \frac{1}{5} n r (5 n r + n r^{2} (n r) + 5) \frac{5 + n r^{2}}{5 + (5 + n r^{2}) n r} + \log (1 - \frac{5 + n r^{2}}{5 + (5 + n r^{2}) n r} n r) \\ > \frac{1}{5} n r ((5 + n r^{2}) (n r) + 5) \frac{5 + n r^{2}}{5 + (5 + n r^{2}) n r} + \log (\frac{5}{5 + (5 + n r^{2}) n r}) \\ > \frac{1}{5} n r (5 + n r^{2}) + \log (\frac{5}{5 + (5 + n r^{2}) n r}) \\ > \frac{1}{5} n r (5 + n r^{2}) + \log (\frac{1}{1 + (5 + n r^{2}) \frac{n r}{5}}) \\ > \frac{1}{5} n r (5 + n r^{2}) - \log (1 + \frac{1}{5} n r (5 + n r^{2})) = ψ_{1} (\frac{1}{5} n r (5 + n r^{2})) \end{aligned}

Hence:

Δ > ψ_{1} (\frac{1}{5} n r (5 + n r^{2})) .

Remark 10

It is easily shown that $ψ_{1}$ is increasing on $[0, + \infty [$ and in particular:

ψ_{1} (\frac{1}{5} n r (5 + n r^{2})) \geq ψ_{1} (n r) \geq ψ_{1} (1) = 1 - \log (2) .

3.1 Improved displacement step

Recall that for $α_{S} = \frac{1}{1 + n r}$ , Schrijver [ 7 ] showed that the algorithm converges after $\frac{n}{1 - \log (2)} \log (\frac{c^{t} e_{n}}{ε})$ iterations.

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

Theorem 11

α_{B} = \frac{5 + n r^{2}}{5 + (5 + n r^{2}) n r},

then Karmarkar’s algorithm converges after

\frac{n}{1 - \log (2) + (\frac{n r^{2}}{10})} \log (\frac{c^{t} e_{n}}{ε})

iterations.

Proof â–¼

By Lemma 9 c) we have:

Δ > ψ_{1} (\frac{1}{5} n r (5 + n r^{2})) = ψ_{1} (n r + \frac{n r}{5} n r^{2}) > ψ_{1} (1 + \frac{1}{5} n r^{2}),

such as $n r > 1$ and $ψ_{1}$ is increasing, then

\begin{matrix} (3.1) & Δ > ψ_{1} (1 + \frac{1}{5} n r^{2}), \end{matrix}

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

ψ_{1} (1 + \frac{1}{5} n r^{2}) - ψ_{1} (1) > \frac{n r^{2}}{10} .

So from (3.1), we get:

\begin{matrix} (3.2) & Δ > ψ_{1} (1) + \frac{n r^{2}}{10} \end{matrix}

Also from Lemma 7, we have:

f (x^{k}) - f (x^{k - 1}) = - Δ, \  \  \  \ \forall k \in N^{*},

using (3.2) we get:

f (x^{i}) - f (x^{i - 1}) < - (ψ_{1} (1) + \frac{n r^{2}}{10}),

accordingly:

\sum_{i = 1}^{k} (f (x^{i}) - f (x^{i - 1})) < - \sum_{i = 1}^{k} (ψ_{1} (1) + \frac{n r^{2}}{10}),

which gives:

f (x^{k}) - f (x^{0}) < - k (ψ_{1} (1) + \frac{n r^{2}}{10}), where x^{0} = \frac{e_{n}}{n},

then:

f (x^{k}) < - k (ψ_{1} (1) + \frac{n r^{2}}{10}) + f (x^{0}),

such that:

f (x^{0}) = f (\frac{e_{n}}{n}) = n \log c^{t} \frac{e_{n}}{n} - \sum_{i = 1}^{n} \log \frac{1}{n} = n \log c^{t} e_{n},

so:

\begin{matrix} (3.3) & \frac{f (x^{k})}{n} < \frac{- k (ψ_{1} (1) + \frac{n r^{2}}{10}) + n \log c^{t} e_{n}}{n}, \end{matrix}

by Lemma 5 and (3.3), we have:

c^{t} x^{k} < \exp (\frac{- k (ψ_{1} (1) + \frac{n r^{2}}{10}) + n \log c^{t} e_{n}}{n}) .

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

\exp (\frac{- k (ψ_{1} (1) + \frac{n r^{2}}{10}) + n \log c^{t} e_{n}}{n}) < ε,

which can be done:

\begin{matrix} (3.4) & k > \frac{n}{1 - \log 2 + \frac{n r^{2}}{10}} \log \frac{c^{t} e_{n}}{ε} . \end{matrix}

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

Remark 12

The previous Theorem 11 gives a displacement step $α_{B}$ greater than the displacement step $α_{S}$ of Schrijver which improve the practical behavior of the algorithm and the theoretical performance results, in the sense that the number of iterations given in this theorem is less than the number of iterations given by Schrijver.â–¡

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^{*}$ is unknown) using differently two alternatives, once the displacement step $α_{S}$ of (Schrijver) and again the displacement step $α_{B}$ of (Bouafia & Benterki). The precision $ε$ is taken between $10^{- 4}$ and $10^{- 6} .$

In each case, $k$ denotes the number of iterations required for the optimality.

Example

$(m, n)$

Number of iterations

$α_{S}$ Schrijver

Number of iterations

$α_{B}$ Bouafia & Benterki

$1$

$(3, 4)$

$k = 18$

$k = 17$

$2$

$(3, 5)$

$k = 26$

$k = 25$

$3$

$(4, 7)$

$k = 36$

$k = 35$

$4$

$(5, 9)$

$k = 47$

$k = 46$

$5$

$(5, 11)$

$k = 46$

$6$

$(6, 12)$

$k = 48$

$k = 47$

$7$

$(16, 26)$

$k = 71$

$k = 70$

Table 1 Comparative table

5 Conclusion

This study shows that the new displacement step $α_{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 $α_{B}$ and $α_{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.