# zbMATH — the first resource for mathematics

Polynomial convergence of a new family of primal-dual algorithms for semidefinite programming. (English) Zbl 0960.65072
This paper establishes the polynomial convergence of a new class of primal-dual interior-point path-following feasible algorithm for semidefinite programming whose search directions are obtained by applying Newton’s method to the symmetric central path equation $(PXP^T)^{1/2} (P^{-T}SP^{- 1})(PXP^T)^{1/2}- \mu I=0,$ where $$P$$ is a nonsingular matrix. Specifically it is shown that the short-step-path-following algorithm based on the Frobenius norm neighborhood and the semilong-step path-following algorithm based on the operator 2-norm neighborhood have $$O(\sqrt nL)$$ and $$O(nL)$$ iteration-complexity bounds, respectively. Some particular cases are minutely studied.

##### MSC:
 65K05 Numerical mathematical programming methods 90C22 Semidefinite programming 90C51 Interior-point methods
Full Text: