Linear programming and the Newton barrier flow
From MaRDI portal
The author investigates the interior algorithms for linear programming. These algorithms are connected with some trajectories of vectors approximating an optimal solution to a linear programming problem. The author shows that given a bounded polyhedral set P with nonempty interior, the logarithmic barrier function (with no objective components) induces a vector field of negative Newton directions which flows from the center of P to the solution of every possible linear program of P.
Recommendations
- NEWTON FLOW AND INTERIOR POINT METHODS IN LINEAR PROGRAMMING
- A multiplicative barrier function method for linear programming
- Interior path following primal-dual algorithms. I: Linear programming
- Boundary Behavior of Interior Point Algorithms in Linear Programming
- A new polynomial-time algorithm for linear programming
Cites work
- A modification of Karmarkar's linear programming algorithm
- A new polynomial-time algorithm for linear programming
- A polynomial-time algorithm, based on Newton's method, for linear programming
- A variation on Karmarkar’s algorithm for solving linear programming problems
- An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
- Boundary Behavior of Interior Point Algorithms in Linear Programming
- Introduction: New approaches to linear programming
- On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method
- 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
Cited in
(13)- Degeneracy in interior point methods for linear programming: A survey
- K-K-T multiplier estimates and objective function lower bounds from projective SUMT
- Limiting behavior of weighted central paths in linear programming
- scientific article; zbMATH DE number 4204836 (Why is no real title available?)
- Boundary Behavior of Interior Point Algorithms in Linear Programming
- scientific article; zbMATH DE number 4126998 (Why is no real title available?)
- On the generalized path-following methods for linear programming
- On the length of primal-dual projection of potential reduction algorithm
- A Survey on Analog Models of Computation
- A convex analysis view of the barrier problem
- NEWTON FLOW AND INTERIOR POINT METHODS IN LINEAR PROGRAMMING
- The relation between the path of centers and Smale's regularization of the linear programming problem
- Theoretical efficiency of a shifted-barrier-function algorithm for linear programming
This page was built for publication: Linear programming and the Newton barrier flow
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1111465)
