| THE PRIMAL—DUAL POTENTIAL REDUCTION ALGORITHM FOR POSITIVE SEMI—DEFINITE PROGRAMMING |
| |
| 引用本文： | Si-ming Huang(Institute of Policy and Management,Academy of Mathematics and System Sciences,Chinese Academy of Sciences,Beijing 100080,China). THE PRIMAL—DUAL POTENTIAL REDUCTION ALGORITHM FOR POSITIVE SEMI—DEFINITE PROGRAMMING[J]. 计算数学(英文版), 2003, 21(3): 339-346 |
| |
| 作者姓名： | Si-ming Huang(Institute of Policy and Management Academy of Mathematics and System Sciences Chinese Academy of Sciences Beijing 100080 China) |
| |
| 作者单位： | Institute of Policy and Management，Academy of Mathematics and System Sciences，Chinese Academy of Sciences，Beijing 100080，China |
| |
| 基金项目： | This research was partially supported by a fund from Chinese Academy of Science,and a fund from the Personal Department of the State Council.It is also sponsored by scientific research foundation for returned overseas Chinese Scholars,State Education |
| |
| 摘 要： | In this paper we introduce a primal-dual potential reduction algorithm for positive semi-definite programming. Using the symetric preserving scalings for both primal and dual 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. The complexity of the algorithm is either O(nlog(X0 · S0/ε) or O(nlog(X0· S0/ε) depends on the value of ρ in the primal-dual potential function, where X0 and S0 is the initial interior matrices of the positive semi-definite programming.
|
| 关 键 词： | 原始对偶位势约化算法 正半定规划 对偶问题 内部矩阵 复杂性 梯度矩阵 搜索方向 齐次最小化问题 原始对偶投影 |
THE PRIMAL-DUAL POTENTIAL REDUCTION ALGORITHM FOR POSITIVE SEMI-DEFINITE PROGRAMMING |
| |
| Si-ming Huang. THE PRIMAL-DUAL POTENTIAL REDUCTION ALGORITHM FOR POSITIVE SEMI-DEFINITE PROGRAMMING[J]. Journal of Computational Mathematics, 2003, 21(3): 339-346 |
| |
| Authors: | Si-ming Huang |
| |
| Abstract: | In this paper we introduce a primal-dual potential reduction algorithm for positive semi-definite programming. Using the symetric preserving scalings for both primal and dual 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. The complexity of the algorithm is either $O(n log(X^0cdot S^0/epsilon))$ or $O(sqrt{n}log(X^0cdot S^0/epsilon))$ depends on the value of $rho$ in the primal-dual potential function, where $X^0$ and $S^0$ is the initial interior matrices of the positive semi-definite programming. |
| |
| Keywords: | Positive semi-definite programming Potential reduction algorithms Complexity. |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算数学(英文版)》浏览原始摘要信息 |
