Polynomial Primal-Dual Affine Scaling Algorithms in Semidefinite Programming

摘要

Two primal-dual affine scale algorithms for linear programming are extended tosemidefinite 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. (8) and the second the pure affine scaling method of Monteiro et el al. (12). The extension of the former has a worst-case complexity bound of O(tau sub zero nL) iterations, where T(sub O) is a measure of centrality of the starting solution, and the latter a bound of O(tau sub zero nL squared) iterations. (Copyright (c) 1996 by Faculty of Technical Mathematics and Informatics, Delft.)