A primal-dual interior-point algorithm with arc-search for semidefinite programming

摘要

We propose a wide neighborhood primal-dual interior-point algorithm with arc-search for semidefinite programming. In every iteration, the algorithm constructs an ellipse and searches an epsilon-approximate solution of the problem along the ellipsoidal approximation of the central path. Assuming a strictly feasible starting point is available, we show that the algorithm has the iteration complexity bound O (n(3/4) log X-0.S-0/epsilon) for the Nesterov-Todd direction, which is similar to that of the corresponding algorithm for linear programming. The numerical results show that our algorithm is efficient and promising.