A new wide-neighborhood interior point algorithms for LCP. (English) Zbl 1229.90228
Summary: This paper establishes the polynomial convergence of a new class of path-following methods for linear complementarity problems (LCP). Namely, we show that the semilong-step path-following methods based on the \(L^-_\infty \) seminorm neighborhood have the iteration-complexity bounds of \(O(n)\).
MSC:
90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
65G20 | Algorithms with automatic result verification |
65G50 | Roundoff error |