Article ID: | iaor19911741 |
Country: | Netherlands |
Volume: | 45 |
Issue: | 3 |
Start Page Number: | 437 |
End Page Number: | 474 |
Publication Date: | Dec 1989 |
Journal: | Mathematical Programming |
Authors: | Gill Philip E., Murray Walter, Saunders Michael A., Wright Margaret H. |
A procedure is described for preventing cycling in active-set mehods for linearly constrained optimization, including the simplex method. The key ideas are a limited acceptance of infeasibilities in all variables, and maintenance of a ‘working’ feasibility tolerance that increases over a long sequence of iterations. The additional work per iteration is nominal, and ‘stalling’ cannot occur with exact arithmetic. The methods appear to be reliable, based on computationnuy3400al results for the first 53 linear programming problems in the