Activity Analysis: The Qualitative Analysis of Stationary Points for Optimal Reasoning

Brian C. Williams and Jonathan Cagan
In Proceedings of AAAI-94.

We present a theory of a modeler's problem decomposition skills in the context of optimal reasoning --- the use of qualitative modeling to strategically guide numerical explorations of objective space. Our technique, called activity analysis, applies to the pervasive family of linear and non-linear, constrained optimization problems, and easily integrates with any existing numerical approach. Activity analysis draws from the power of two seemingly divergent perspectives -- the global conflict-based approaches of combinatorial satisficing 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.

[Paper (211k)]