Karmarkar’s algorithm: A view from nonlinear programming

Karmarkar’s algorithm for linear programming has become a highly active field of research, because it is claimed to be supremely efficient for the solution of very large calculations, because it has polynomial-time complexity and because its theoretical properties are interesting. The paper describes the algorithm in the usual way that employs projective transformations and that requires the linear programming problem to be expressed in a standard form, the only inequality constraints being simple bounds on the variables. It then eliminates the dependence on the transformations analytically, which gives the form of the algorithm that can be viewed as a barrier function method from nonlinear programming. In this case the directions of the changes to the variables are solutions of quadratic programming calculations that have no general inequality constraints. By using some of the equalities to eliminate variables, a way is found of applying the algorithm directly to linear programming problems in general form. Thus, except for the addition of at most two new variables that make all but one of the constraints homogeneous, there is no need to increase the original number of variables, even when there are very many constraints. This procedure is applied to a two variable problem with an infinite number of constraints that are derived from tangents to the unit circle. It is found that convergence occurs to a point that, unfortunately, is not the solution of the calculation. In finite cases, however, the present way of treating general linear constraints directly does preserve all the convergence properties of the standard form of Karmarkar’s algorithm.