bs@faron.UUCP (Robert D. Silverman) (12/14/84)
Karmarkar'snew algorithm really is as good as people claim. It works via linear projective transformation. Basically it maps via transformation the n-dimensional convex polytope of the LP problem and an interior point onto an n+1 dimensional simplex so that the interior point maps to the center of the simplex. The radius of circumscribed to inscribed spheres on the simplex is exactly n Finding an extremum of the obective function subject to being on the surface of a sphere is a trivial problem. Simply move in the direction of the gradient of the objective function from the center of the sphere a distance equal to the radius of the sphere. Thus, in the transformed simplex each iteration og the algorithm moves you at worst 1/n'th of the way from the interior point (now the center) to the optimal vertex. In practice the algorithm takes O(log(n)) iterations to converge on the optimal vertex compared with the Simplex method's O(n) iterations. The work done at each iteration by both algorithms is comparable. However, the worst case for Karmarkar's algorithm is O(n) compared with the O(2**n) for the Simplex method. The new method may be applied to optimization problems over any convex hull, regardless of the objective function. The paper has appeared or will shortly appear in the Hungarian journal 'Combinatorica'.