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.

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