Karmarkar's algorithm
Encyclopedia
Karmarkar's algorithm is an algorithm
introduced by Narendra Karmarkar
in 1984 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
is the number of variables and 
is the number of bits of input to the algorithm, Karmarkar's algorithm requires 
operations on 
digit numbers, as compared to 
such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is thus
using FFT-based multiplication (see Big O notation
).
Karmarkar's algorithm falls within the class of interior point method
s: 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 region, improving the approximation of the optimal solution by a definite fraction with every iteration, and converging to an optimal solution with rational data.
problem in matrix form:
The algorithm determines the next feasible direction toward optimality and scales back by a factor 0 < γ ≤ 1.
Karmarkar's algorithm is rather complicated. A simplified version, called the affine-scaling method, proposed and analyzed by others, can be described succinctly as follows. Note that the affine-scaling algorithm, while efficient in practice, is not a polynomial time algorithm.
Input: A, b, c,
, stopping criterion, 
.
do while stopping criterion not satisfied
if
then
return unbounded
end if
end do
That is, there are 2 variables
and 11 constraints associated with varying values of 
. This figure shows each iteration of the algorithm as red circle points. The constraints are shown as blue lines.
and they realized that his invention could be of practical importance. In April 1985, AT&T promptly applied for a patent on Karmarkar's algorithm and that became more fuel for the ongoing controversy over the issue of software patent
s. This left many mathematicians uneasy, such as Ronald Rivest (himself one of the holders of the patent on the RSA algorithm), who expressed the opinion that research proceeded on the basis that algorithms should be free. Even before the patent was actually granted, it seemed that there was prior art
that might have been applicable. Mathematicians who specialize in numerical analysis
such as Philip Gill and others showed that Karmarkar's algorithm is actually equivalent to a projected Newton barrier method with a logarithmic barrier function
, if the parameters are chosen suitably. Methods referred to by Gill were widely used for nonlinear programming
since the 1960s. In fact, one well-known book first published in 1968 described the technique specifically in the context of linear programming. However, some say Gill's argument is flawed, insofar as the method they describe does not even qualify as an "algorithm", since it requires choices of parameters that don't follow from the internal logic of the method, but rely on external guidance, essentially from Karmarkar's algorithm. Furthermore, Karmarkar's contributions are considered far from obvious in light of all prior work, including Fiacco-McCormick, Gill and others cited by Saltzman.
The patent was eventually granted as : "Methods and apparatus for efficient resource allocation" in May 1988. The patent, however, proved to be of limited commercial value to AT&T. They built up the KORBX system, an 8-processor Alliant
computer incorporating linear programming software using Karmarkar's algorithm, priced at US$8.9 million each, and they only managed to sell two such systems. Opponents of software patents have further alleged that the patents ruined the positive interaction cycles that previously characterized the relationship between researchers in linear programming and industry, and specifically it isolated Karmarkar himself from the network of mathematical researchers in his field.
The patent itself expired in April 2006, and the algorithm is presently in the public domain.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
introduced by Narendra Karmarkar
Narendra Karmarkar
Narendra K. Karmarkar is an Indian mathematician, renowned for developing Karmarkar's algorithm. He is listed as an ISI highly cited researcher.- Biography :...
in 1984 for solving linear programming
Linear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
problems. It was the first reasonably efficient algorithm that solves these problems in polynomial time. The ellipsoid method
Ellipsoid method
In mathematical optimization, the ellipsoid method is an iterative method for minimizing convex functions. When specialized to solving feasible linear optimization problems with rational data, the ellipsoid method is an algorithm, which finds an optimal solution in a finite number of steps.The...
is also polynomial time but proved to be inefficient in practice.
Where
is the number of variables and is the number of bits of input to the algorithm, Karmarkar's algorithm requires operations on digit numbers, as compared to such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is thususing FFT-based multiplication (see Big O notation
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
).
Karmarkar's algorithm falls within the class of interior point method
Interior point method
Interior point methods are a certain class of algorithms to solve linear and nonlinear convex optimization problems.The interior point method was invented by John von Neumann...
s: 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 region, improving the approximation of the optimal solution by a definite fraction with every iteration, and converging to an optimal solution with rational data.
The Algorithm
Consider a Linear ProgrammingLinear programming
Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
problem in matrix form:
| maximize cTx | |
| subject to | Ax ≤ b. |
The algorithm determines the next feasible direction toward optimality and scales back by a factor 0 < γ ≤ 1.
Karmarkar's algorithm is rather complicated. A simplified version, called the affine-scaling method, proposed and analyzed by others, can be described succinctly as follows. Note that the affine-scaling algorithm, while efficient in practice, is not a polynomial time algorithm.
Input: A, b, c,
, stopping criterion, .do while stopping criterion not satisfied
if
thenreturn unbounded
end if
end do
Example
Consider the linear program| maximize |  |
+ |  |
||
| subject to |  |
+ |  |
  ,  |
