Polynomial primal-dual affine scaling algorithms in semidefinite programming

被引：4

作者：

De Klerk, E ^{[1
]}

Roos, C ^{[1
]}

Terlaky, T ^{[1
]}

机构：

[1] Delft Univ Technol, Fac Tech Math & Informat, NL-2600 GA Delft, Netherlands

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 1998年 / 2卷 / 01期

关键词：

interior-point method; primal-dual method; semidefinite programming; affine scaling; Dikin steps;

D O I：

10.1023/A:1009791827917

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

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 0(tau(0)nL) iterations, where tau(0) is a measure of centrality of the the starting solution, and the latter a bound of 0(tau(0)nL(2)) iterations.

引用

页码：51 / 69

页数：19