The Symbolic Interior Point Method
This work addresses the problem of enabling descriptive clarity and generic solvers in optimization for modelers, representing an incremental advance by adapting existing methods to symbolic contexts.
The authors tackled the challenge of applying high-level modeling languages to numerical optimization by introducing a symbolic interior-point method that uses algebraic decision diagrams (ADDs) to handle complex dependencies efficiently. They demonstrated its flexibility on tasks like decision making and compressed sensing, scaling to millions of non-zero entries.
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.