A primal projective interior point method for linear programming

DOI10.1007/BF01586924MaRDI QIDQ1176804zbMATH OpenFDO

Authors Donald Goldfarb, Dong Xiao

Publication date 25 June 1992

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

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

zbMATH Keywords

polynomial timeprojective interior point algorithm

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Linear programming (90C05) Fractional programming (90C32)

Review text

The authors present a new projective interior point algorithm [cf. \textit{N. Karmarkar}, Combinatorica 4, No. 4, 373-395 (1984; Zbl 0557.90065)] which solves linear programming problems in polynomial time without requiring knowledge of the optimal value of the objective function, or a lower bound for this value. To start with, the algorithm requires only that an interior feasible point be provided. In the absence of degeneracy it generates a monotonically decreasing sequence of objective values which converges to the optimal objective value, if it exists, or proves that the problem is unbounded. No computational results for the algorithm are given.

Recommendations

• A new polynomial-time algorithm for linear programming
• New trajectory-following polynomial-time algorithm for linear programming problems
• On the finite convergence of interior-point algorithms for linear programming
• A primal-dual infeasible-interior-point algorithm for linear programming
• A Centered Projective Algorithm for Linear Programming

Cites work

• A different convergence proof of the projective method for linear programming
• 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 Self-Correcting Version of Karmarkar’s Algorithm
• A variation on Karmarkar’s algorithm for solving linear programming problems
• An extension of Karmarkar's algorithm for linear programming using dual variables
• Conical projection algorithms for linear programming
• scientific article; zbMATH DE number 4202017 (Why is no real title available?)
• scientific article; zbMATH DE number 3625108 (Why is no real title available?)
• scientific article; zbMATH DE number 3301975 (Why is no real title available?)
• Interior path following primal-dual algorithms. I: Linear programming

Cited in

(13)

• New trajectory-following polynomial-time algorithm for linear programming problems
• On interior algorithms for linear programming with no regularity assumptions
• Polynomial primal-dual cone affine scaling for semidefinite programming
• An infeasible-interior-point algorithm using projections onto a convex set
• An \(O(\sqrt {n} L)\) iteration bound primal-dual cone affine scaling algorithm for linear programming
• Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programming
• scientific article; zbMATH DE number 1801376 (Why is no real title available?)
• An experimental approach to karmarkar’s projective method for linear programming
• scientific article; zbMATH DE number 4070200 (Why is no real title available?)
• A fifth bibliography of fractional programming^*
• A Path-Following Projective Interior Point Method for Linear Programming
• A circular cone relaxation primal interior point algorithm for LP
• PCx: an interior-point code for linear programming

This page was built for publication: A primal projective interior point method for linear programming

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