On projected newton barrier methods for linear programming and an equivalence to Karmarkar's projective method

Philip E. Gill; Walter Murray; Michael A. Saunders; J. A. Tomlin; Margaret H. Wright

doi:10.1007/BF02592025

On projected newton barrier methods for linear programming and an equivalence to Karmarkar's projective method

Philip E. Gill, Walter Murray, Michael A. Saunders, J. A. Tomlin, Margaret H. Wright

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Interest in linear programming has been intensified recently by 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.

Original language	English (US)
Pages (from-to)	183-209
Number of pages	27
Journal	Mathematical Programming
Volume	36
Issue number	2
DOIs	https://doi.org/10.1007/BF02592025
State	Published - Jun 1986

Keywords

Karmarkar's method
Linear programming
barrier methods

ASJC Scopus subject areas

Software
General Mathematics

Access to Document

10.1007/BF02592025

Cite this

@article{c1b9331dc8784c3996d4f75dcb88a51f,

title = "On projected newton barrier methods for linear programming and an equivalence to Karmarkar's projective method",

abstract = "Interest in linear programming has been intensified recently by 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.",

keywords = "Karmarkar's method, Linear programming, barrier methods",

author = "Gill, {Philip E.} and Walter Murray and Saunders, {Michael A.} and Tomlin, {J. A.} and Wright, {Margaret H.}",

year = "1986",

month = jun,

doi = "10.1007/BF02592025",

language = "English (US)",

volume = "36",

pages = "183--209",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "2",

}

TY - JOUR

T1 - On projected newton barrier methods for linear programming and an equivalence to Karmarkar's projective method

AU - Gill, Philip E.

AU - Murray, Walter

AU - Saunders, Michael A.

AU - Tomlin, J. A.

AU - Wright, Margaret H.

PY - 1986/6

Y1 - 1986/6

N2 - Interest in linear programming has been intensified recently by 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.

AB - Interest in linear programming has been intensified recently by 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.

KW - Karmarkar's method

KW - Linear programming

KW - barrier methods

UR - http://www.scopus.com/inward/record.url?scp=0022808235&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022808235&partnerID=8YFLogxK

U2 - 10.1007/BF02592025

DO - 10.1007/BF02592025

M3 - Article

AN - SCOPUS:0022808235

SN - 0025-5610

VL - 36

SP - 183

EP - 209

JO - Mathematical Programming

JF - Mathematical Programming

IS - 2

ER -

On projected newton barrier methods for linear programming and an equivalence to Karmarkar's projective method

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this