Computing Karmarkar projections quickly

DOI10.1007/BF01580753MaRDI QIDQ1107438zbMATH OpenFDO

Authors David F. Shanno

Publication date 1988

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01580753

zbMATH Keywords

Cholesky factorizationcomputation of projectionsKarmarkar's algorithmrank one updatessparsity

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Review text

The paper presents and investigates a numerical method for computing the projections for Karmarkar's algorithm for linear programming. A comparison is carried out with known methods that factor the matrix at each iteration. The numerical results obtained show that the proposed method promises advantages.

Recommendations

• Karmarkar's projective method for linear programming: a computational survey
• Some experiments with Karmarkar's algorithm for linear programming
• A variable-metric variant of the Karmarkar algorithm for linear programming
• scientific article; zbMATH DE number 468924
• scientific article; zbMATH DE number 4068603

Cites work

• A monotonic projective algorithm for fractional linear programming
• A new polynomial-time algorithm for linear programming
• A variant of Karmarkar's linear programming algorithm for problems in standard form
• An experimental approach to karmarkar’s projective method for linear programming
• An extension of Karmarkar's algorithm for linear programming using dual variables
• On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
• On the Modification of LDL T Factorizations

Cited in

(20)

• A reduced-gradient variant of Karmarkar's algorithm and null-space projections
• Long steps in an \(O(n^ 3L)\) algorithm for linear programming
• On partial updating in a potential reduction linear programming algorithm of Kojima, Mizuno, and Yoshise
• An interior point method, based on rank-1 updates, for linear programming
• Computing Karmarkar's projections quickly by using matrix factorization
• El metodo de Karmarkar: Un estudio de sus variantes
• A variable-metric variant of the Karmarkar algorithm for linear programming
• Computing Block-Angular Karmarkar Projections with Applications to Stochastic Programming
• Implementing cholesky factorization for interior point methods of linear programming
• scientific article; zbMATH DE number 176432 (Why is no real title available?)
• scientific article; zbMATH DE number 468924 (Why is no real title available?)
• A Faster Method For Computing Karmarkar's Projections For Large Number of Constraints
• Massive memory buys little speed for complete, in-core sparse Cholesky factorizations on some scalar computers
• Computing projections for the Karmarkar algorithm
• A quadratically convergent method for linear programming
• Optimizing over three-dimensional subspaces in an interior-point method for linear programming
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• An extended variant of Karmarkar's interior point algorithm
• A survey of dynamic network flows
• A standard form variant, and safeguarded linesearch, for the modified Karmarkar algorithm

This page was built for publication: Computing Karmarkar projections quickly

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1107438)