Computing projections for the Karmarkar algorithm

DOI10.1016/0024-3795(91)90272-XMaRDI QIDQ806966zbMATH OpenFDO

Authors Kathryn Turner

Publication date 1991

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(91)90272-X

zbMATH Keywords

Karmarkar algorithmlinear programmingsparsity

Mathematics Subject Classification ID

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

Review text

For computing the projection of a vector onto the nullspace of a matrix some alternatives are considered. Especially the sparsity of the computed matrices is investigated. The author works with an extended but indefinite matrix which is usually sparser than the originally used normal matrix. For the solution process a subroutine from Harwell is modified. Computational results are given for twelve test problems in the Netlib test set. These results indicate a computational advantage for factoring the extended matrix.

Recommendations

• Computing Karmarkar projections quickly
• Karmarkar's projective algorithm: A null space variant for multi- commodity generalized networks
• Some experiments with Karmarkar's algorithm for linear programming
• Publication:3486755
• A reduced-gradient variant of Karmarkar's algorithm and null-space projections

Cites work

• A new polynomial-time algorithm for linear programming
• A variable-metric variant of the Karmarkar algorithm for linear programming
• An extension of Karmarkar's algorithm for linear programming using dual variables
• scientific article; zbMATH DE number 3928227 (Why is no real title available?)
• The Factorization of Sparse Symmetric Indefinite Matrices
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear

Cited in

(9)

• The role of the augmented system in interior point methods
• Solving symmetric indefinite systems in an interior-point method for linear programming
• An algorithm for finding projections with extreme kurtosis
• Loss and retention of accuracy in affine scaling methods
• scientific article; zbMATH DE number 4037557 (Why is no real title available?)
• scientific article; zbMATH DE number 11760 (Why is no real title available?)
• LOQO:an interior point code for quadratic programming
• Computational performance of a projection and rescaling algorithm
• Computing projections with LSQR

Describes a project that uses

Uses Software

• MA27
• NETLIB LP Test Set

This page was built for publication: Computing projections for the Karmarkar algorithm

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