Publication
The Symbolic Interior Point Method
Martin Mladenov; Vaishak Belle; Kristian Kersting
In: Satinder Singh; Shaul Markovitch (Hrsg.). Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence. AAAI Conference on Artificial Intelligence (AAAI-2017), February 4-9, San Francisco, California, USA, Pages 1199-1205, AAAI Press, 2017.
Abstract
A recent trend in probabilistic inference emphasizes the codification of models in a formal syntax, with suitable high-level features such as individuals, relations, and connectives, enabling descriptive clarity, succinctness and circumventing the need for the modeler to engineer a custom solver. Unfortunately, bringing these linguistic and pragmatic benefits to numerical optimization has proven surprisingly challenging. In this paper, we turn to these challenges: we introduce a rich modeling language, for which an interior-point method computes approximate solutions in a generic way. While logical features easily complicates the underlying model, often yielding intricate dependencies, we exploit and cache local structure using algebraic decision diagrams (ADDs). Indeed, standard matrix-vector algebra is efficiently realizable in ADDs, but we argue and show that well-known optimization methods are not ideal for ADDs. Our engine, therefore, invokes a sophisticated matrix-free approach. We demonstrate the flexibility of the resulting symbolic-numeric optimizer on decision making and compressed sensing tasks with millions of non-zero entries.