A polynomial-time algorithm, based on Newton's method, for linear programming

DOI10.1007/BF01580724zbMath0654.90050MaRDI QIDQ1108927

James Renegar

Publication date: 1988

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

Newton's methodellipsoid algorithmlinear optimizationinterior methodKarmarkar's algorithmpolynomial time bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05)

Related Items (only showing first 100 items - show all)

Analysis of some interior point continuous trajectories for convex programming ⋮ AN ENTROPY CONTINUATION METHOD FOR A CLASS OF THE PERIODICITY PROBLEMS OF ORDINARY DIFFERENTIAL EQUATIONS ⋮ Minimum Point-Overlap Labeling ⋮ Projective transformations for interior-point algorithms, and a superlinearly convergent algorithm for the w-center problem ⋮ Global convergence analysis of the aggregate constraint homotopy method for nonlinear programming problems with both inequality and equality constraints ⋮ THE CENTRAL PATH IN SMOOTH CONVEX SEMIDEFINITE PROGRAMS ⋮ An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming ⋮ Search directions for interior linear-programming methods ⋮ On Chubanov’s Method for Solving a Homogeneous Inequality System ⋮ Best \(k\)-digit rational bounds for irrational numbers: pre- and super-computer era ⋮ Some results on centers of polytopes ⋮ Unit Capacity Maxflow in Almost $m^{4/3}$ Time ⋮ Log-Barrier Interior Point Methods Are Not Strongly Polynomial ⋮ Intersecting restrictions in clutters ⋮ A new algorithm for minimizing convex functions over convex sets ⋮ An \(O(\sqrt {n} L)\) iteration bound primal-dual cone affine scaling algorithm for linear programming ⋮ On polynomiality of the method of analytic centers for fractional problems ⋮ New infeasible interior-point algorithm based on monomial method ⋮ A cutting plane algorithm for convex programming that uses analytic centers ⋮ A cutting plane method from analytic centers for stochastic programming ⋮ Complexity estimates of some cutting plane methods based on the analytic barrier ⋮ An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities ⋮ Linear programming, complexity theory and elementary functional analysis ⋮ Solving a linear multiperiod portfolio problem by interior-point methodology ⋮ Removing algorithmic discrimination (with minimal individual error) ⋮ Solving Simple Stochastic Games ⋮ Minimum cost flow in the CONGEST model ⋮ Finite convergence into a convex polytope via facet reflections. ⋮ How Do Exponential Size Solutions Arise in Semidefinite Programming? ⋮ Recovering optimal dual solutions in Karmarkar's polynomial algorithm for linear programming ⋮ Predictor-corrector primal-dual interior point method for solving economic dispatch problems: a postoptimization analysis ⋮ Unnamed Item ⋮ An entire space polynomial-time algorithm for linear programming ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ General equilibrium models and homotopy methods ⋮ Properties Of Primal Interior Point Methods For QP^∗ ⋮ A direct heuristic algorithm for linear programming ⋮ Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States ⋮ Calmness of partially perturbed linear systems with an application to the central path ⋮ An improved version of Chubanov's method for solving a homogeneous feasibility problem ⋮ What Tropical Geometry Tells Us about the Complexity of Linear Programming ⋮ Dual versus primal-dual interior-point methods for linear and conic programming ⋮ Polynomial Interior Point Cutting Plane Methods ⋮ Solving the discrete \(l_p\)-approximation problem by a method of centers ⋮ Improved complexity results on solving real-number linear feasibility problems ⋮ The aggregate constraint homotopy method for nonconvex nonlinear programming ⋮ Search directions for a class of projective methods ⋮ Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem ⋮ Suggested research topics in sensitivity and stability analysis for semi- infinite programming problems ⋮ On the convergence of the method of analytic centers when applied to convex quadratic programs ⋮ A new potential reduction algorithm for smooth convex programming ⋮ El metodo de Karmarkar: Un estudio de sus variantes ⋮ Maintaining closeness to the analytic center of a polytope by perturbing added hyperplanes ⋮ Simple Stochastic Games with Few Random Vertices Are Easy to Solve ⋮ Linear programming using limited-precision oracles ⋮ Men and progress in linear programming ⋮ Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem ⋮ Calmness of linear constraint systems under structured perturbations with an application to the path-following scheme ⋮ An exterior-point method for linear programming problems ⋮ An ADMM-based interior-point method for large-scale linear programming ⋮ Computing weighted analytic center for linear matrix inequalities using infeasible Newton's method ⋮ Maximum matching in almost linear time on graphs of bounded clique-width ⋮ Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization ⋮ An exterior point polynomial-time algorithm for convex quadratic programming ⋮ Lagrangian transformation and interior ellipsoid methods in convex optimization ⋮ An interior-point algorithm for the minimization arising from 3D contact problems with friction ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix ⋮ A globally convergent primal-dual interior point algorithm for convex programming ⋮ Interior-point algorithms for semi-infinite programming ⋮ Convergence property of the Iri-Imai algorithm for some smooth convex programming problems ⋮ Extensions of the potential reduction algorithm for linear programming ⋮ Zonotopes and the LP-Newton method ⋮ A new linesearch method for quadratically constrained convex programming ⋮ Potential reduction method for harmonically convex programming ⋮ A primal-dual interior point method whose running time depends only on the constraint matrix ⋮ Long-step strategies in interior-point primal-dual methods ⋮ Improved complexity using higher-order correctors for primal-dual Dikin affine scaling ⋮ Volumetric path following algorithms for linear programming ⋮ A logarithmic barrier cutting plane method for convex programming ⋮ An arc-search \({\mathcal {O}}(nL)\) infeasible-interior-point algorithm for linear programming ⋮ On the complexity of a combined homotopy interior method for convex programming ⋮ Interior-point methods: An old and new approach to nonlinear programming ⋮ Linear programming and the Newton barrier flow ⋮ New trajectory-following polynomial-time algorithm for linear programming problems ⋮ Primal-dual target-following algorithms for linear programming ⋮ An interior-point method for semi-infinite programming problems ⋮ Large step volumetric potential reduction algorithms for linear programming ⋮ New complexity results for the Iri-Imai method ⋮ Identifying an optimal basis in linear programming ⋮ A path-following version of the Todd-Burrell procedure for linear programming ⋮ An extension of predictor-corrector algorithm to a class of convex separable program ⋮ Interior path following primal-dual algorithms. I: Linear programming ⋮ A polynomial-time algorithm for a class of linear complementarity problems ⋮ On the complexity of linear programming under finite precision arithmetic ⋮ Interior point methods 25 years later ⋮ An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations ⋮ A noninterior path following algorithm for solving a class of multiobjective programming problems ⋮ Best \(k\)-digit rational approximation of irrational numbers: pre-computer versus computer era ⋮ On some efficient interior point methods for nonlinear convex programming ⋮ Solving variational inequalities with a quadratic cut method: a primal-dual, Jacobian-free approach

Cites Work

• Towards an asymptotic analysis of Karmarkar's algorithm
• 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
• On the existence of generally convergent algorithms
• On the efficiency of algorithms of analysis
• Boundary Behavior of Interior Point Algorithms in Linear Programming
• Polynomial algorithms in linear programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A polynomial-time algorithm, based on Newton's method, for linear programming