deposit_your_work

A VARIABLE-METRIC VARIANT OF THE KARMARKAR ALGORITHM FOR LINEAR PROGRAMMING

Files in this item

Files Size Format View
8718774.PDF 2.202Mb application/pdf Thumbnail

Show full item record

Item Metadata

Title: A VARIABLE-METRIC VARIANT OF THE KARMARKAR ALGORITHM FOR LINEAR PROGRAMMING
Author: TURNER, KATHRYN
Abstract: The most time-consuming 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 variable-metric 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 polynomial-time 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 polynomial-time 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 VARIABLE-METRIC 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

This item appears in the following Collection(s)