Convergence results and numerical experiments on a linear programming hybrid algorithm

DOI10.1016/0377-2217(87)90270-0MaRDI QIDQ1095026zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1987

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(87)90270-0

zbMATH Keywords

column scalingconvergence resultsinterior-feasible-preserving algorithmKarmarkar's algorithmmodificationorthogonal projectionscaling algorithmsteepest descent directions

Mathematics Subject Classification ID

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

Review text

A modification of Karmarkar's algorithm for linear programming successively generates column-scaled equivalents of the original linear program, and in the scaled coordinates obtains improvements according to steepest descent directions. As an interior-feasible-preserving algorithm, termination requires a purification algorithm to obtain a dual basic optimal solution. Together the two algorithms comprise a `hybrid' procedure for solving linear programs. In this paper we present some convergence results on the Phase II and Phase I portions of the scaling algorithm. We also present results of numerical experiments on examples of Klee-Minty type which show sensitivity to the starting interior-feasible point and steepest descent step size.

Recommendations

• Convergence in Karmarkar’s Algorithm for Linear Programming
• Publication:4887688
• Some experiments with Karmarkar's algorithm for linear programming
• scientific article; zbMATH DE number 4085412
• On the Performance of Karmarkar's Algorithm

Cites work

• A new polynomial-time algorithm for linear programming
• A variant of Karmarkar's linear programming algorithm for problems in standard form
• An experimental approach to karmarkar’s projective method for linear programming
• An extension of Karmarkar's algorithm for linear programming using dual variables
• Intelligent gradient search in linear programming
• Iterative linear programming solution of convex programs
• On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
• On semi-infinite systems of linear inequalities
• The efficient solution of large-scale linear programming problems—some algorithmic techniques and computational results
• The iterative step in the linear programming algorithm of N. Karmarkar
• THE STRONG MINKOWSKI FARKAS-WEYL THEOREM FOR VECTOR SPACES OVER ORDERED FIELDS

Cited in

(16)

• Implementing an affine scaling algorithm for linear programming
• An interior point algorithm for semi-infinite linear programming
• On the convergence of the affine-scaling algorithm
• Interior-point algorithms for semi-infinite programming
• On motivating the Mitchell-Todd modification of Karmarkar's algorithm for LP problems with free variables
• A hybrid method for linear programming
• An affine-scaling pivot algorithm for linear programming
• A modified scaling algorithm for LP
• scientific article; zbMATH DE number 4064763 (Why is no real title available?)
• A second order affine scaling algorithm for the geometric programming dual with logarithmic barrier
• scientific article; zbMATH DE number 913271 (Why is no real title available?)
• A Hybrid Direction Algorithm with Long Step Rule for Linear Programming: Numerical Experiments
• Computation of the collapse state in limit analysis using the LP primal affine scaling algorithm
• Computing material collapse displacement fields on a Cray X-MP/48 by the LP primal affine scaling algorithm
• An \(O(n^ 3L)\) potential reduction algorithm for linear programming
• Asymptotic behaviour of Karmarkar's method for linear programming

This page was built for publication: Convergence results and numerical experiments on a linear programming hybrid algorithm

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