A multiplicative barrier function method for linear programming

DOI10.1007/BF01840457zbMath0641.90048MaRDI QIDQ1101008

Hiroshi Imai, Masao Iri

Publication date: 1986

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

superlinear convergencebarrier functionKarmarkar's algorithminterior feasible direction methodNewton-like descent algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Newton-type methods (49M15) Linear programming (90C05)

Related Items (32)

Convergence property of the Iri-Imai algorithm for some smooth convex programming problems ⋮ Introduction: New approaches to linear programming ⋮ Potential reduction method for harmonically convex programming ⋮ Search directions for interior linear-programming methods ⋮ Quadratic convergence of the Iri-Imai algorithm for degenerate linear programming problems ⋮ Nonlinear coordinate representations of smooth optimization problems ⋮ 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 ⋮ New complexity results for the Iri-Imai method ⋮ Recursive portfolio management: Large-scale evidence from two Scandinavian stock markets ⋮ Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming ⋮ Geodesic convexity on Rⁿ¹₊ ⋮ 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 ⋮ A convexity theorem for multiplicative functions ⋮ Global ellipsoidal approximations and homotopy methods for solving convex analytic programs ⋮ On the choice of parameters for power-series interior point algorithms in linear programming ⋮ Les effets de l'exposant de la fonction barrière multiplicative dans les méthodes de points intérieurs ⋮ Two design principles of geometric algorithms in finite-precision arithmetic ⋮ A class of polynomial variable metric algorithms for linear optimization ⋮ An ADMM-based interior-point method for large-scale linear programming ⋮ Value estimation approach to the Iri-Imai method for constrained convex optimization ⋮ A unified view of interior point methods for linear programming ⋮ Degeneracy in interior point methods for linear programming: A survey ⋮ A quadratically convergent method for linear programming ⋮ On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP ⋮ An \(O(n^ 3L)\) potential reduction algorithm for linear programming

Cites Work

• A new polynomial-time algorithm for linear programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A multiplicative barrier function method for linear programming