Communications of the
Korean Mathematical Society CKMS

Finding an initial feasible solution on the central path is the main difficulty of feasible interior-point methods. Although, some algorithms have been suggested to remedy this difficulty, many practical implementations often do not use perfectly centered starting points. Therefore, it is worth to analyze the case that the starting point is not exactly on the central path. In this paper, we propose a weighted-path following interior-point algorithm for solving the Cartesian $P _*(\kappa)$-linear complementarity problems (LCPs) over symmetric cones. The convergence analysis of the algorithm is shown and it is proved that the algorithm terminates after at most $O\br{(1+4\kappa)\sqrt{r}\log\frac{\textbf{Tr}(x^0\diamond s^0)}{\varepsilon}}$ iterations.

Keywords: linear complementarity problems, the Cartesian property, path following algorithm, polynomial complexity

MSC numbers: 90C33, 90C51