On the Relationship Between the Curvature Integral and the Complexity of Path-Following Methods in Linear Programming

DOI10.1137/0806005zbMath0846.90074OpenAlexW2025853232MaRDI QIDQ4877506

Gongyun Zhao

Publication date: 13 May 1996

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0806005

zbMATH Keywords

interior point methodcurvature integralbounds of derivativescomplexity of primal-dual path-following methods

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)

Related Items (4)

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 ⋮ Uniform bounds on the limiting and marginal derivatives of the analytic center solution over a set of normalized weights ⋮ Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem

This page was built for publication: On the Relationship Between the Curvature Integral and the Complexity of Path-Following Methods in Linear Programming