Please use this identifier to cite or link to this item:
http://dspace.mediu.edu.my:8181/xmlui/handle/1721.1/5185Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.creator | Freund, Robert M. | - |
| dc.date | 2004-05-28T19:27:01Z | - |
| dc.date | 2004-05-28T19:27:01Z | - |
| dc.date | 1989-04 | - |
| dc.date.accessioned | 2013-10-09T02:38:14Z | - |
| dc.date.available | 2013-10-09T02:38:14Z | - |
| dc.date.issued | 2013-10-09 | - |
| dc.identifier | http://hdl.handle.net/1721.1/5185 | - |
| dc.identifier.uri | http://koha.mediu.edu.my:8181/xmlui/handle/1721 | - |
| dc.description | This paper examines the theoretical efficiency of solving a standard-form linear program by solving a sequence of shifted-barrier problems of the form minimize cTx - n (xj + ehj) j.,1 x s.t. Ax = b , x + e h > , for a given and fixed shift vector h > 0, and for a sequence of values of > 0 that converges to zero. The resulting sequence of solutions to the shifted barrier problems will converge to a solution to the standard form linear program. The advantage of using the shiftedbarrier approach is that a starting feasible solution is unnecessary, and there is no need for a Phase I-Phase II approach to solving the linear program, either directly or through the addition of an artificial variable. Furthermore, the algorithm can be initiated with a "warm start," i.e., an initial guess of a primal solution x that need not be feasible. The number of iterations needed to solve the linear program to a desired level of accuracy will depend on a measure of how close the initial solution x is to being feasible. The number of iterations will also depend on the judicious choice of the shift vector h . If an approximate center of the dual feasible region is known, then h can be chosen so that the guaranteed fractional decrease in e at each iteration is (1 - 1/(6 i)) , which contributes a factor of 6 ii to the number of iterations needed to solve the problem. The paper also analyzes the complexity of computing an approximate center of the dual feasible region from a "warm start," i.e., an initial (possibly infeasible) guess ir of a solution to the center problem of the dual. Key Words: linear program, interior-point algorithm, center, barrier function, shifted-barrier function, Newton step. | - |
| dc.format | 1770411 bytes | - |
| dc.format | application/pdf | - |
| dc.language | en_US | - |
| dc.publisher | Massachusetts Institute of Technology, Operations Research Center | - |
| dc.relation | Operations Research Center Working Paper;OR 194-89 | - |
| dc.title | Theoretical Efficiency of A Shifted Barrier Function Algorithm for Linear Programming | - |
| dc.type | Working Paper | - |
| Appears in Collections: | MIT Items | |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.