Karmarkar's linear programming algorithm and Newton's method

DOI10.1007/BF01594941zbMath0736.90053OpenAlexW1985393884WikidataQ102106404 ScholiaQ102106404MaRDI QIDQ1176568

David Bayer, Jeffrey C. Lagarias

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/bf01594941

zbMATH Keywords

global Newton methodlogarithmic barrier functionKarmarkar's linear programming algorithmprojective scaling algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonlinear programming (90C30) Newton-type methods (49M15) Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items

Projective transformations for interior-point algorithms, and a superlinearly convergent algorithm for the w-center problem, An Infeasible Mizuno–Todd–Ye Type Algorithm for Convex Quadratic Programming with Polynomial Complexity, Search directions for interior linear-programming methods, Potential-reduction methods in mathematical programming, NEWTON FLOW AND INTERIOR POINT METHODS IN LINEAR PROGRAMMING, New trajectory-following polynomial-time algorithm for linear programming problems, An interior point algorithm for nonlinear quantile regression, On the convex programming approach to linear programming, Enlarging neighborhoods of interior-point algorithms for linear programming via least values of proximity measure functions, A new primal-dual path-following interior-point algorithm for linearly constrained convex optimization, Optimizing over three-dimensional subspaces in an interior-point method for linear programming, On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP, A Survey on Analog Models of Computation, Deriving an unconstrained convex program for linear programming, A global Newton method. II: Analytic centers

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A monotonic projective algorithm for fractional linear programming
• A modification of Karmarkar's linear programming algorithm
• A new polynomial-time algorithm for linear programming
• A multiplicative barrier function method for linear programming
• An analog of Karmarkar's algorithm for inequality constrained liner programs, with a `new' class of projective transformations for centering a polytope
• A polynomial-time algorithm, based on Newton's method, for linear programming
• A convergent process of price adjustment and global Newton methods
• On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
• A variation on Karmarkar’s algorithm for solving linear programming problems
• A Collinear Scaling Interpretation of Karmarkar’s Linear Programming Algorithm
• The Nonlinear Geometry of Linear Programming. III Projective Legendre Transform Coordinates and Hilbert Geometry
• 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
• Conic Approximations and Collinear Scalings for Optimizers
• Variable Metric Method for Minimization
• Quasi-Newton Methods, Motivation and Theory