Polynomial Primal-Dual Affine Scaling Algorithms in Semidefinite Programming

Two primal-dual affine scaling algorithms for linear programming are extended to semidefinite programming. The algorithms do not require (nearly) centered starting solutions, and can be initiated with any primal-dual feasible solution. The first algorithm is the Dikin-type affine scaling method of Jansen et al. (1993b) and the second the classical affine scaling method of Monteiro et al. (1990). The extension of the former has a worst-case complexity bound of O(₀nL) iterations, where ₀ is a measure of centrality of the the starting solution, and the latter a bound of O(₀nL²) iterations.