مشخصات پژوهش

This paper presents a new primal-dual interior-point predictor-corrector algorithm based on the wide neighborhood for semidefinite optimization (SDO). Per the idea of the neighborhood used, we decompose Newton’s directions into two separate directions corresponding to the positive and negative parts of the right-hand side of the centrality equation. The predictor step uses the search directions of the negative part, while the use of a new corrector direction corresponding to the positive part also reduces the duality gap in the corrector step. We prove that the new algorithm has an iteration bound of O(√n log Tr(X0S0) ε ), which matches the currently best-known iteration bound for interior-point methods. Finally, numerical results are presented that show the effectiveness and competitiveness of the proposed algorithm.