Karmarkar's algorithm and the ellipsoid method

DOI10.1016/0167-6377(87)90016-2MaRDI QIDQ1095025zbMATH OpenOpenAlexFDO

Authors Yinyu Ye

Publication date 1987

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(87)90016-2

zbMATH Keywords

ellipsoid methodKarmarkar's algorithmpotential functionprimal and dual programs

Mathematics Subject Classification ID

Linear programming (90C05)

Review text

We show that Karmarkar's algorithm and the ellipsoid method are closely related. At each iteration, the potential function used to measure convergence of the primal solutions in Karmarkar's algorithm correctly characterizes the logarithmic volume of an ellipsoid that contains all of the optimal dual solutions. As the potential function declines, the volume of the ellipsoid monotonicly shrinks to zero. These ellipsoids can be used to determine the optimal basis for linear programming. Conversely, the relation of these two algorithms may lead to an efficient implementation for the ellipsoid method.

Recommendations

• Interior point algorithm for linear programming problem and related inscribed ellipsoids
• Improved Bounds and Containing Ellipsoids in Karmarkar's Linear Programming Algorithm
• scientific article; zbMATH DE number 892328
• Containing and shrinking ellipsoids in the path-following algorithm
• scientific article; zbMATH DE number 3970513

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 extension of Karmarkar's algorithm for linear programming using dual variables
• scientific article; zbMATH DE number 3644821 (Why is no real title available?)
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• The Ellipsoid Method Generates Dual Variables

Cited in

(19)

• Eliminating columns in the simplex method for linear programming
• Primal-dual-infeasible Newton approach for the analytic center deep-cutting plane method
• Degeneracy in interior point methods for linear programming: A survey
• A deep cut ellipsoid algorithm for convex programming: Theory and applications
• Containing and shrinking ellipsoids in the path-following algorithm
• Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem
• An ellipsoid algorithm for the computation of fixed points
• A variation on Karmarkar’s algorithm for solving linear programming problems
• Polynomial time algorithms for some classes of constrained nonconvex quadratic problems
• scientific article; zbMATH DE number 3908161 (Why is no real title available?)
• scientific article; zbMATH DE number 1310536 (Why is no real title available?)
• A direct ellipsoid method for linear programming
• scientific article; zbMATH DE number 568568 (Why is no real title available?)
• scientific article; zbMATH DE number 3727 (Why is no real title available?)
• Interior point algorithm for linear programming problem and related inscribed ellipsoids
• The steepest descent gravitational method for linear programming
• On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm
• A subgradient supported ellipsoid method for convex multiobjective optimization problems
• A ``build-down scheme for linear programming

This page was built for publication: Karmarkar's algorithm and the ellipsoid method

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