Show simple item record

dc.contributor.authorTurner, Kathryn
dc.date.accessioned 2018-06-18T17:27:38Z
dc.date.available 2018-06-18T17:27:38Z
dc.date.issued 1987-05
dc.identifier.citation Turner, Kathryn. "A Variable-Metric Variant of the Karmarkar Algorithm for Linear Programming." (1987) https://hdl.handle.net/1911/101624.
dc.identifier.urihttps://hdl.handle.net/1911/101624
dc.descriptionThis work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/16112
dc.description.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 ofthe 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.
dc.format.extent 47 pp
dc.title A Variable-Metric Variant of the Karmarkar Algorithm for Linear Programming
dc.type Technical report
dc.date.note May 1987
dc.identifier.digital TR87-13
dc.type.dcmi Text


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record