An O(nL) infeasible-interior-point algorithm for LCP with quadratic convergence

An O(nL) infeasible-interior-point algorithm for LCP with quadratic convergence

0.00 Avg rating0 Votes
Article ID: iaor19971557
Country: Netherlands
Volume: 62
Issue: 1
Start Page Number: 81
End Page Number: 102
Publication Date: Mar 1996
Journal: Annals of Operations Research
Authors:
Keywords: interior point methods
Abstract:

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 equ1 iteration complexity. If a certain measure of feasibility at the starting point is small enough, then the algorithm has equ2 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 equ3. A variant of the algorithm can be used to detect whether solutions with norm less than a given constant exist.

Reviews

Required fields are marked *. Your email address will not be published.