Abstract:

Interior-Point Methods (IPMs) not only are the most effective methods in
practice but also have polynomial-time complexity. Many researchers have proposed
IPMs for Linear Optimization (LO) and achieved plentiful results. In many cases
these methods were extendable for LO to Linear Complementarity Problems (LCPs)
successfully. In this paper, motivated by the complexity results for linear optimization
based on the study of H. Mansouri et al. (Mansouri and Zangiabadi in J. Optim.
62(2):285–297, 2013), we extend their idea for LO to LCP. The proposed algorithm
requires two types of full-Newton steps are called, feasibility steps and (ordinary)
centering steps, respectively. At each iteration both feasibility and optimality are reduced
exactly at the same rate. In each iteration of the algorithm we use the largest
possible barrier parameter value θ which lies between the two values 1
17n and 1
13n , this
makes the algorithm faster convergent for problems having a strictly complementarity
solution.