Karmarkar's algorithm : a view from nonlinear programming
Degree GrantorUniversity of Canterbury
Degree NameResearch report
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. We describe and study 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. We then eliminate 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, we find a way 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. We apply this procedure to a two variable problem with an infinite number of constraints that are derived from tangents to the unit circle. We find that convergence occurs to a point that, unfortunately, is not the solution of the calculation. In finite cases, however, our way of treating general linear constraints directly does preserve all the convergence properties of the standard form of Karmarkar's algorithm.
SubjectsField of Research::01 - Mathematical Sciences::0101 - Pure Mathematics::010107 - Mathematical Logic, Set Theory, Lattices and Universal Algebra
- Engineering: Reports