Abstract:

Combing Newton method with predictor-corrector method, a new search direction is applied to a wide neighborhood infeasible-interior point algorithm for solving semidefinite programming． It is shown that this algorithm is a polynomial-time algorithm, which requires that all iterative points are in the neighborhood of the infeasible central path, but does not require the feasibility of the initial and iterative points．Under some mild assumptions, we show that the iteration-complexity bound is O(\sqrt{n}L)．Numerical analysis are also presented in this paper．Preliminary numerical results demonstrate the effectiveness of our method in both KM direction and NT direction．

Key words: semidefinite programming, wide neighborhood, infeasible interior-point algorithm, numerical analysis