Superlinear convergence of a symmetric primal-dual path following algorithm
for semidefinite programming
Zhi-Quan Luo, Jos Sturm and Shuzhong Zhang
This paper establishes the superlinear convergence of
a symmetric primal-dual path following algorithm for
semidefinite programming under the assumptions that the semidefinite
program has a strictly complementary primal-dual optimal solution and
that the size of the central path neighborhood tends to zero.
The interior point algorithm considered here
closely resembles the Mizuno-Todd-Ye predictor-corrector method for linear
programming which is known to be quadratically convergent.
It is shown that when the iterates are well centered, the duality
gap is reduced superlinearly after each predictor step.
Indeed, if each predictor step is succeeded by $r$ consecutive
corrector steps then the predictor reduces
the duality gap superlinearly with order $\frac{2}{1+2^{-2r}}$.
The proof relies on a careful analysis of the central path for
semidefinite programming. It is shown that under the strict
complementarity assumption, the primal-dual
central path converges to the analytic center of the primal-dual
optimal solution set, and the distance from any point on the central path
to this analytic center is bounded by the duality gap.
Report 9607/A, Econometric Institute, Erasmus University, Rotterdam.