AN INTERIOR-POINT ALGORITHM FOR P*(k)-LCPS BASED ON A NEW KERNEL FUNCTION WITH A DOUBLE BARRIER TERM

Abstract

In this paper, new search directions and proximity measures are proposed for P*(k)-linear complementarity problem. The new algorithm is based on a new class of kernel function which differs from the existing kernel functions in which it has a double barrier term. These functions constitute a combination of the classic kernel function and a barrier term. We derive
the complexity bounds for large and small-update methods respectively. We
show that the best result of iteration bounds for large-update methods can be achieved, namely

          O((1 + 2k) q√n(log√n)^(q+1/q) log(n/ε).

With a special choice of the parameter q, the iteration complexity becames                     O((1+2k)√n log(n) log(n/ε).
We test the efficiency and the validity of our algorithm by running some computational tests, then we compare our numerical results with results obtained by algorithms based on different kernel functions.