On monotonicity in the scaled potential algorithm for linear programming

DOI10.1016/0024-3795(91)90276-3MaRDI QIDQ805164zbMATH OpenOpenAlexWikidataFDO

Authors Kurt M. Anstreicher

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://doi.org/10.1016/0024-3795(91)90276-3

zbMATH Keywords

affinely scaled potential reduction algorithmKarmarker algorithmScaled potential algorithms

Mathematics Subject Classification ID

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

Review text

Scaled potential algorithms, like the original Karmarker algorithm, may produce iterates which are nonmonotone in the original objective function. This paper contains a modification of the ``affinely scaled potential reduction algorithm proposed by \textit{Y. Ye} [An \(O(n^ 3L)\) potential reduction algorithm for linear programming. Math. Programm., Ser. A 50, No.2, 239-258 (1991)]. This modification makes the method monotone in the original objective function.

Recommendations

• scientific article; zbMATH DE number 1047677
• A combined phase I-phase II scaled potential algorithm for linear programming
• Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
• O(n\({}^ pL)\)-iteration and \(O(n^ 3L)\)-operation potential reduction algorithms for linear programming
• Some remarks on Karmarkar's potential function

Cites work

• A Centered Projective Algorithm for Linear Programming
• A Family of Search Directions for Karmarkar's Algorithm
• 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 variation on Karmarkar’s algorithm for solving linear programming problems
• Conical projection algorithms for linear programming
• Generation of degenerate linear programming problems
• scientific article; zbMATH DE number 4199962 (Why is no real title available?)
• scientific article; zbMATH DE number 4202017 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 3301975 (Why is no real title available?)
• Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
• Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming

Cited in

(3)

• Strict monotonicity in Todd's low-complexity algorithm for linear programming
• Monotonizing linear programs with up to two nonzeroes per column
• Combining phase I and phase II in a potential reduction algorithm for linear programming

This page was built for publication: On monotonicity in the scaled potential algorithm for linear programming

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