A new O(nL)-iteration predictor–corrector algorithm with wide neighborhood for semidefinite programming

摘要

In this paper, we extend the Ai–Zhang predictor–corrector method to the class of semidefinite programming. First, we define a new wide neighborhood N(τ,β). Another key ingredient of our method is that we treat the classical Newton direction as the sum of two other directions, corresponding to respectively the negative part and the positive part of the right-hand-side. We prove that, besides the predictor steps, each corrector step also reduces the duality gap by a rate of 1−1O(n). Then the method enjoys the low iteration bound of O(nL), which is better than that of usual wide neighborhood algorithm O(nL), where n is the dimension of the problem and L=(X0)T•S0ϵ with ϵ the required precision and (X0,y0,S0) the initial interior solution.