An O(nL) infeasible-interior-point algorithm for LCP with quadratic convergence. (English)
In: Annals of Operations Research, Jg. 62 (1996), Heft 1-4, S. 81-102
Online
academicJournal
Zugriff:
The Mizuno-Todd-Ye predictor-corrector algorithm for linear programming is extended for solving monotone linear complementarity problems from infeasible starting points. The proposed algorithm requires two matrix factorizations and at most three backsolves per iteration. Its computational complexity depends on the quality of the starting point. If the starting points are large enough, then the algorithm has 0(nL) iteration complexity. If a certain measure of feasibility at the starting point is small enough, then the algorithm has O(√nL) iteration complexity. At each iteration, both "feasibility" and "optimality" are reduced exactly at the same rate. The algorithm is quadratically convergent for problems having a strictly complementary solution, and therefore its asymptotic efficiency index is √2. A variant of the algorithm can be used to detect whether solutions with norm less than a given constant exist. [ABSTRACT FROM AUTHOR]
Copyright of Annals of Operations Research is the property of Springer Nature and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Titel: |
An O(nL) infeasible-interior-point algorithm for LCP with quadratic convergence. (English)
|
---|---|
Autor/in / Beteiligte Person: | Potra, Florian A. |
Link: | |
Zeitschrift: | Annals of Operations Research, Jg. 62 (1996), Heft 1-4, S. 81-102 |
Veröffentlichung: | 1996 |
Medientyp: | academicJournal |
ISSN: | 0254-5330 (print) |
DOI: | 10.1007/BF02206812 |
Schlagwort: |
|
Sonstiges: |
|