A survey of search directions in interior point methods for linear programming
From MaRDI portal
Publication:1181912
DOI10.1007/BF01582902zbMath0739.90041MaRDI QIDQ1181912
Cornelis Roos, Dick den Hertog
Publication date: 27 June 1992
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
barrier functions; potential function; interior point algorithm; projected gradient; search direction; Newton directions
90C05: Linear programming
90-02: Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90-08: Computational methods for problems pertaining to operations research and mathematical programming
Related Items
An alternative derivation of the projective interior point method for linear programming through the least squares approach, A potential-reduction variant of Renegar's short-step path-following method for linear programming, An extended variant of Karmarkar's interior point algorithm, Integrability of vector and multivector fields associated with interior point methods for linear programming, Solving combinatorial optimization problems using Karmarkar's algorithm, Prior reduced fill-in in solving equations in interior point algorithms, A weighted least squares study of robustness in interior point linear programming, Degeneracy in interior point methods for linear programming: A survey, Updating lower bounds when using Karmarkar's projective algorithm for linear programming, Interior-point algorithms for semi-infinite programming, A path-following version of the Todd-Burrell procedure for linear programming, Piecewise linear programming via interior points, A class of polynomial variable metric algorithms for linear optimization, A primal-dual interior-point method for linear programming based on a weighted barrier function, An \(O(\sqrt {n} L)\) iteration bound primal-dual cone affine scaling algorithm for linear programming, Uniform bounds on the limiting and marginal derivatives of the analytic center solution over a set of normalized weights
Cites Work
- 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 potential-reduction variant of Renegar's short-step path-following method for linear programming
- A standard form variant, and safeguarded linesearch, for the modified Karmarkar algorithm
- An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
- Computational experience with a dual affine variant of Karmarkar's method for linear programming
- A polynomial Newton method for linear programming
- A multiplicative barrier function method for linear programming
- A polynomial-time algorithm, based on Newton's method, for linear programming
- On the convexity of the multiplicative version of Karmarkar's potential function
- New trajectory-following polynomial-time algorithm for linear programming problems
- Conical projection algorithms for linear programming
- Interior path following primal-dual algorithms. I: Linear programming
- An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
- Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function
- Interior point algorithms for linear programming with inequality constraints
- Long steps in an \(O(n^ 3L)\) algorithm for linear programming
- A polynomial method of approximate centers for linear programming
- Polynomial affine algorithms for linear programming
- An implementation of Karmarkar's algorithm for linear programming
- Search directions for interior linear-programming 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 Polynomial-Time Primal-Dual Affine Scaling Algorithm for Linear and Convex Quadratic Programming and Its Power Series Extension
- A Centered Projective Algorithm for Linear Programming
- A variant of Karmarkar's linear programming algorithm for problems in standard form
- Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
- Boundary Behavior of Interior Point Algorithms in Linear Programming
- A Polynomial Method of Weighted Centers for Convex Quadratic Programming
- Large Step Path-Following Methods for Linear Programming, Part I: Barrier Function Method
- Large Step Path-Following Methods for Linear Programming, Part II: Potential Reduction Method
- Unnamed Item
- Unnamed Item
- Unnamed Item