A polynomial Newton method for linear programming
From MaRDI portal
A method for solving systems of affine equations on the nonnegative orthant is proposed. The problem is reduced to the (equivalent) nonlinear programming problem with the cost function in the form of a sum of logarithms. A Newton-like method, based on the second-order approximation of a log-function, is proposed for solving the latter problem. The basic steps of the method are the projection of the vector on the null space of the equation and the one-dimensional search. The procedure computes an exact solution in at most \(0(n^ 3m^ 2L)\) operations (here L is the size of the problem).
Recommendations
- A polynomial-time algorithm, based on Newton's method, for linear programming
- Polynomial affine algorithms for linear programming
- Karmarkar's linear programming algorithm and Newton's method
- A new polynomial-time algorithm for linear programming
- An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations
Cites work
- A new polynomial-time algorithm for linear programming
- An extension of Karmarkar's algorithm for linear programming using dual variables
- An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex
- scientific article; zbMATH DE number 3121281 (Why is no real title available?)
- Khachiyan's linear programming algorithm
Cited in
(49)- Introduction: New approaches to linear programming
- Exploiting special structure in Karmarkar's linear programming algorithm
- A combined phase I-phase II projective algorithm for linear programming
- Cutting planes and column generation techniques with the projective algorithm
- An optimal-basis identification technique for interior-point linear programming algorithms
- On lower bound updates in primal potential reduction methods for linear programming
- A combined phase I-phase II scaled potential algorithm for linear programming
- A survey of search directions in interior point methods for linear programming
- A polynomial-time algorithm to decide liveness of bounded free choice nets
- On Anstreicher's combined phase I-phase II projective algorithm for linear programming
- A polynomial method of approximate centers for linear programming
- On interior algorithms for linear programming with no regularity assumptions
- A projective algorithm for linear programming with no regularity condition
- Recurrent neural networks for linear programming: Analysis and design principles
- On combined phase 1-phase 2 projective methods for linear programming
- Using an interior point method for the master problem in a decomposition approach
- Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming
- On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP
- Updating lower bounds when using Karmarkar's projective algorithm for linear programming
- Experimental behavior of an interior point cutting plane algorithm for convex programming: An application to geometric programming
- Interior-point algorithms for semi-infinite programming
- Potential-reduction methods in mathematical programming
- Long-step strategies in interior-point primal-dual methods
- Solving nonlinear multicommodity flow problems by the analytic center cutting plane method
- A path-following version of the Todd-Burrell procedure for linear programming
- On well definedness of the central path
- A generalized homogeneous and self-dual algorithm for linear programming
- An infeasible-start algorithm for linear programming whose complexity depends on the distance from the starting point to the optimal solution
- A cutting plane method from analytic centers for stochastic programming
- Newton-type method for solving systems of linear equations and inequalities
- Linear updates for a single-phase projective method
- scientific article; zbMATH DE number 5991677 (Why is no real title available?)
- scientific article; zbMATH DE number 4181135 (Why is no real title available?)
- scientific article; zbMATH DE number 4141790 (Why is no real title available?)
- An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex
- scientific article; zbMATH DE number 4110452 (Why is no real title available?)
- Les effets de l'exposant de la fonction barrière multiplicative dans les méthodes de points intérieurs
- scientific article; zbMATH DE number 4119927 (Why is no real title available?)
- On the symmetric affiine scaling algorithm for line programming*
- An alternative derivation of the projective interior point method for linear programming through the least squares approach
- Search directions for a class of projective methods
- The steepest descent gravitational method for linear programming
- Essentials of numerical nonsmooth optimization
- Essentials of numerical nonsmooth optimization
- A little theorem of the big \({\mathcal M}\) in interior point algorithms
- On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm
- On monotonicity in the scaled potential algorithm for linear programming
- The affine-scaling direction for linear programming is a limit of projective-scaling directions
- An \(O(n^ 3L)\) potential reduction algorithm for linear programming
This page was built for publication: A polynomial Newton method for linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1094330)
