An Inexact Non-interior Continuation Algorithm For The P₀LCP

In the middle of the 90s of twentith century, non-interior continuation algorithm received extensive attention of international optimization field. From then on, non-interior continuation algorithm developed so fast that could resolve many kinds of optimization problems. In the non-interior continuation algorithm, solving Newton equation is its critical step and also brings a heavy workload. In the existing papers, they all solve the equation exactly, so a large computation workload is produced, especially for the problems with large sparse matrixes. At the same time, using inexact Newton method to solve the equation has been developed quickly. This method does not solve equations exactly. In each iteration, it adds a perturbation to the right side of Newton equation to reduce the computation workload.In this paper, we propose a new inexact non-interior continuation algorithm for the linear complementarity problem. This new algorithm combines inexact Newton method and non-interior continuation algorithm, using inexact Newton method to solve the equation. And then, we verify that this new algorithm is well defined and it has global linear convergence and local quadratic convergence with proper assumptions. Theoretically this new algorithm is more efficient than non-interior continuation algorithm, and has a better result in the numerical tests, especially for linear complementarity problems with large sparse matrixes. P0...