A relaxed version of Karmarkar's method

DOI10.1007/BF01580737zbMath0654.90049MaRDI QIDQ1108926

Sanjay Mehrotra, Donald Goldfarb

Publication date: 1988

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

zbMATH Keywords

interior-point methodspolynomial time complexityinexact projectionsrelaxed version of Karmarkar's method

Mathematics Subject Classification ID

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

Related Items

A strengthened acceptance criterion for approximate projections in Karmarkar's algorithm, Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value, A modified homogeneous potential reduction algorithm for solving the monotone semidefinite linear complementarity problem, A combined phase I-phase II projective algorithm for linear programming, A relaxed primal-dual path-following algorithm for linear programming, A primal-dual potential reduction method for problems involving matrix inequalities, A variant of Karmarkar's linear programming algorithm for problems in standard form, A variable-metric variant of the Karmarkar algorithm for linear programming, Karmarkar's algorithm with improved steps, Computational results of an interior point algorithm for large scale linear programming, On interior algorithms for linear programming with no regularity assumptions, An active-set strategy in an interior point method for linear programming, A modified scaling algorithm for LP, El metodo de Karmarkar: Un estudio de sus variantes, On the symmetric affiine scaling algorithm for line programming^*

Uses Software

• LSQR
• CRAIG

Cites Work

• 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 different convergence proof of the projective method for linear programming
• An extension of Karmarkar's algorithm for linear programming using dual variables
• Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value
• An implementation of Karmarkar's algorithm for linear programming
• Evolution of Linear Programming Computing Techniques
• 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 variant of Karmarkar's linear programming algorithm for problems in standard form
• An experimental approach to karmarkar’s projective method for linear programming
• A practicable steepest-edge simplex algorithm
• Polynomial algorithms in linear programming
• Feature Article—The Ellipsoid Method: A Survey
• LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
• Large-scale linearly constrained optimization
• A Self-Correcting Version of Karmarkar’s Algorithm