Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals

DOI10.1007/BF01182599zbMath0768.90056MaRDI QIDQ1205513

Gongyun Zhao, Josef Stoer

Publication date: 1 April 1993

Published in: Applied Mathematics and Optimization (Search for Journal in Brave)

zbMATH Keywords

predictor-corrector methodscurvature integral of the trajectoryNewton-type predictor stepprimal-dual path following interior point methods

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 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 (19)

An analogue of the Klee-Walkup result for sonnevend's curvature of the central path ⋮ The curvature integral and the complexity of linear complementarity problems ⋮ Log-Barrier Interior Point Methods Are Not Strongly Polynomial ⋮ 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 ⋮ A Primal-dual affine scaling algorithm with necessary centering as a safeguard ⋮ 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 ⋮ On the complexity of following the central path of linear programs by linear extrapolation. II ⋮ What Tropical Geometry Tells Us about the Complexity of Linear Programming ⋮ Central Path Curvature and Iteration-Complexity for Redundant Klee—Minty Cubes ⋮ The central curve in linear programming ⋮ Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem ⋮ 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 ⋮ Interior-point methods with decomposition for solving large-scale linear programs ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Global ellipsoidal approximations and homotopy methods for solving convex analytic programs
• A new polynomial-time algorithm for linear programming
• The degree of polynomial approximation and interpolation of analytic functions
• A polynomial-time algorithm, based on Newton's method, for linear programming
• On the complexity of following the central path of linear programs by linear extrapolation. II
• An implementation of Karmarkar's algorithm for linear programming
• The Nonlinear Geometry of Linear Programming. I Affine and Projective Scaling Trajectories
• Power Series Variants of Karmarkar-Type Algorithms

This page was built for publication: Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals