Exploring complexity of large update interior-point methods for P ∗ ( κ ) linear complementarity problem based on Kernel function

• Published in: Applied mathematics and computation 2009-01, Vol.207 (2), p.501-513
• Main Authors: Amini, Keyvan, Reza Peyghami, M.
• Format: Article
• Language: English
• Subjects: Calculus of variations and optimal control; Exact sciences and technology; Kernel function; Large updates method; Linear complementarity problem; Mathematical analysis; Mathematics; Numerical analysis; Numerical analysis. Scientific computation; Numerical methods in mathematical programming, optimization and calculus of variations; Numerical methods in optimization and calculus of variations; Polynomial complexity; Primal-dual interior-point method; Proximity function; Sciences and techniques of general use
• ISSN: 0096-3003; 1873-5649
• DOI: 10.1016/j.amc.2008.11.002

Interior-point methods not only are the most effective methods in practice but also have polynomial-time complexity. The large update interior-point methods perform in practice much better than the small update methods which have the best known theoretical complexity. In this paper, motivated by the complexity results for linear optimization based on kernel functions, we extend a generic primal-dual interior-point algorithm based on a new kernel function to solve P ∗ ( κ ) linear complementarity problems. By using some elegant and simple tools and having interior-point condition, we show that the large update primal-dual interior-point methods for solving P ∗ ( κ ) linear complementarity problems enjoys O q ( 1 + 2 κ ) n ( log n ) q + 1 q log n ε iteration bound which becomes O ( 1 + 2 κ ) n log n log ( log n ) log n ε with special choices of the parameter q. This bound is much better than the classical primal-dual interior-point methods based on logarithmic barrier function and recent kernel functions introduced by some authors in optimization field. Some computational results have been provided.