Interior point method (IPM) defines a search direction at each interior point of a region. These search directions form a direction field which in turn gives rise to a system of ordinary differential equations (ODEs). The solutions of the system of ODEs can be viewed as underlying paths in the interior of the region. In [31], these off-central paths are shown to be well-defined analytic curves and any of their accumulation points is a solution to a given monotone semidefinite linear complementarity problem (SDLCP). The study of these paths provides a way to understand how iterates generated by an interior point algorithm behave. In this paper, we give a weak sufficient condition using these off-central paths that guarantees superlinear convergence of a predictor-corrector path-following interior point algorithm for SDLCP using the HKM direction. This sufficient condition is implied by a currently known sufficient condition for superlinear convergence. Using this sufficient condition, we show that for any linear semi-definite feasibility problem, superlinear convergence using the interior point algorithm, with the HKM direction, can be achieved, for a suitable starting point. We work under the assumption of strict complementarity.
Citation
Submitted.