The affine-scaling direction for linear programming is a limit of projective-scaling directions

DOI10.1016/0024-3795(91)90268-2MaRDI QIDQ806963zbMATH OpenOpenAlexWikidataFDO

Authors Michael J. Todd

Publication date 1991

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://hdl.handle.net/1813/8717

zbMATH Keywords

affine-scaling algorithmKarmarker algorithmlinear programmingprojective-scaling algorithm

Mathematics Subject Classification ID

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

Review text

The author first presents the affine-scaling algorithm for linear programming. The second algorithm is the projective-scaling algorithm, which is not invariant under the addition of nonnegatively constrained dummy variables. The author shows that the affine-scaling direction for linear programming is a limit of projective-scaling directions. It is an excellent result.

Recommendations

• scientific article; zbMATH DE number 4197742
• Limiting behavior of the affine scaling continuous trajectories for linear programming problems
• Affine scaling with degenerate linear programming problems
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• scientific article; zbMATH DE number 4197743
• Convergence and Boundary Behavior of the Projective Scaling Trajectories for Linear Programming
• scientific article; zbMATH DE number 1785846
• scientific article; zbMATH DE number 910007
• Generalized affine scaling algorithms for linear programming problems
• Implementing an affine scaling algorithm for linear programming

Cites work

• A modification of Karmarkar's linear programming algorithm
• A monotonic projective algorithm for fractional linear programming
• A new polynomial-time algorithm for linear programming
• A polynomial Newton method for linear programming
• A variant of Karmarkar's linear programming algorithm for problems in standard form
• A Variant of Karmarkar’s Linear Programming Algorithm for Problems with Some Unrestricted Variables
• A variation on Karmarkar’s algorithm for solving linear programming problems
• Boundary Behavior of Interior Point Algorithms in Linear Programming
• Conical projection algorithms for linear programming
• scientific article; zbMATH DE number 3625108 (Why is no real title available?)
• scientific article; zbMATH DE number 4119923 (Why is no real title available?)
• scientific article; zbMATH DE number 3301975 (Why is no real title available?)
• Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
• Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
• Search directions for interior linear-programming methods

Cited in

(3)

• Loss and retention of accuracy in affine scaling methods
• scientific article; zbMATH DE number 1785846 (Why is no real title available?)
• scientific article; zbMATH DE number 4195697 (Why is no real title available?)

This page was built for publication: The affine-scaling direction for linear programming is a limit of projective-scaling directions

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