Title:

A VARIABLEMETRIC VARIANT OF THE KARMARKAR ALGORITHM FOR LINEAR PROGRAMMING 
Author:

TURNER, KATHRYN 
Degree:

Doctor of Philosophy thesis 
Abstract:

The most timeconsuming part of the Karmarkar algorithm for linear programming is computation of the step direction, which requires the projection of a vector onto the nullspace of a matrix that changes at each iteration. We present a variant of the Karmarkar algorithm that uses standard variablemetric techniques in an innovative way to approximate this projection. We prove that the modified algorithm that we construct using a step direction obtained from this approximation retains the polynomialtime complexity of the Karmarkar algorithm. We extend applicability of the modified algorithm to the solution of linear programming problems with unknown optimal value, using a construction of monotonic lower bounds on the optimal objective value that approximates the lower bound construction of Todd and Burrell. We show that our modified algorithm for solving problems with unknown optimal value also retains the polynomialtime complexity of the Karmarkar algorithm. Computational testing has verified that our modification substantially reduces the number of matrix factorizations needed for the solution of linear programming problems, compared to the number of matrix factorizations required by the Karmarkar algorithm. 
Citation:

TURNER, KATHRYN. (1987) "A VARIABLEMETRIC VARIANT OF THE KARMARKAR ALGORITHM FOR LINEAR PROGRAMMING." Doctoral Thesis, Rice University. http://hdl.handle.net/1911/16112. 
URI:

http://hdl.handle.net/1911/16112 
Date:

1987 