A multiplicative barrier function method for linear programming
From MaRDI portal
The authors propose a Newton-like descent algorithm to solve linear programming problems. The algorithm is similar to \textit{N. Karmarkar}'s algorithm [Combinatorica 4, 373-395 (1984; Zbl 0557.90065)] in that it is an interior feasible direction method and self-correcting, while it is quite different from Karmarkar's in that it gives superlinear convergence and that no artificial extra constraint is introduced nor is projective geometry needed. The authors record extensive computational experience on a number of problems of different sizes.
Recommendations
- scientific article; zbMATH DE number 4059112
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- Dual barrier functions with superfast rates of convergence for the linear programming problem
- Karmarkar's linear programming algorithm and Newton's method
- An interior point method for linear programming
Cites work
- A new polynomial-time algorithm for linear programming
- scientific article; zbMATH DE number 3644821 (Why is no real title available?)
- scientific article; zbMATH DE number 3672004 (Why is no real title available?)
- scientific article; zbMATH DE number 3466805 (Why is no real title available?)
- scientific article; zbMATH DE number 3626518 (Why is no real title available?)
Cited in
(45)- Introduction: New approaches to linear programming
- Linear programming and the Newton barrier flow
- 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
- Karmarkar's linear programming algorithm and Newton's method
- Interior point algorithms for linear programming with inequality constraints
- Improving the rate of convergence of interior point methods for linear programming
- A survey of search directions in interior point methods for linear programming
- Integrability of vector and multivector fields associated with interior point methods for linear programming
- Generalized convexity on affine subspaces with an application to potential functions
- Degeneracy in interior point methods for linear programming: A survey
- On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP
- Convergence property of the Iri-Imai algorithm for some smooth convex programming problems
- On the choice of parameters for power-series interior point algorithms in linear programming
- A class of polynomial variable metric algorithms for linear optimization
- Potential reduction method for harmonically convex programming
- Quadratic convergence of the Iri-Imai algorithm for degenerate linear programming problems
- Nonlinear coordinate representations of smooth optimization problems
- New complexity results for the Iri-Imai method
- Value estimation approach to the Iri-Imai method for constrained convex optimization
- Search directions for interior linear-programming methods
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- An experimental investigation of a new multiplex method for linear programming
- Dual barrier functions with superfast rates of convergence for the linear programming problem
- Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
- scientific article; zbMATH DE number 4059112 (Why is no real title available?)
- Large Step Path-Following Methods for Linear Programming, Part I: Barrier Function Method
- Recursive portfolio management: Large-scale evidence from two Scandinavian stock markets
- scientific article; zbMATH DE number 123727 (Why is no real title available?)
- Geodesic convexity on Rn1+
- Les effets de l'exposant de la fonction barrière multiplicative dans les méthodes de points intérieurs
- Inverse barrier methods for linear programming
- A logarithm barrier method for linear programming
- An ADMM-based interior-point method for large-scale linear programming
- NEWTON FLOW AND INTERIOR POINT METHODS IN LINEAR PROGRAMMING
- Global ellipsoidal approximations and homotopy methods for solving convex analytic programs
- A convexity theorem for multiplicative functions
- On the equivalence of the simplex methods and a multiplier-alike method for linear programming
- Two design principles of geometric algorithms in finite-precision arithmetic
- A unified view of interior point methods for linear programming
- Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
- A quadratically convergent method for linear programming
- An \(O(n^ 3L)\) potential reduction algorithm for linear programming
- The modified barrier function method for linear programming and its extensions
This page was built for publication: A multiplicative barrier function method for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1101008)
