Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: A Quadratically-Convergent Algorithm for the Linear Programming Problem with Lower and Upper Bounds
Authors: Coleman, Thomas F.
Li, Yuying
Keywords: computer science
technical report
Issue Date: Apr-1990
Publisher: Cornell University
Abstract: We present a new algorithm to solve linear programming problems with finite lower and upper bounds. This algorithm generates an infinite sequence of points guaranteed to converge to the solution; the ultimate convergence rate is quadratic. The algorithm requires the solution of a linear least squares problem at each iteration - it is similar in this respect to recent interior point and "Karmarkar-like" methods. However, the algorithm does not require feasibility of the iterates; instead, monotonic decrease of an augmented linear $l_{1}$ function is maintained. A penalty parameter is not required. This method is particularly attractive for large-scale problems in that the number of iterations required to obtain high accuracy is relatively insensitive to problem size and is typically quite small. We provide results of numerical experiments.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
90-1119.pdf811.24 kBAdobe PDFView/Open
90-1119.ps223.74 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us