POLYNOMIAL PRIMAL-DUAL AFFINE SCALING ALGORITHMS IN SEMIDEFINITE PROGRAMMING

Authors
DEKLERK E ROOS C TERLAKY T
Citation
E. Deklerk et al., POLYNOMIAL PRIMAL-DUAL AFFINE SCALING ALGORITHMS IN SEMIDEFINITE PROGRAMMING, Journal of combinatorial optimization, 2(1), 1998, pp. 51-69
Citations number
20
Categorie Soggetti
Mathematics,"Computer Science Interdisciplinary Applications",Mathematics,"Computer Science Interdisciplinary Applications
Journal title
Journal of combinatorial optimization → ACNP
ISSN journal
13826905
Volume
2
Issue
1
Year of publication
1998
Pages
51 - 69
Database
ISI
SICI code
1382-6905(1998)2:1<51:PPASAI>2.0.ZU;2-V
Abstract
Two primal-dual affine scaling algorithms for linear programming are e xtended to semidefinite programming. The algorithms do not require (ne arly) centered starting solutions, and can be initiated with any prima l-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 0(tau(0)nL) iterations, wh ere tau(0) is a measure of centrality of the the starting solution, an d the latter a bound of 0(tau(0)nL(2)) iterations.