An Active-Set Algorithm for Nonlinear Programming Using Linear Programming and Equality Constrained Subproblems

Richard H. Byrd (richardcs.colorado.edu)
Nicholas I.M. Gould (n.gouldrl.ac.uk)
Jorge Nocedal (nocedalece.northwestern.edu)
Richard A. Waltz (rwaltzece.northwestern.edu)

Abstract: This paper describes an active-set algorithm for large-scale nonlinear programming based on the successive linear programming method proposed by Fletcher and Sainz de la Maza. The step computation is performed in two stages. In the first stage a linear program is solved to estimate the active set at the solution. The linear program is obtained by making a linear approximation to the l1 penalty function inside a trust region. In the second stage, an equality constrained quadratic program (EQP) is solved involving only those constraints that are active at the solution of the linear program. The EQP incorporates a trust-region constraint and is solved (inexactly) by means of a projected conjugate gradient method. Numerical experiments are presented illustrating the performance of the algorithm on the CUTEr test set.

Keywords: active-set method, trust-region method, linear programming, nonlinear programming, equality constrained quadratic programming, projected conjugate gradient method

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Optimization Software and Modeling Systems (Optimization Software Benchmark )

Citation: Report OTC 2002/4, Optimization Technology Center, Northwestern University, Evanston, Illinois, USA, September 2002

Download: [Postscript][PDF]

Entry Submitted: 11/06/2002
Entry Accepted: 11/06/2002
Entry Last Modified: 05/14/2003

Modify/Update this entry