A Modification of Karmarkar's Linear Programming Algorithm

被引：180

作者：

Vanderbei, Robert J. ^{[1
]}

Meketon, Marc S. ^{[1
]}

Freedman, Barry A. ^{[1
]}

机构：

[1] AT&T Bell Labs, Holmdel, NJ 07733 USA

来源：

ALGORITHMICA | 1986年 / 1卷 / 1-4期

关键词：

Linear programming; Karmarkar's algorithm; Projected gradient methods; Least squares;

D O I：

10.1007/BF01840454

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We present a modification of Karmarkar's linear programming algorithm. Our algorithm uses a recentered projected gradient approach thereby obviating a priori knowledge of the optimal objective function value. Assuming primal and dual nondegeneracy, we prove that our algorithm converges. We present computational comparisons between our algorithm and the revised simplex method. For small, dense constraint matrices we saw little difference between the two methods.

引用

页码：395 / 407

页数：13