Polynomial Primal-dual Affine Scaling Algorithms in Semidefinite Programming

E. de Klerk, C. Roos, T. Terlaky

Two primal-dual 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, and the second the pure primal-dual affine scaling method of Monteiro et al. The worst-case iteration complexity bounds of the extended algorithms are the same as their linear programming counterparts.

Report 96-42, Faculty of Technical Mathematics and Informatics, Delft University of Technology, Delft, The Netherlands

Contact: e.deklerk@twi.tudelft.nl