Active set strategies and an ellipsoid algorithm for general nonlinear programming problems

The classical ellipsoid algorithm solves convex nonlinear programming problems having feasible sets of full dimension. While a proof of convergence is only available for the convex case, the ellipsoid 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. In this thesis I develop a robust restarting procedure for Shah's algorithm and investigate two active set strategies to improve computational efficiency. The first strategy ignores inequality constraints that will be slack at optimality; the second treats active inequalities as equalities. Experimental results are presented to show that the new algorithm is effective, and often faster than Shah's algorithm, for a wide variety of convex and nonconvex nonlinear programs with inequality and equality constraints, and can also be used to solve systems of nonlinear equations and inequalities. Constraint classifications determined by the active set strategies are shown to provide insights that can be useful in refining the formulation of a nonlinear program.