ON PROJECTED NEWTON BARRIER METHODS FOR LINEAR-PROGRAMMING AND AN EQUIVALENCE TO KARMARKAR PROJECTIVE METHOD

被引：186

作者：

GILL, PE ^{[1
]}

MURRAY, W ^{[1
]}

SAUNDERS, MA ^{[1
]}

TOMLIN, JA ^{[1
]}

WRIGHT, MH ^{[1
]}

机构：

[1] KETRON INC,MT VIEW,CA 94040

来源：

MATHEMATICAL PROGRAMMING | 1986年 / 36卷 / 02期

关键词：

COMPUTER PROGRAMMING - Algorithms;

D O I：

10.1007/BF02592025

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Interest in linear programming has been intensified recently by N. Karmarkar's publication in 1984 of an algorithm that is claimed to be much faster than the simplex method for practical problems. We review classical barrier-function methods for nonlinear programming based on applying a logarithmic transformation to inequality constraints. For the special case of linear programming, the transformed problem can be solved by a 'projected Newton barrier' method. This method is shown to be equivalent to Karmarkar's projective method for a particular choice of the barrier parameter. We then present details of a specific barrier algorithm and its practical implementation. Numerical results are given for several non-trivial test problems, and the implications for future developments in linear programming are discussed.

引用

页码：183 / 209

页数：27

共 51 条

[1]

AFiacco V, 1979, OPERATIONS RES SUPPO, P377

[2]

[Anonymous], 1953, J SOC IND APPL MATH

[3] EFFICIENT SOLUTION OF LARGE-SCALE LINEAR-PROGRAMMING PROBLEMS - SOME ALGORITHMIC TECHNIQUES AND COMPUTATIONAL RESULTS [J].