A monotonic projective algorithm for fractional linear programming
From MaRDI portal
(Redirected from Publication:580191)
The purpose of this paper is to demonstrate that N. Karmarkar's projective algorithm [Combinatorica 4, 373-395 (1984; Zbl 0557.90065)] for linear programming is fundamentally an algorithm for fractional linear programming on the simplex. Convergence of the algorithm is established assuming only an initial lower bound on the optimal objective value using either the lower bound construction proposed by the author [Analysis of a modified Karmarkar algorithm for linear programming, Working Paper, Series B 84, Yale School of Oranization and Management, New Haven, CT, 1985.] or a construction proposed by \textit{M. J. Todd} and \textit{B. P. Burrell} [Algorithmica 1, 409-424 (1986; Zbl 0621.90048)]. The author shows that the algorithm can be made monotone and that the monotonic algorithm can be applied to obtain an initial lower bound.
Recommendations
- A combined phase I-phase II projective algorithm for linear programming
- Short Steps with Karmarkar’s Projective Algorithm for Linear Programming
- A Centered Projective Algorithm for Linear Programming
- Karmarkar's linear programming algorithm and Newton's method
- scientific article; zbMATH DE number 4068603
Cites work
Cited in
(53)- Introduction: New approaches to linear programming
- Karmarkar's algorithm and the ellipsoid method
- Relaxed variants of Karmarkar's algorithm for linear programs with unknown optimal objective value
- Exploiting special structure in Karmarkar's linear programming algorithm
- An analog of Karmarkar's algorithm for inequality constrained liner programs, with a `new' class of projective transformations for centering a polytope
- Computing Karmarkar projections quickly
- A relaxed version of Karmarkar's method
- A combined phase I-phase II projective algorithm for linear programming
- Conical projection algorithms for linear programming
- An extension of Karmarkar's projective algorithm for convex quadratic programming
- Cutting planes and column generation techniques with the projective algorithm
- Karmarkar's linear programming algorithm and Newton's method
- A primal projective interior point method for linear programming
- 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
- 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 potential-function reduction algorithm for solving a linear program directly from an infeasible ``warm start
- A survey of search directions in interior point methods for linear programming
- On Anstreicher's combined phase I-phase II projective algorithm for linear programming
- Solving combinatorial optimization problems using Karmarkar's algorithm
- Long steps in an \(O(n^ 3L)\) algorithm for linear programming
- A polynomial method of approximate centers for linear programming
- On combined phase 1-phase 2 projective methods for linear programming
- Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming
- Interior-point algorithms for semi-infinite programming
- Potential-reduction methods in mathematical programming
- A path-following version of the Todd-Burrell procedure for linear programming
- An interior-point method for fractional programs with convex constraints
- The finite criss-cross method for hyperbolic programming
- Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm
- On polynomiality of the method of analytic centers for fractional problems
- Projective transformations for interior-point algorithms, and a superlinearly convergent algorithm for the w-center problem
- Combining phase I and phase II in a potential reduction algorithm for linear programming
- Search directions for interior linear-programming methods
- El metodo de Karmarkar: Un estudio de sus variantes
- Karmarkar's projective method for linear programming: a computational survey
- A variant of Karmarkar's linear programming algorithm for problems in standard form
- A variable-metric variant of the Karmarkar algorithm for linear programming
- An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex
- Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming
- A Polynomial Method of Weighted Centers for Convex Quadratic Programming
- Recursive portfolio management: Large-scale evidence from two Scandinavian stock markets
- Convergence in Karmarkar's algorithm: a review
- A Fourth bibliography of fractional programming
- An alternative derivation of the projective interior point method for linear programming through the least squares approach
- On monotonicity in the scaled potential algorithm for linear programming
- Theoretical efficiency of a shifted-barrier-function 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
- A ``build-down scheme for linear programming
- On the improvement per iteration in Karmarkar's algorithm for linear programming
- A standard form variant, and safeguarded linesearch, for the modified Karmarkar algorithm
This page was built for publication: A monotonic projective algorithm for fractional linear programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q580191)
