Interior-Point Methods for Linear Complementarity Problems

A class of Linear Complementarity Problems (LCP) is an important class of problems closely related to many important and frequently used optimization problems. Thus, efficient algorithms for solving LCP are of the interest for theoretical and practical purposes. In the first part of the talk Feasible Interior-Point Methods (IPM) based on the class of eligible kernel functions will be presented. This class of kernel functions is fairly general and includes the classical logarithmic function, the prototype self-regular function, and non-self-regular kernel functions as special cases. It will be shown that the methods globally converge and iteration bounds to obtain epsilon-approximate solution match best known iteration bounds for these types of methods. In particular, one of the main achievements of the kernel-based IPMs is the improved complexity of long-step methods leading to the significant reduction of the theoretical complexity gap between long-step and short-step algorithms. In the second part of the talk generalizations of these methods to Linear Complementarity Problems over symmetric cones will be considered. A remarkable and surprising result has been shown recently: The algebraic structure of Euclidean Jordan Algebras and associated symmetric cones are connected to important optimization problems and can serve as a unifying frame to analyze IPMs for semi definite optimization problems, second order cone optimization problems, and classical optimization problems over nonnegative orthant. Using carefully tools of EJA and symmetric cones it is shown that generalizations of the kernel based IPMs for LCP over symmetric cones still possess the best known complexity achieved for the LCPs over nonnegative orthrant