A variable-metric variant of the Karmarkar algorithm for linear programming |
| |
Authors: | J. E. Dennis Jr. A. M. Morshedi Kathryn Turner |
| |
Affiliation: | (1) Mathematical Sciences Department, Rice University, 77251-1892 Houston, TX, USA;(2) Shell Development Company, Westhollow Research Center, 77001 Houston, TX, USA |
| |
Abstract: | 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. Research sponsored by DOE DE-AS05-82ER13016, ARO DAAG-29-83-K-0035, AFOSR 85-0243. Research sponsored by ARO DAAG-29-83-K-0035, AFOSR 85-0243, Shell Development Company. |
| |
Keywords: | Linear programming Karmarkar algorithm projective algorithm variable-metric Karmarkar |
本文献已被 SpringerLink 等数据库收录! |
|