Using Activity Analysis to Identify Relevant Constraints in Optimal Reasoning Problems

Brian C. Williams and Jonathan Cagan
In Proceedings of the AAAI 96 Spring Symposium on Computational Issues in Learning Models of Dynamical Systems.

Together, discrete satisfying search and adaptvie optimizing search are at the foundation of most computational disciplines. A core abstraction mechanism used to focus a wide variety of satisfying search problems is the summarization of minimal inconsistencies. These include Nogoods, used in dependency-directed search and Conflicts, used in model-based diagnosis. This paper explores two questions: First, does there exist an analogously powerful abstraction mechanism for focusing continuous optimizing search? Second, can the seemingly disparate search strategies of satisfying and optimizing search be unified? We answer in the affirmative, introducing a qualitative abstraction, called {\em QKKT}, and a corresponding search technique called {\em activity analysis}, that applies to the pervasive family of linear and non-linear, constrained optimization problems. Activity analysis draws from the power of two seemingly divergent methods -- the global conflict-based approaches of combinatorial satisfying search, and the local gradient-based approaches of continuous optimization -- combined with the underlying insights of engineering monotonicity analysis. The result is an approach that strategically cuts away subspaces that it can quickly rule out as suboptimal, and then guides the numerical methods to the remaining subspaces. Activity analysis represents an important step towards the unification of two powerful yet disjoint search disciplines.

[Paper (???k)]