Analyzing infeasible nonlinear programs

Nonlinear optimizers often report infeasibility during the process of initial construction of a model, or alterations to an existing model. Because solvers are unable to decide feasibility of a nonlinear constraint set with perfect accuracy, there are numerous possible explanations: the physical model really is infeasible, there is an error in the nonlinear constraint set causing infeasibility, or the model is feasible but the initial point or solver parameters are poorly chosen. It is difficult to proceed to a diagnosis of the problem in a large NLP.This paper presents an algorithm providing automated assistance in analyzing infeasible NLPs. The deletion filtering algorithm isolates a Minimal Intractable Subsystem (MIS) of constraints, a minimal set of constraints which appears infeasible to the solver given a specified initial point and parameter settings. The MIS may be as small as a few constraints from among the very much larger set defining the original model, and helps to focus the examination, thereby speeding the diagnosis. A computer tool embodying the algorithm, LSGRG (MIS), is developed and applied to demonstration examples.