Symmetric primal-dual path-following algorithms for semidefinite programming (Q1294556)

A framework for developing and analyzing primal-dual interior point algorithms for semidefinite programming problems is proposed. The \(v\)-space concept for linear programming, which was introduced by \textit{M. Kojima}, \textit{N. Megiddo}, \textit{T. Toshito} and \textit{A. Yoshise} [see ``A unified approach to interior point algorithms for linear complementarity problems'', Berlin (1991; Zbl 0766.90077)], is extended to semidefinite programming problems. This concept is based on the symmetric primal-dual transformation and the existence of primal-dual scaling in case of linear programming. It is shown that this property of linear programming can be inherited to some extent by semidefinite programming. Taking this fact into account, the following three primal-dual interior point algorithms are generalized from linear programming to semidefinite programming: 1) the short step primal-dual path following algorithm, 2) the predictor-corrector algorithm, and 3) the largest step algorithm. If \(\varepsilon\) is the required precision, an \(O(\sqrt{n} \log (1/\varepsilon))\) bound on the number of main iterations for these algorithms is derived.