Article ID: | iaor20043754 |
Country: | United Kingdom |
Volume: | 31 |
Issue: | 6 |
Start Page Number: | 941 |
End Page Number: | 962 |
Publication Date: | May 2004 |
Journal: | Computers and Operations Research |
Authors: | Kupferschmid Michael, Rugenstein Edgar K. |
The classical ellipsoid algorithm solves convex nonlinear programming problems having feasible sets of full dimension. Convergence is certain only for the convex case, but the algorithm often works in practice for nonconvex problems as well. Shah's algorithm modifies the classical method to permit the solution of nonlinear programs including equality constraints. This paper describes a robust restarting procedure for Shah's algorithm and investigates two active set strategies to improve computational efficiency. Experimental results are presented to show the new algorithm is effective, and usually faster than Shah's algorithm, for a wide variety of convex and nonconvex nonlinear programs with inequality and equality constraints. We also demonstrate that the algorithm can be used to solve systems of nonlinear equations and inequalities, including Karush–Kuhn–Tucker conditions.