On the Identification of Active Constraints II: The Nonconvex Case

In this paper the results of Burke and Moré [5] on the identification of active constraints are extended to the nonconvex constrained nonlinear programming problem. The approach is motivated by the geometric structure of a certain polyhedral convex “linearization” of the constraint region at each iteration. As in Burke and Moré [5] questions of constraint identification are couched in terms of the faces of these polyhedra. The main result employs a nondegeneracy condition due to Dunn [7] and the linear independence condition to obtain a characterization of those algorithms that identify the optimal active constraints in a finite number of iterations. The role of the linear independence condition is carefully examined and it is argued that it is required within the context of a first-order theory of constraint identification. In conclusion, the characterization theorem is applied to the Wilson–Han–Powell sequential quadratic programming algorithm [J. Optim. Theory Appl., 22 (1977), pp. 297–309], [Proceedings of the 1977 Dundee Conference on Numerical Analysis, Springer-Verlag, Berlin, 1977], and [A simplicial algorithm for concave programming, Ph.D. thesis, Graduate School of Business Administration, Harvard University, Boston, 1963] and Fletcher’s $QL$ algorithm [Practical Methods for Optimization, Vol. 2, John Wiley, New York, 1981], [Math. Programming Study, 17 (1982), pp. 67–76].