Loading…

Active set strategies in an ellipsoid algorithm for nonlinear programming

The classical ellipsoid algorithm solves convex nonlinear programming problems having feasible sets of full dimension. Convergence is certain only for the convex case (Math. Oper. Res. 10 (1985) 515), but the algorithm often works in practice for nonconvex problems as well (SIAM J. Control Optim. 23...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2004-05, Vol.31 (6), p.941-962
Main Authors: Rugenstein, Edgar K., Kupferschmid, Michael
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The classical ellipsoid algorithm solves convex nonlinear programming problems having feasible sets of full dimension. Convergence is certain only for the convex case (Math. Oper. Res. 10 (1985) 515), but the algorithm often works in practice for nonconvex problems as well (SIAM J. Control Optim. 23 (1985) 657). Shah's algorithm (Comput. Oper. Res. 20 (2001) 85) 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. The purpose of this paper is to describe an ellipsoid algorithm using two active set strategies, and to provide a careful experimental characterization of its performance on a significant set of general nonlinear programming test problems.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/S0305-0548(03)00045-5