From: borchers@rainbow.nmt.edu (Brian Borchers)
Subject: Re: Karmarkar's method
Date: Sun, 4 Feb 2001 20:55:24 +0000 (UTC)
Newsgroups: sci.math.num-analysis,sci.op-research
Summary: Interior point methods in linear programming

Tim Chow wrote:
>Doesn't the term "interior point method" include the ellipsoid method?

This is a question of nomenclature, and it clearly depends on how you
define "interior point method", but I personally wouldn't consider the
ellipsoid algorithm to be an interior point method because it isn't
similar in its details or in its performance to the other methods that
we now call "interior point methods."

Khachian's ellipsoid algorithm (1979) settled the issue of whether or
not LP could be solved in polynomial time, and soon led to the
important result of Groetschel, Lovasz, and Schrijver on the
polynomial equivalence of separation and optimization (1981.) However,
it was quickly discovered that this algorithm was of little computational
use.

Khachian's algorithm requires O(n^2 L) iterations (n is the number of
variables, L is the size of the problem data in bits) while interior
point methods typically require O(sqrt(n) L) iterations.
 
I'm aware of some papers which showed connections between the
ellipsoid algorithm and what are now called interior point methods,
but the connection is (IMHO) tenuous.

Looking through the contemporary books on my shelf that discuss
interior point methods I find that the ellipsoid algorithm is seldom
discussed in more than an historical footnote.

One older book that contains a very readable discussion of the
ellipsoid method is Chvatal's "Linear Programming."
 
-- 
Brian Borchers                          borchers@nmt.edu
Department of Mathematics               http://www.nmt.edu/~borchers/
New Mexico Tech                         Phone: 505-835-5813
Socorro, NM 87801                       FAX: 505-835-5366