An active-constraint logic for nonlinear programming

The choice of active-constraint logic for screening inequalities has a major impact on the performance of gradient-projection method. It has been found that least-constrained strategies, which keep the number of constraints in the active set as small as possible, are computationally most efficient. However, these strategies are often prone to cycling of constraints between active and inactive status. This occurs mainly due to the violation of some of the constraints, taken as inactive, by the resulting step. This research develops methods for choosing an active set such that constraints in the active set satisfy the Kuhn-Tucker conditions and the resulting step does not violate the linear approximations to any of the constraints satisfied as equalities but considered inactive.

Some of the existing active-constraint logics, specifically the dual-violator rule, yield the desired active set when two constraints are satisfied as equalities. However, when three or more constraints are satisfied as equalities, none of the existing logics give the desired active set.

A number of general results, which help in the selection of the active set, have been developed in this research. An active-constraint logic has been developed for the case of three constraints. This logic gives the desired active-set. For the general case, when more than three constraints are satisfied as equalities, a separate active-set logic is suggested. This guarantees the nonviolation of the linear approximations to any of the constraints, taken as inactive, by the resulting step. The resulting active-set may not, however, satisfy the Kuhn-Tucker conditions.

The efficiency of the proposed logic was tested computationally using quadratic programming problems. Three existing active-set strategies were used for comparision. The proposed logic almost always performed as well or better than the best among the three existing active-set strategies.