An extension of Karmarkar's algorithm for linear programming using dual variables
From MaRDI portal
Publication:1090601
DOI10.1007/BF01840455zbMath0621.90048OpenAlexW1982967176MaRDI QIDQ1090601
Bruce P. Burrell, Michael J. Todd
Publication date: 1986
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01840455
Numerical mathematical programming methods (65K05) Large-scale problems in mathematical programming (90C06) Linear programming (90C05)
Related Items (72)
Interior-point algorithms for semi-infinite programming ⋮ Projective transformations for interior-point algorithms, and a superlinearly convergent algorithm for the w-center problem ⋮ Introduction: New approaches to linear programming ⋮ A strengthened acceptance criterion for approximate projections in Karmarkar's algorithm ⋮ A polynomial Newton method for linear programming ⋮ Karmarkar's algorithm and the ellipsoid method ⋮ Convergence results and numerical experiments on a linear programming hybrid algorithm ⋮ Implementing an affine scaling algorithm for linear programming ⋮ Search directions for interior linear-programming methods ⋮ A sequential quadratic programming method for potentially infeasible mathematical programs ⋮ 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 ⋮ Potential-reduction methods in mathematical programming ⋮ Computing Karmarkar projections quickly ⋮ A relaxed version of Karmarkar's method ⋮ On the convexity of the multiplicative version of Karmarkar's potential function ⋮ New trajectory-following polynomial-time algorithm for linear programming problems ⋮ A combined phase I-phase II projective algorithm for linear programming ⋮ Conical projection algorithms for linear programming ⋮ A path-following version of the Todd-Burrell procedure for linear programming ⋮ Convergence in Karmarkar's algorithm: a review ⋮ An extension of Karmarkar's projective algorithm for convex quadratic programming ⋮ Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm ⋮ Cutting planes and column generation techniques with the projective algorithm ⋮ An interior-point method for generalized linear-fractional programming ⋮ Recursive portfolio management: Large-scale evidence from two Scandinavian stock markets ⋮ Discrete-time Takagi-Sugeno singular systems with unmeasurable decision variables: state and fault fuzzy observer design ⋮ 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 ⋮ Karmarkar's algorithm with improved steps ⋮ Asymptotic behaviour of Karmarkar's method 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 ⋮ Geodesic convexity on Rn1+ ⋮ An optimal-basis identification technique for interior-point linear programming algorithms ⋮ An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems ⋮ 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 ⋮ Solving combinatorial optimization problems using Karmarkar's algorithm ⋮ A polynomial method of approximate centers for linear programming ⋮ Generalization of Karmarkar's algorithm to convex homogeneous functions ⋮ Generalized convexity on affine subspaces with an application to potential functions ⋮ A projective algorithm for linear programming with no regularity condition ⋮ Recurrent neural networks for linear programming: Analysis and design principles ⋮ On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm ⋮ On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method ⋮ On combined phase 1-phase 2 projective methods for linear programming ⋮ Loss and retention of accuracy in affine scaling methods ⋮ Search directions for a class of projective methods ⋮ Linear updates for a single-phase projective method ⋮ The steepest descent gravitational method for linear programming ⋮ Extension of a projective interior point method for linearly constrained convex programming ⋮ El metodo de Karmarkar: Un estudio de sus variantes ⋮ Polynomial affine algorithms for linear programming ⋮ Maintaining LU factors of a general sparse matrix ⋮ An implementation of Karmarkar's algorithm for linear programming ⋮ A unified view of interior point methods for linear programming ⋮ Degeneracy in interior point methods for linear programming: A survey ⋮ Theoretical efficiency of a shifted-barrier-function algorithm for linear programming ⋮ Computing projections for the Karmarkar algorithm ⋮ Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming ⋮ An \(O(n^ 3L)\) potential reduction algorithm for linear programming ⋮ Updating lower bounds when using Karmarkar's projective algorithm for linear programming ⋮ On the number of iterations of Karmarkar's algorithm for linear programming
Cites Work
- A new polynomial-time algorithm for linear programming
- Solution of sparse linear least squares problems using Givens rotations
- Extensions of Lemke's algorithm for the linear complementarity problem
- Some Extensions of an Algorithm for Sparse Linear Least Squares Problems
- A class of methods for linear programming
- Programming with linear fractional functionals
- Unnamed Item
- Unnamed Item
This page was built for publication: An extension of Karmarkar's algorithm for linear programming using dual variables
