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

From MaRDI portal

Publication:1108927

Jump to:navigation, search

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 method ellipsoid algorithm linear optimization interior method Karmarkar's algorithm polynomial time bound

Mathematics Subject Classification ID

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

Related Items

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, Some efficiently solvable problems over integer partition polytopes, Karmarkar's linear programming algorithm and Newton's method, An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems, Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function, A unified approach to interior point algorithms for linear complementarity problems: A summary, A survey of search directions in interior point methods for linear programming, An \(O(n^ 3L)\) adaptive path following algorithm for a linear complementarity problem, Unified complexity analysis for Newton LP methods, Pure adaptive search in global optimization, On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Modified barrier functions (theory and methods), Semidefinite programming and arithmetic circuit evaluation, On affine scaling algorithms for nonconvex quadratic programming, On the convergence of the affine-scaling algorithm, Long steps in an \(O(n^ 3L)\) algorithm for linear programming, A polynomial method of approximate centers for linear programming, A globally and quadratically convergent affine scaling method for linear \(l_ 1\) problems, Exterior point algorithms for nearest points and convex quadratic programs, A scaling technique for finding the weighted analytic center of a polytope, An interior point algorithm of O\((\sqrt m| \ln\varepsilon |)\) iterations for \(C^ 1\)-convex programming, On the finite convergence of interior-point algorithms for linear programming, A build-up variant of the logarithmic barrier method for LP, On the computation of weighted analytic centers and dual ellipsoids with the projective algorithm, Convergence behavior of interior-point algorithms, Interior-point methods for convex programming, Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals, On partial updating in a potential reduction linear programming algorithm of Kojima, Mizuno, and Yoshise, An interior point method for solving semidefinite programs using cutting planes and weighted analytic centers, A new polynomial time method for a linear complementarity problem, The Kantorovich theorem and interior point methods, Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes, Global ellipsoidal approximations and homotopy methods for solving convex analytic programs, A continuation algorithm for a class of linear complementarity problems using an extrapolation technique, Near boundary behavior of primal-dual potential reduction algorithms for linear programming, Exploiting special structure in a primal-dual path-following algorithm, On well definedness of the central path, A polynomial projection algorithm for linear feasibility problems, Containing and shrinking ellipsoids in the path-following algorithm, Polynomial affine algorithms for linear programming, An interior point potential reduction method for constrained equations, A sensitivity analysis to assess the completion time deviation for multi-purpose machines facing demand uncertainty, A simple complexity proof for a polynomial-time linear programming algorithm, \(O(n^ 3)\) noniterative heuristic algorithm for linear programs with error-free implementation., An interior point method, based on rank-1 updates, for linear programming, Analytic centers and repelling inequalities, Interior-point methods, The Gaussian hare and the Laplacian tortoise: computability of squared-error versus absolute-error estimators. With comments by Ronald A. Thisted and M. R. Osborne and a rejoinder by the authors, A unified view of interior point methods for linear programming, Degeneracy in interior point methods for linear programming: A survey, The relation between the path of centers and Smale's regularization of the linear programming problem, Interior-point algorithms for global optimization, O(n\({}^ pL)\)-iteration and \(O(n^ 3L)\)-operation potential reduction algorithms for linear programming, On the complexity of approximating the maximal inscribed ellipsoid for a polytope, An \(O(n^ 3 L)\) primal-dual potential reduction algorithm for solving convex quadratic programs, Theoretical efficiency of a shifted-barrier-function algorithm for linear programming, Optimizing over three-dimensional subspaces in an interior-point method for linear programming, An interactive interior point algorithm for multiobjective linear programming problems, Finding an interior point in the optimal face of linear programs, Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming, A potential-reduction variant of Renegar's short-step path-following method for linear programming, An \(O(n^ 3L)\) potential reduction algorithm for linear programming, On the classical logarithmic barrier function method for a class of smooth convex programming problems, Deriving an unconstrained convex program for linear programming, Interior-point algorithm for quadratically constrained entropy minimization problems, On solution-containing ellipsoids in linear programming, A global Newton method. II: Analytic centers, Randomized interior point methods for sampling and optimization, 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

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1108927&oldid=13146395"