On the complexity of following the central path of linear programs by linear extrapolation. II

DOI10.1007/BF01582904zbMath0742.90056OpenAlexW2036887860MaRDI QIDQ1181914

Gy. Sonnevend, Gongyun Zhao, Josef Stoer

Publication date: 27 June 1992

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

Full work available at URL: https://doi.org/10.1007/bf01582904

zbMATH Keywords

Newton's methodinequality constraintscentral curvelogarithmic derivatives of the slack variablesweighted curvature

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (34)

Interior-point algorithms for semi-infinite programming ⋮ A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming ⋮ An analogue of the Klee-Walkup result for sonnevend's curvature of the central path ⋮ Representing the space of linear programs as the Grassmann manifold ⋮ A primal-dual interior point method whose running time depends only on the constraint matrix ⋮ The curvature integral and the complexity of linear complementarity problems ⋮ Log-Barrier Interior Point Methods Are Not Strongly Polynomial ⋮ A lower bound on the number of iterations of long-step primal-dual linear programming algorithms ⋮ An interior-point method for semi-infinite programming problems ⋮ Information geometry and interior-point algorithms in semidefinite programs and symmetric cone programs ⋮ Curvature integrals and iteration complexities in SDP and symmetric cone programs ⋮ Doubly autoparallel structure and curvature integrals. Applications to iteration complexity for solving convex programs ⋮ Asymptotic behavior of helmberg-kojima-Monteiro (HKM) paths in interior-point methods for monotone semidefinite linear complementarity problems: General theory ⋮ A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms ⋮ What Tropical Geometry Tells Us about the Complexity of Linear Programming ⋮ Central Path Curvature and Iteration-Complexity for Redundant Klee—Minty Cubes ⋮ Interior-point methods for convex programming ⋮ Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals ⋮ The central curve in linear programming ⋮ Improved complexity results on solving real-number linear feasibility problems ⋮ Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem ⋮ Large-step predictor-corrector interior point method for sufficient linear complementarity problems based on the algebraic equivalent transformation ⋮ Note on implementing the new sphere method for LP using matrix inversions sparingly ⋮ Comments on: Recent progress on the combinatorial diameter of polytopes and simplicial complexes ⋮ On the choice of parameters for power-series interior point algorithms in linear programming ⋮ Feasible Corrector-Predictor Interior-Point Algorithm for $P_{*} (\kappa)$-Linear Complementarity Problems Based on a New Search Direction ⋮ A continuous \(d\)-step conjecture for polytopes ⋮ Predictor-corrector interior-point algorithm for \(P_*(\kappa)\)-linear complementarity problems based on a new type of algebraic equivalent transformation technique ⋮ 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 ⋮ On the Central Path of Semidefinite Optimization: Degree and Worst-Case Convergence Rate ⋮ Iteration complexity of an interior-point algorithm for nonlinear p∗-complementarity problems ⋮ On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix ⋮ An interior point parameterized central path following algorithm for linearly constrained convex programming

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Global ellipsoidal approximations and homotopy methods for solving convex analytic programs
• Computational experience with a primal-dual interior point method for linear programming
• Sequential algorithms of optimal order global error for the uniform recovery of functions with monotone (r-1) derivatives
• An \(O(\sqrt n L)\) iteration potential reduction algorithm for linear complementarity problems
• Integrability of vector and multivector fields associated with interior point methods for linear programming
• A polynomial method of approximate centers for linear programming
• Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals
• An implementation of Karmarkar's algorithm for linear programming
• Decomposition and Nondifferentiable Optimization with the Projective Algorithm
• Algorithmic Enhancements to the Method of Centers for Linear Programming Problems

This page was built for publication: On the complexity of following the central path of linear programs by linear extrapolation. II