turkmath.org

Linear Complementarity Problems (LCP) is important class of problems closely related to many optimization problems. Thus, efficient algorithms for solving LCP are of the interest for theoretical and practical purposes. The Feasible Interior-Point Methods (IPM) based on the class of eligible kernel functions will be presented. This class is fairly general and includes the classical logarithmic function, the prototype self-regular function, and non-self-regular kernel functions as special cases. We will show that the method globally converges and iteration bounds to obtain epsilon-approximate solution matches 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. Next, we will consider generalizations of these methods to Linear Complementarity Problems over symmetric cones. 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.