A Centered Projective Algorithm for Linear Programming
Mathematics of Operations ResearchPublished 1 August 1990
Michael J. Todd, Yinyu Ye
Citations154
SJR quartileQ1
SJR score1.35
SNIP1.90
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A projective algorithms for linear programming that shares features with Karmarkar's projective algorithm and its variants and with the path-following methods of Gonzaga, Kojima-Mizuno-Yoshise, Monteiro-Adler, Renegar, Vaidya and Ye is described.
Abstract
We describe a projective algorithm for linear programming that shares features with Karmarkar's projective algorithm and its variants and with the path-following methods of Gonzaga, Kojima-Mizuno-Yoshise, Monteiro-Adler, Renegar, Vaidya and Ye. It operates in a primal-dual setting, stays close to the central trajectories, and converges in O(√n L) iterations like the latter methods. (Here n is the number of variables and L the input size of the problem.) However, it is motivated by seeking reductions in a suitable potential function as in projective algorithms, and the approximate centering is an automatic byproduct of our choice of potential function.
Keywords
Computer ScienceMathematics
COMBINATORICAA new polynomial-time algorithm for linear programming
4,840 Citations1984Narendra Karmarkar
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)Nonlinear programming: sequential unconstrained minimization techniques
2,272 Citations1968Anthony V. Fiacco, Garth P. McCormick
Pathways to the Optimal Set in Linear Programming
588 Citations1989Nimrod Megiddo
Mathematical ProgrammingA polynomial-time algorithm, based on Newton's method, for linear programming
585 Citations1988James Renegar
A new interior method for linear programming is presented and a polynomial time bound for it is proven and it is conceptually simpler than either the ellipsoid algorithm or Karmarkar's algorithm.
A Primal-Dual Interior Point Algorithm for Linear Programming
489 Citations1989Masakazu Kojima, Shinji Mizuno +1 more
Mathematical ProgrammingInterior path following primal-dual algorithms. part I: Linear programming
488 Citations1989Renato D. C. Monteiro, Ilan Adler
A primal-dual interior point algorithm for linear programming problems which requires a total of O(n L) number of iterations to find the Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem.
Mathematical ProgrammingAn implementation of Karmarkar's algorithm for linear programming
422 Citations1989Ilan Adler, Maurício G. C. Resende +2 more
Based on a continuous version of Karmarkar's algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested and compares favorably with the simplex codeMinos 4.0.
AlgorithmicaA modification of karmarkar's linear programming algorithm
357 Citations1986Robert J. Vanderbei, Marc S. Meketon +1 more
A modification of Karmarkar's linear programming algorithm that uses a recentered projected gradient approach thereby obviating a priori knowledge of the optimal objective function value and proves that the algorithm converges.
Lecture notes in control and information sciencesAn "analytical centre" for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming
356 Citations2006Gy. Sonnevend
The above results are applied to outline new approaches to linear (smooth, convex) programming by constructing affine invariant relatives of Karmarkar'-s interior point, projective invariant method.
Mathematical ProgrammingA polynomial-time algorithm for a class of linear complementarity problems
340 Citations1989Masakazu Kojima, Shinji Mizuno +1 more
An algorithm is presented that solves the problem of finding n-dimensional vectors in O(n3L) arithmetic operations by tracing the path of centers by identifying the centers of centers of the feasible region.
Mathematical ProgrammingInterior path following primal-dual algorithms. part II: Convex quadratic programming
334 Citations1989Renato D. C. Monteiro, Ilan Adler
A primal-dual interior point algorithm for convex quadratic programming problems which requires a total of O(n3L) number of iterations, whereL is the input size.
Mathematical ProgrammingA variation on Karmarkar’s algorithm for solving linear programming problems
331 Citations1986Earl Barnes
The algorithm described here is a variation on Karmarkar’s algorithm for linear programming that applies to the standard form of a linear programming problem and produces a monotone decreasing sequence of values of the objective function.
Mathematical ProgrammingAn O(n 3 L) potential reduction algorithm for linear programming
289 Citations1991Yinyu Ye
Neither tracing the central path nor using the projective transformation, the algorithm converges to the optimal solution set in O(\sqrt n L) iterations and uses O(n3L) total arithmetic operations.
An Algorithm for Solving Linear Programming Problems in O(n 3 L) Operations
204 Citations1989Clóvis C. Gonzaga
This chapter describes a short-step penalty function algorithm that solves linear programming problems in no more than O(n 0.5 L) iterations and follows the path of optimal solutions for the penalized functions as in a predictor-corrector homotopy algorithm.
Mathematical ProgrammingAn algorithm for linear programming which requires O(((m+n)n 2+(m+n)1.5 n)L) arithmetic operations
197 Citations1990Pravin M. Vaidya
Transactions of the American Mathematical SocietyThe nonlinear geometry of linear programming. I. Affine and projective scaling trajectories
182 Citations1989David Bayer, Jeffrey C. Lagarias
Interior path following primal-dual algorithms
163 Citations1988Renato Duarte Carneiro Monteiro, Ilan Adler
This work describes a primal-dual interior point algorithm for linear programming and convex quadratic programming problems which requires a total of O(n$\sp3$L) arithmetic operations and shows that the duality gap is reduced at each iteration by a factor of 1, where $\delta$ is positive and depends on some parameters associated with the objective function.
AlgorithmicaAn extension of Karmarkar's algorithm for linear programming using dual variables
153 Citations1986Michael J. Todd, Bruce P. Burrell
An extension of Karmarkar's algorithm for linear programming that handles problems with unknown optimal value and generates Primal and dual solutions with objective values converging to the common optimal primal and dual value is described.
Mathematics of Operations ResearchBoundary Behavior of Interior Point Algorithms in Linear Programming
143 Citations1989Nimrod Megiddo, Michael Shub
It is proved that all the trajectories have a unique asymptotic direction of convergence to the optimum of the linear rescaling algorithm.
AlgorithmicaA polynomial newton method for linear programming
139 Citations1986Guy de Ghellinck, J.‐P. Vial
An algorithm is presented for solving a set of linear equations on the nonnegative orthant which can be made equivalent to the maximization of a simple concave function subject to a similar set oflinear equations and bounds on the variables.
Interior Algorithms for Linear, Quadratic, and Linearly Constrained Convex Programming
56 Citations1997Edison Tse, Yinyu Ye
Practical approaches to efficiently implementing the interior algorithms are proposed--approaches that bypass the difficulties found in Karmarkar's original algorithm for linear programs, relax the small-step-size restriction in the path-following algorithm, and solve more general linearly constrained convex programs.
Mathematical ProgrammingExploiting special structure in Karmarkar's linear programming algorithm
27 Citations1988Michael J. Todd
Methods to take advantage of specially-structured constraints in a variant of Karmarkar's projective algorithm for standard form linear programming problems can be proposed to generate improved bounds on the optimal value of the problem and also to compute the necessary projections more efficiently, while maintaining the theoretical bound on the algorithm's performance.
Mathematical ProgrammingContaining and shrinking ellipsoids in the path-following algorithm
24 Citations1990Yinyu Ye, Michael J. Todd
A new potential function and a sequence of ellipsoids in the path-following algorithm for convex quadratic programming that contains all of the optimal primal and dual slack vectors.
Mathematical ProgrammingAn extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex
23 Citations1987Guy de Ghellinck, Jean-Philippe Vial
An extension of Karmarkar's algorithm for solving a system of linear homogeneous equations on the simplex is presented and it is shown that in at most O(nL) steps the algorithm produces a feasible point or proves that the problem has no solution.
Mathematics of Operations ResearchThe Worst-Case Step in Karmarkar's Algorithm
14 Citations1989Kurt M. Anstreicher
The worst-case performance in a single step of Karmarkar's projective algorithm for linear programming is considered, and it is shown that the critical ratio “r/R” can be improved (asymptotically) by a factor of two.
Mathematical ProgrammingOn the improvement per iteration in Karmarkar's algorithm for linear programming
10 Citations1990Colin McDiarmid
The decrease in potential at an iteration of Karmarkar's projective method for linear programming is investigated, showing the precise result thatδn(α) equals ln(1 +α)-ln(1 −α/(n − 1)) forn sufficiently large.
Nō to shinkei Brain and nerveOn the Relationship Between the Search Directions in the Affine and Projective Variants of Karmarkar's Linear Programming Algorithm
8 Citations1986John E. Mitchell, Michael J. Todd