A second-order Mehrotra-type predictor-corrector algorithm with a new wide neighbourhood for semi-definite programming

摘要

In this paper, we present a new second-order Mehrotra-type predictor-corrector algorithm for semi-definite programming (SDP). The proposed algorithm is based on a new wide neighbourhood. We are particularly concerned with an important inequality. Based on the inequality, the convergence is shown for a specific class of search directions. In particular, the complexity bound is (O)(n~(1/2) log ε~(-1)) for the Nesterov-Todd search direction and (O)(n log ε~(-1)) for the Helmberg-Kojima-Monteiro search direction. The derived complexity bounds coincide with the currently best known theoretical complexity bounds obtained so far for SDP. We provide some preliminary numerical results as well.