Unified Analysis of Kernel-Based Interior-Point Methods for P?(?)-Linear Complementarity Problems

Unified Analysis of Kernel-Based Interior-Point Methods for P?(?)-Linear Complementarity Problems

Lesaja, G.
Roos, C.

Electrical Engineering, Mathematics and Computer Science

Software Technology

2010-10-19

We present an interior-point method for the P?(?)-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?(?)-LCPs based on the entire class of eligible kernel functions.

linear complementarity problem
P?(?)-matrix
interior-point method
kernel functions
polynomial complexity

http://resolver.tudelft.nl/uuid:7ecaaaf5-0166-4310-ba04-c541716f15c5

https://doi.org/10.1137/090766735

Society for Industrial and Applied Mathematics

1052-6234

SIAM Journal on Optimization, 20 (6), 2010

Institutional Repository

journal article

(c) 2010 The Author(s)
Society for Industrial and Applied Mathematics