Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. A Quadratically-Convergent Algorithm for the Linear Programming Problem with Lower and Upper Bounds

A Quadratically-Convergent Algorithm for the Linear Programming Problem with Lower and Upper Bounds

File(s)
90-1119.pdf (811.24 KB)
90-1119.ps (223.74 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6959
Collections
Computer Science Technical Reports
Author
Coleman, Thomas F.
Li, Yuying
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.

Date Issued
1990-04
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR90-1119
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance