Theoretical Efficiency of A Shifted Barrier Function Algorithm for Linear Programming
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 t...
| Main Author: | |
|---|---|
| Format: | Working Paper |
| Language: | en_US |
| Published: |
Massachusetts Institute of Technology, Operations Research Center
2004
|
| Online Access: | http://hdl.handle.net/1721.1/5185 |
| _version_ | 1811078877497262080 |
|---|---|
| author | Freund, Robert M. |
| author_facet | Freund, Robert M. |
| author_sort | Freund, Robert M. |
| collection | MIT |
| 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. |
| first_indexed | 2024-09-23T11:06:44Z |
| format | Working Paper |
| id | mit-1721.1/5185 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:06:44Z |
| publishDate | 2004 |
| publisher | Massachusetts Institute of Technology, Operations Research Center |
| record_format | dspace |
| spelling | mit-1721.1/51852019-04-12T13:40:44Z Theoretical Efficiency of A Shifted Barrier Function Algorithm for Linear Programming Freund, Robert M. 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. 2004-05-28T19:27:01Z 2004-05-28T19:27:01Z 1989-04 Working Paper http://hdl.handle.net/1721.1/5185 en_US Operations Research Center Working Paper;OR 194-89 1770411 bytes application/pdf application/pdf Massachusetts Institute of Technology, Operations Research Center |
| spellingShingle | Freund, Robert M. Theoretical Efficiency of A Shifted Barrier Function Algorithm for Linear Programming |
| title | Theoretical Efficiency of A Shifted Barrier Function Algorithm for Linear Programming |
| title_full | Theoretical Efficiency of A Shifted Barrier Function Algorithm for Linear Programming |
| title_fullStr | Theoretical Efficiency of A Shifted Barrier Function Algorithm for Linear Programming |
| title_full_unstemmed | Theoretical Efficiency of A Shifted Barrier Function Algorithm for Linear Programming |
| title_short | Theoretical Efficiency of A Shifted Barrier Function Algorithm for Linear Programming |
| title_sort | theoretical efficiency of a shifted barrier function algorithm for linear programming |
| url | http://hdl.handle.net/1721.1/5185 |
| work_keys_str_mv | AT freundrobertm theoreticalefficiencyofashiftedbarrierfunctionalgorithmforlinearprogramming |