Karmarkar's algorithm

From Wikipedia, the free encyclopedia

In mathematics, Karmarkar's algorithm is an algorithm for solving linear programming problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method is also polynomial time but proved to be inefficient in practice.

Where $n$ is the number of variables and $L$ is the number of bits of input to the algorithm, Karmarkar's algorithm requires $O (n 3.5 L)$ operations on $O (L)$ digit numbers, as compared to $O (n 6 L)$ such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is $O (n 3.5 L 2 ln L lnln L)$ . (see Big O notation)

Narendra Karmarkar proposed his algorithm in 1984. It falls within the class of interior point methods: the current guess for the solution does not follow the boundary of the feasible set as in the simplex method, but it moves through the interior of the feasible set.

Consider a Linear Programming problem in matrix form:

maximize $c T x$
subject to	$Ax\leq b$

The algorithm determines the next feasible direction toward optimality and scales back by a factor $0\le\gamma\le 1$ .

[edit] The Algorithm

The basic algorithm is

Algorithm Karmarkar
  Input: A, b, c,  $x 0$ , stopping criterion,  $γ$ .
  k ← 0
  do while stopping criterion not satisfied
      $v k$  ← $b - A x k$ 
      $D v$  ←diag
      $h x$  ←
      $h v$  ← $- A h x$ 
     if  then
        return unbounded
     end if
      $α$  ←
      $x k + 1$  ← $x k + α h x$ 
      $k$  ← $k + 1$ 
  end do

"←" is a loose shorthand for "changes to". For instance, "largest ← item" means that the value of largest changes to the value of item.
"return" terminates the algorithm and outputs the value that follows.

[edit] Example

Example solution

Consider the linear program

maximize		$x 1$	+	$x 2$
subject to		$2 p x 1$	+	$x 2$	$\leq$ $p 2 + 1$ , $p=0.0, 0.1, 0.2,\ldots, 0.9, 1.0$

That is, there are 2 variables $x 1, x 2$ and 11 constraints associated with varying values of $p$ . This figure shows each iteration of the algorithm as red circle points. The constraints are shown as blue lines.

[edit] References

Ilan Adler, Mauricio G.C. and Geraldo Veiga (1989). "An Implementation of Karmarkar's Algorithm for Linear Programming". Mathematical Programming, Vol 44, p. 297–335.
Narendra Karmarkar (1984). "A New Polynomial Time Algorithm for Linear Programming", Combinatorica, Vol 4, nr. 4, p. 373–395.

Retrieved from "http://en.wikipedia.org../../../k/a/r/Karmarkar%27s_algorithm.html"

Category: Optimization algorithms

Karmarkar's algorithm

From Wikipedia, the free encyclopedia

[edit] The Algorithm

[edit] Example

[edit] References

Views

Navigation

Search