Path-Following Interior Point Method With Improved Iteration Bounds For Monotone Linear Complementarity Problem

In this thesis, we present a path-following interior point method (IPM) algorithm to solve a monotone linear complementarity problem (LCP). A new eligible kernel function will be used to help improve the theoretical iteration bounds for the path-following IPM algorithm. IPM algorithms have two types of updates called large-step updates and small-step updates. Small-step updates have a better theoretical iteration bound than large-step updates, even though large-step updates perform better in practice than small-step updates. It is shown in this thesis, that using this new eligible kernel function will lead to the small-step and large-step updates to have the same theoretical iteration bound, matching the best know iteration bound. These results help close the ironic gap between theoretical complexity and practical use of path-following IPMs