Polynomial Convergence of a New Family of Primal-Dual Algorithms for Semidefinite Programming

Renato D.C. Monteiro and Takashi T. Tsuchiya

This paper establishes the polynomial convergence of a new class of (feasible) primal-dual interior-point path following algorithms for semidefinite programming (SDP) whose search directions are obtained by applying Newton method to the symmetric central path equation $$(P^T X P)^{1/2}(P^{-1} S P^{-T}) ( P^T X P)^{1/2} - \mu I =0,$$ where $P$ is a nonsingular matrix. Specifically, we show 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{n}L)$ and $O(nL)$ iteration-complexity bounds, respectively. When $P=I$, this yields the first polynomially convergent semilong-step algorithm based on a pure Newton direction. Restricting the scaling matrix $P$ at each iteration to a certain subset of nonsingular matrices, we are able to establish an $O(n^{3/2}L)$ iteration-complexity for the long-step path following method. The resulting subclass of search directions contains both the Nesterov-Todd direction and the Helmberg-Rendl-Vanderbei-Wolkowicz/Kojima-Shindoh-Hara/Monteiro direction.

Report Memorandum No. 627, The Institute of Statistical Mathematics, 4-6-7 Minami-Azabu, Minato-ku, Tokyo 106, JAPAN.

Contact: [email protected]

[DVI] [PS] [IP PAGE] [SEARCH AGAIN]