A Variable Metric Variant of the Karmarkar Algorithm for Linear Programming
Dennis, J.E. Jr.
The most time-consuming part of the Karmarkar algorithm for linear programming is 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. In limited tests, this modification greatly reduces the number of matrix factorizations needed for the solution of linear programming problems.
Citable link to this pagehttps://hdl.handle.net/1911/101601
MetadataShow full item record
- CAAM Technical Reports