| 线性规划内点算法的若干收敛性问题 |
| |
| 引用本文： | 施妙根. 线性规划内点算法的若干收敛性问题[J]. 清华大学学报(自然科学版), 1988, 0(3) |
| |
| 作者姓名： | 施妙根 |
| |
| 作者单位： | 应用数学系 |
| |
| 摘 要： | 对于线性规划问题 ｍｉｎ｛ｃтｘ｜Ａｘ≥ｂ，ｘ≥０｝，印度学者 и．Ｋａｒｍａｒｋａｒ于 １９８４年发明 了一种新的内点算法，它的时间复杂性为Ｏ（ｎ３．５Ｌ２），其中ｎ为问题的变量个数，Ｌ为输 入中的二进制位数。其后又出现了多种变形方案，如原始型和对偶型内点算法等等。本 文主要讨论它们的收敛性问题。关于Ｋａｒｍａｒｋａｒ算法，证明了当原始线性规划问题无有 限最优解时算法也可以收敛。关于原始型和对偶型内点算法，给出了它们的基本性质以 及若干收敛性结果。
|
| 关 键 词： | 线性规划 Karmarkar算法 原始型内点算法 对偶型内点算法 |
Some Convergence Problems of Interior-point Algorithms for Linear Programming |
| |
| Shi Miaogen. Some Convergence Problems of Interior-point Algorithms for Linear Programming[J]. Journal of Tsinghua University(Science and Technology), 1988, 0(3) |
| |
| Authors: | Shi Miaogen |
| |
| Affiliation: | Department of Applied Mathematics |
| |
| Abstract: | |
| |
| Keywords: | linear programming Karmarkar's algorithm primal and dual interior-point algorithms |
| 本文献已被 CNKI 等数据库收录！ |
