The curvature integral and the complexity of linear complementarity problems

DOI10.1007/BF01585931zbMath0841.90118OpenAlexW1976529189MaRDI QIDQ1904662

Gongyun Zhao, Jishan Zhu

Publication date: 7 January 1996

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

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

zbMATH Keywords

linear complementarity probleminterior-point methodscurvature integralcentral trajectorypredictor-corrector-type algorithm

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) (90C33)

Related Items

Asymptotic behavior of helmberg-kojima-Monteiro (HKM) paths in interior-point methods for monotone semidefinite linear complementarity problems: General theory ⋮ Corrector-predictor methods for sufficient linear complementarity problems ⋮ Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem

Cites Work

• Unnamed Item
• A polynomial-time algorithm for a class of linear complementarity problems
• A unified approach to interior point algorithms for linear complementarity problems: A summary
• On the complexity of following the central path of linear programs by linear extrapolation. II
• 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
• Predictor-corrector method for linear complementarity problems with polynomial complexity and superlinear convergence
• A quadratically convergent \(O(\sqrt n\;L)\)-iteration algorithm for linear programming
• A path following algorithm for a class of convex programming problems
• On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming
• Power Series Variants of Karmarkar-Type Algorithms