A conjugate direction method for approximating the analytic center of a polytope

DOI10.1155/S1025583498000113MaRDI QIDQ1386699zbMATH OpenOpenAlexFDO

Authors Nimrod Megiddo, Shinji Mizuno, Masakazu Kojima

Publication date 15 October 1998

Published in Journal of Inequalities and Applications (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/119577

zbMATH Keywords

analytic center of a polytopeconjugate gradient methodsinterior point algorithmslinear programsRenegar's polynomial-time algorithm

Mathematics Subject Classification ID

(n)-dimensional polytopes (52B11) Numerical mathematical programming methods (65K05) Linear programming (90C05)

Review text

The authors suggest a modification of Renegar's polynomial-time algorithm for linear programs. Usually Newton's method is used to trace central trajectory in Renegar's algorithm. The authors' aim is to see whether the conjugate gradient methods can be effectively incorporated in interior point algorithms.

Recommendations

• scientific article; zbMATH DE number 4074370
• scientific article; zbMATH DE number 3972641
• A polynomial method of approximate centers for linear programming
• Algorithmic Enhancements to the Method of Centers for Linear Programming Problems

Cited in

(2)

• scientific article; zbMATH DE number 4074370 (Why is no real title available?)
• Analytic center of spherical shells and its application to analytic center machine

This page was built for publication: A conjugate direction method for approximating the analytic center of a polytope

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