A modified Schur-complement method for handling dense columns in interior-point methods for linear programming
A modified Schur-complement method for handling dense columns in interior-point methods for linear programming
复制标题
一种改进的 Schur 补法，用于处理线性规划内点法中的密集列
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Knud D. Andersen
中科院分区：
文献类型：
--
作者：
Knud D. Andersen
线性规划的邻域点法的主要计算工作是求解最小二乘问题。通常使用正规方程，但如果LP约束矩阵包含近似稠密列，则正规方程矩阵将是近似稠密的。假设约束矩阵的非稠密部分是满秩的，舒尔补可以用来处理稠密列。在这篇文章中，我们提出了一个修改的舒尔补方法，放松这一假设。令人鼓舞的数值结果。
The main computational work in interior-point methods for linear programming (LP) is to solve a least-squares problem. The normal equations are often used, but if the LP constraint matrix contains a nearly dense column the normal-equations matrix will be nearly dense. Assuming that the nondense part of the constraint matrix is of full rank, the Schur complement can be used to handle dense columns. In this article we propose a modified Schur-complement method that relaxes this assumption. Encouraging numerical results are presented.