A modified Schur-complement method for handling dense columns in interior-point methods for linear programming

被引:29
作者
Andersen, KD
机构
[1] CORE, Universite Catholique de Louvain, B-1348 Louvain-la-Neuve
来源
ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE | 1996年 / 22卷 / 03期
关键词
Cholesky factorization; interior-point methods;
D O I
10.1145/232826.232937
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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.
引用
收藏
页码:348 / 356
页数:9
相关论文
共 16 条
[1]   AN IMPLEMENTATION OF KARMARKAR ALGORITHM FOR LINEAR-PROGRAMMING [J].
ADLER, I ;
RESENDE, MGC ;
VEIGA, G ;
KARMARKAR, N .
MATHEMATICAL PROGRAMMING, 1989, 44 (03) :297-335
[2]  
ANDERSEN E, 1996, APOS LP SOLVER
[3]  
ANDERSEN E, 1994, UNPUB COMBINING INTE
[4]   Presolving in linear programming [J].
Andersen, ED ;
Andersen, KD .
MATHEMATICAL PROGRAMMING, 1995, 71 (02) :221-245
[5]   An efficient Newton barrier method for minimizing a sum of Euclidean norms [J].
Andersen, KD .
SIAM JOURNAL ON OPTIMIZATION, 1996, 6 (01) :74-95
[6]  
Choi IC, 1990, ORSA J. Comput., V2, P304
[7]  
Gay D.M., 1985, MATH PROGRAMMING SOC, V13, P10
[8]   ON PROJECTED NEWTON BARRIER METHODS FOR LINEAR-PROGRAMMING AND AN EQUIVALENCE TO KARMARKAR PROJECTIVE METHOD [J].
GILL, PE ;
MURRAY, W ;
SAUNDERS, MA ;
TOMLIN, JA ;
WRIGHT, MH .
MATHEMATICAL PROGRAMMING, 1986, 36 (02) :183-209
[9]  
Golub GH, 1989, MATRIX COMPUTATIONS
[10]  
HEATH MT, 1982, SIAM J SCI STAT COMP, V3, P223, DOI 10.1137/0903014