A class of polynomial interior point algorithms for the Cartesian P-matrix linear complementarity problem over symmetric cones (Q415402)

The aim of the authors is to extend the interior point algorithms for linear optimization and sufficient linear complementarity problems based on the kernel functions to the Cartesian P-matrix linear complementarity problem over symmetric cones. The difficulty of the extension is that a symmetric cone is nonpolyhedral. In that purpose, the authors introduced a new class of polynomial interior point algorithms based on a parametric kernel function which is fairly general and covers a wide range of kernel functions, including the classical logarithmic kernel function, the prototype self-regular functions and also non-self-regular functions. This parametric kernel function determines both search directions and the proximity measure between the iterates and the central path. The Nesterov and Todd scaling scheme is used to get the symmetrization of the search directions. Finally, by using Euclidean Jordan algebras, the authors derive the iteration bounds that match the currently best known iteration bounds for large and small update methods, which reduce the gap between the practical behavior and the theoretical iteration bounds.