New trajectory-following polynomial-time algorithm for linear programming problems

DOI10.1007/BF00939806MaRDI QIDQ1114587zbMATH OpenFDO

Authors C. Roos

Publication date 1989

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF00939806

zbMATH Keywords

interior point methodpath following methodspolynomial time bound

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Review text

A new interior point method for the solution of the linear programming problem is presented. It is shown that the method admits a polynomial time bound. The method is based on the use of the trajectory of the problem, which makes it conceptually very simple. It has the advantage above related methods that it requires no problem transformation (either affine or projective) and that the feasible region may be unbounded. More importantly, the method generates at each stage solutions of both the primal and the dual problem. This implies that, contrary to the simplex method, the quality of the present solution is known at each stage. The paper also contains a practical (i.e., a deep step) version of the algorithm.

Recommendations

• A new polynomial-time algorithm for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• A primal projective interior point method for linear programming
• scientific article; zbMATH DE number 938987
• Interior path following primal-dual algorithms. I: Linear programming

Cites work

• A modification of Karmarkar's linear programming algorithm
• A multiplicative barrier function method for linear programming
• A new polynomial-time algorithm for linear programming
• A polynomial-time algorithm, based on Newton's method, for linear programming
• An extension of Karmarkar's algorithm for linear programming using dual variables
• An implementation of Karmarkar's algorithm for linear programming
• scientific article; zbMATH DE number 4164543 (Why is no real title available?)
• scientific article; zbMATH DE number 3809326 (Why is no real title available?)
• scientific article; zbMATH DE number 4048535 (Why is no real title available?)
• scientific article; zbMATH DE number 3253619 (Why is no real title available?)
• scientific article; zbMATH DE number 3381785 (Why is no real title available?)
• Karmarkar's linear programming algorithm and Newton's method
• On the convexity of the multiplicative version of Karmarkar's potential function
• Search directions for interior linear-programming methods
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• The Nonlinear Geometry of Linear Programming. II Legendre Transform Coordinates and Central Trajectories
• The Nonlinear Geometry of Linear Programming. III Projective Legendre Transform Coordinates and Hilbert Geometry

Cited in

(19)

• A polynomial-time algorithm, based on Newton's method, for linear programming
• A primal projective interior point method for linear programming
• A survey of search directions in interior point methods for linear programming
• A polynomial method of approximate centers for linear programming
• Volumetric path following algorithms for linear programming
• A path-following version of the Todd-Burrell procedure for linear programming
• An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities
• An interior point continuous path-following trajectory for linear programming
• New interior point algorithms in linear programming
• A Polynomial Method of Weighted Centers for Convex Quadratic Programming
• Algorithmic Enhancements to the Method of Centers for Linear Programming Problems
• scientific article; zbMATH DE number 1336278 (Why is no real title available?)
• A Path-Following Projective Interior Point Method for Linear Programming
• Following a “Balanced” Trajectory from an Infeasible Point to an Optimal Linear Programming Solution with a Polynomial-Time Algorithm
• scientific article; zbMATH DE number 1150439 (Why is no real title available?)
• scientific article; zbMATH DE number 938987 (Why is no real title available?)
• Analysis of some interior point continuous trajectories for convex programming
• scientific article; zbMATH DE number 5066284 (Why is no real title available?)
• On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm

This page was built for publication: New trajectory-following polynomial-time algorithm for linear programming problems

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