|
That is, there are 2 variables
and 11 constraints associated with varying values of . This figure shows each iteration of the algorithm as red circle points. The constraints are shown as blue lines.Patent controversy
At the time he invented the algorithm, Narendra Karmarkar was employed by AT&TAT&T
AT&T Inc. is an American multinational telecommunications corporation headquartered in Whitacre Tower, Dallas, Texas, United States. It is the largest provider of mobile telephony and fixed telephony in the United States, and is also a provider of broadband and subscription television services...
and they realized that his invention could be of practical importance. In April 1985, AT&T promptly applied for a patent on Karmarkar's algorithm and that became more fuel for the ongoing controversy over the issue of software patent
Software patent
Software patent does not have a universally accepted definition. One definition suggested by the Foundation for a Free Information Infrastructure is that a software patent is a "patent on any performance of a computer realised by means of a computer program".In 2005, the European Patent Office...
s. This left many mathematicians uneasy, such as Ronald Rivest (himself one of the holders of the patent on the RSA algorithm), who expressed the opinion that research proceeded on the basis that algorithms should be free. Even before the patent was actually granted, it seemed that there was prior art
Prior art
Prior art , in most systems of patent law, constitutes all information that has been made available to the public in any form before a given date that might be relevant to a patent's claims of originality...
that might have been applicable. Mathematicians who specialize in numerical analysis
Numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation for the problems of mathematical analysis ....
such as Philip Gill and others showed that Karmarkar's algorithm is actually equivalent to a projected Newton barrier method with a logarithmic barrier function
Barrier function
In constrained optimization, a field of mathematics, a barrier function is a continuous function whose value on a point increases to infinity as the point approaches the boundary of the feasible region . It is used as a penalizing term for violations of constraints...
, if the parameters are chosen suitably. Methods referred to by Gill were widely used for nonlinear programming
Nonlinear programming
In mathematics, nonlinear programming is the process of solving a system of equalities and inequalities, collectively termed constraints, over a set of unknown real variables, along with an objective function to be maximized or minimized, where some of the constraints or the objective function are...
since the 1960s. In fact, one well-known book first published in 1968 described the technique specifically in the context of linear programming. However, some say Gill's argument is flawed, insofar as the method they describe does not even qualify as an "algorithm", since it requires choices of parameters that don't follow from the internal logic of the method, but rely on external guidance, essentially from Karmarkar's algorithm. Furthermore, Karmarkar's contributions are considered far from obvious in light of all prior work, including Fiacco-McCormick, Gill and others cited by Saltzman.
The patent was eventually granted as : "Methods and apparatus for efficient resource allocation" in May 1988. The patent, however, proved to be of limited commercial value to AT&T. They built up the KORBX system, an 8-processor Alliant
Alliant Computer Systems
Alliant Computer Systems was a computer company that designed and manufactured parallel computing systems. Together with Pyramid Technology and Sequent Computer Systems, Alliant's machines pioneered the symmetric multiprocessing market...
computer incorporating linear programming software using Karmarkar's algorithm, priced at US$8.9 million each, and they only managed to sell two such systems. Opponents of software patents have further alleged that the patents ruined the positive interaction cycles that previously characterized the relationship between researchers in linear programming and industry, and specifically it isolated Karmarkar himself from the network of mathematical researchers in his field.
The patent itself expired in April 2006, and the algorithm is presently in the public domain.