Infeasible interior point methods for sufficient linear complementarity problems
Loading...
Links to Files
Permanent Link
Author/Creator
Author/Creator ORCID
Date
2009-01-01
Type of Work
Department
Mathematics and Statistics
Program
Mathematics, Applied
Citation of Original Publication
Rights
This item may be protected under Title 17 of the U.S. Copyright Law. It is made available by UMBC for non-commercial research and education. For permission to publish or reproduce, please see http://aok.lib.umbc.edu/specoll/repro.php or contact Special Collections at speccoll(at)umbc.edu.
Access limited to the UMBC community. Item may possibly be obtained via Interlibrary Loan through a local library, pending author/copyright holder's permission.
Access limited to the UMBC community. Item may possibly be obtained via Interlibrary Loan through a local library, pending author/copyright holder's permission.
Abstract
In the first part of the thesis we focus on algorithms acting in the small neighborhood of the central path. We present a new first order corrector-predictor method for solving sufficient linear complementarity problems for which a sufficiently centered feasible starting point is available. In contrast with its predictor-corrector counterpart proposed by Miao, the method does not depend on the handicap of the problem and our error estimates are sightly better. The algorithm has the same iteration complexity as Miao's method and it is quadratically convergent for problems having a strictly complementary solution. We also present an infeasible high order corrector-predictor method that is superlinearly convergent even in the absence of strict complementarity. The algorithm is globally convergent for general positive starting points and has the best known complexity. We end the first part of the thesis with a high order predictor-corrector algorithm which is better than Miao's generalization of the MTY, in the sense that if we start with a small neighborhood with the radius greater than 0.65, then the radius of the second neighborhood, in which the predicted iterate could lie, is greater than Miao's one. In the second part, two new high-order predictor-corrector and corrector-predictor methods are proposed for solving sufficient linear complementarity problems (LCP) with an infeasible starting point. Both algorithms are globally convergent for general positive starting points. These methods generate a sequence of iterates in a wide symmetric neighborhood of the central path. Both algorithms converge superlinearly to zero even for degenerate problems and have the best known iteration complexity for this type of neighborhoods. The predictor-corrector algorithm depends explicitly on the handicap of the LCP, but we also present a variant of it which does not depend on the handicap, while the corrector-predictor algorithm is independent of the handicap of the LCP.