An Investigation of Karmarkar's Algorithm for Linear Programming.

During this contract period DSA has concentrated on achieving a geometrical rather than an algebraic understanding of Karmarkars algorithm, and on the formulation of alternative approaches that retain the main advantages of Karmarkars approach while avoiding the undesireable computational aspects of his specific algorithm. From a geometric perspective, we have asked why does the algorithm work, when it works How can one understand the convergence process, which occurs in the shifting coordinates of Karmarkars simplex, in terms of an orderly convergence process in the original space This has led to a number of non-obvious insights concerning the essence of the Karmarkar algorithm. The findings of this part of the study are contained in a separate report that has been distributed, and is being prepared for publication. Keywords Optimization non-linear programming quadratic programming numerical stability.