Article ID: | iaor20022534 |
Country: | Netherlands |
Volume: | 103 |
Issue: | 1 |
Start Page Number: | 49 |
End Page Number: | 70 |
Publication Date: | Mar 2001 |
Journal: | Annals of Operations Research |
Authors: | Kanzow Christian, Engelke Stephan |
We introduce a class of algorithms for the solution of linear programs. This class is motivated by some recent methods suggested for the solution of complementarity problems. It reformulates the optimality conditions of a linear program as a nonlinear system of equations and applies a Newton-type method to this system of equations. We investigate the global and local convergence properties and present some numerical results. The algorithms introduced here are somewhat related to the class of primal–dual interior-point methods. Although, at this stage of our research, the theoretical results and the numerical performance of our method are not as good as for interior-point methods, our approach seems to have some advantages which will also be discussed in detail.