Skip to main content
Article
A New Class of Polynomial Interior-Point Algorithms for P*(κ)-Linear Complementarity Problems
Pacific Journal of Optimization
  • Y. Q. Bai, Shanghai University
  • Goran Lesaja, Georgia Southern University
  • C. Roos, Delft University of Technology
Document Type
Article
Publication Date
1-1-2008
Disciplines
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+2K) q(p+1)n(p+q)/q(p+1) log n/E] for large-update methods and O [(1+2K) q2n 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.

Citation Information
Y. Q. Bai, Goran Lesaja and C. Roos. "A New Class of Polynomial Interior-Point Algorithms for P*(κ)-Linear Complementarity Problems" Pacific Journal of Optimization Vol. 4 Iss. 1 (2008) p. 19 - 41 ISSN: 1348-9151
Available at: http://works.bepress.com/goran_lesaja/36/