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

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. The authors review classical barrier-function methods for nonlinear programming based on applying a l...

Full description

Saved in:
Bibliographic Details
Published in:Mathematical programming 1986-06, Vol.36 (2), p.183-209
Main Authors: GILL, P. E, MURRAY, W, SAUNDERS, M. A, TOMLIN, J. A, WRIGHT, M. H
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
Mathematical programming
Operational research and scientific management
Operational research. Management science
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. The authors 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.
ISSN:0025-5610
1436-4646
DOI:10.1007/bf02592025