New Large-update primal-dual interior point algorithms based on kernel functions for LCPs

다국어 초록 (Multilingual Abstract)

In this paper we propose new large-update primal-dual interior point algorithms for P*(κ) linear complementarity problems(LCPs). New search directions and proximity measures are proposed based on a specific class of kernel functions, ψ(t) = (tp+1-l) / (p+1) + (t-q-1) / (q), q＞0, p ∈ [0, 1], which are the generalized form of the ones in [3] and [12]. It is the first to use this class of kernel functions in the complexity analysis of interior point method(IPM) for P*(κ) LCPs. We showed that if a strictly feasible starting point is available, then new large-update primal-dual interior point algorithms for P(κ) LCPs have the best known complexity O((1 + 2κ) √2n(log2n)log(n/ε) when p = 1 and q ＝ 1/2 (log 2n) - 1.