## Abstract

We present a polynomial interior-point algorithm for * P*(K) * Linear Complementarity Problem (LCP) based on a class of parametric kernel functions, with parameters * p * ∈ [0, 1] and * q * ≥ 1. The same class of kernel function was considered earlier for Linear Optimization (LO) by Bai et al. in [7]. This class is fairly general and includes the classical logarithmic function, the prototype sellf-regular function, and non-self-regular kernel functions as special cases. The iteration bounds obtained in this paper are * O * [(1+2 * K * ) * q * ( * p * +1) * n * ^{ ( p + q )/ q ( p +1) } log * n/E * ] for large-update methods and * O * [(1+2 * K * ) * q * ^{ 2 } ** √ ** * n * log n/E] for small-update methods. These bounds match the best known existing iteration bounds. As far as we know this is the first result on interior-point methods for * P*(K) * * * -LCPs based on this class of kernel functions. * * * *

Original language | American English |
---|---|

Pages (from-to) | 19-41 |

Number of pages | 23 |

Journal | Pacific Journal of Optimization |

Volume | 4 |

Issue number | 1 |

State | Published - Jan 1 2008 |

## Keywords

- Interior-point methods
- Iteration bounds
- Kernel function
- Large- and small-update methods
- P*(K) horizontal linear complementarity problem
- Interior-point method
- Linear complementarity problem
- P(κ) matrix
- Polynomial complexity

## DC Disciplines

- Education
- Mathematics

## Fingerprint

Dive into the research topics of 'A New Class of Polynomial Interior-Point Algorithms for*P**(κ)-Linear Complementarity Problems'. Together they form a unique fingerprint.