Superlinearly Convergent Infeasible-Interior-Point Algorithm for Degenerate LCP

F. A. Potra and R. Sheng
Additional contact information
F. A. Potra: University of Iowa
R. Sheng: University of Iowa

Journal of Optimization Theory and Applications, 1998, vol. 97, issue 2, No 1, 249-269

Abstract: Abstract A large-step infeasible path-following method is proposed for solving general linear complementarity problems with sufficient matrices. If the problem has a solution, the algorithm is superlinearly convergent from any positive starting points, even for degenerate problems. The algorithm generates points in a large neighborhood of the central path. Each iteration requires only one matrix factorization and at most three (asymptotically only two) backsolves. It has been recently proved that any sufficient matrix is a P *(κ)-matrix for some κ≥0. The computational complexity of the algorithm depends on κ as well as on a feasibility measure of the starting point. If the starting point is feasible or close to being feasible, then the iteration complexity is $$O((1 + {\kappa)}\sqrt {nL})$$ . Otherwise, for arbitrary positive and large enough starting points, the iteration complexity is O((1 + κ)2 nL). We note that, while computational complexity depends on κ, the algorithm itself does not.

Keywords: Linear complementarity problems; sufficient matrices; P *-matrices; path-following algorithm; infeasible-interior-point algorithm; polynomiality; superlinear convergence (search for similar items in EconPapers)
Date: 1998
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://link.springer.com/10.1023/A:1022670415661 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:97:y:1998:i:2:d:10.1023_a:1022670415661

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1023/A:1022670415661

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().