Interior point algorithm for P∗P∗ nonlinear complementarity problems

In this paper, we propose a new large-update primal–dual interior point algorithm for P∗P∗ complementarity problems (CPs). Different from most interior point methods which are based on the logarithmic kernel function, the new method is based on a class of kernel functions ψ(t)=(tp+1−1)/(p+1)+(t−q−1)/qψ(t)=(tp+1−1)/(p+1)+(t−q−1)/q,p∈[0,1]p∈[0,1], q>0q>0. We show that if a strictly feasible starting point is available and the undertaken problem satisfies some conditions, then the new large-update primal–dual interior point algorithm for P∗P∗ CPs has O((1+2κ)nlognlog(nμ0/ε)) iteration complexity which is currently the best known result for such methods with p=1p=1 and q=(logn)/2−1q=(logn)/2−1.