Unified Analysis of Kernel-Based Interior-Point Methods for $P_*(\kappa)$-Linear Complementarity Problems
Goran Lešaja, Cornelis Roos · SIAM Journal on Optimization · 2010
We present an interior-point method for the $P_*(\kappa)$-linear complementarity problem (LCP) that is based on barrier functions which are defined by a large class of univariate functions called eligible kernel functions. This class is fairly general and includes the classical logarithmic function and the self-regular functions, as well as many non-self-regular functions as special cases. We provide a unified analysis of the method and give a general scheme on how to calculate the iteration bounds for the entire class. We also calculate the iteration bounds of both long-step and short-step versions of the method for several specific eligible kernel functions. For some of them we match the best known iteration bounds for the long-step method, while for the short-step method the iteration bounds are of the same order of magnitude. As far as we know, this is the first paper that provides a unified approach and comprehensive treatment of interior-point methods for $P_*(\kappa)$-LCPs based on the entire class of eligible kernel functions. (The title of this article has been corrected.)