THE PRIMAL-DUAL POTENTIAL REDUCTION ALGORITHM FOR POSITIVE SEMI-DEFINITE PROGRAMMING

• 来源期刊: 计算数学（英文版）
• 学科: 数学
• 关键词: Positive semi-definite programming Potential reduction algorithms Complex-ity.
• 年，卷（期）: 2003,（3）
• 页码范围: 339-346
• 页数: 8页
• 分类号: O1
• 语种: 英文

摘要

In this paper we introduce a primal-dual potential reduction algorithm for positivesemi-definite programming. Using the symetric preserving scalings for both primal anddual interior matrices, we can construct an algorithm which is very similar to the primal-dual potential reduction algorithm of Huang and Kortanek [6] for linear programming. Thecomplexity of the algorithm is either O(n log(X0 @ S0/ε) or O(√nlog(X0 @ S0/ε) dependson the value of ρ in the primal-dual potential function, where X0 and S0 is the initialinterior matrices of the positive semi-definite programming.