The Symbolic Interior Point Method

Martin Mladenov, Vaishak Belle, Kristian Kersting

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Numerical optimization is arguably the most prominent computational framework in machine learning and AI. It can be seen as an assembly language for hard combinatorial problems ranging from classification and regression in learning, to computing optimal policies and equilibria in decision theory, to entropy minimization in information sciences. Unfortunately, specifying such problems in complex domains involving relations, objects and other logical dependencies is cumbersome at best, requiring considerable expert knowledge, and solvers require models to be painstakingly reduced to standard forms. To overcome this, we introduce a rich modeling framework for optimization problems that allows convenient codification of symbolic structure. Rather than reducing this symbolic structure to a sparse or dense matrix, we represent and exploit it directly using algebraic decision diagrams (ADDs). Combining efficient ADD-based matrix-vector algebra with a matrix-free interior-point method, we develop an engine that can fully leverage the structure of symbolic representations to solve convex linear and quadratic optimization problems. We demonstrate the flexibility of the resulting symbolic-numeric optimizer on decision making and compressed sensing tasks with millions of non-zero entries.
Original languageEnglish
Title of host publicationProceedings of The Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)
PublisherAAAI Press
Pages1199-1205
Number of pages7
Publication statusPublished - 12 Feb 2017
EventThirty-First AAAI Conference on Artificial Intelligence - San Francisco, United States
Duration: 4 Feb 20179 Feb 2017
https://www.aaai.org/Conferences/AAAI/aaai17.php

Publication series

Name
PublisherAAAI
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468

Conference

ConferenceThirty-First AAAI Conference on Artificial Intelligence
Abbreviated titleAAAI-17
Country/TerritoryUnited States
CitySan Francisco
Period4/02/179/02/17
Internet address

Fingerprint

Dive into the research topics of 'The Symbolic Interior Point Method'. Together they form a unique fingerprint.

Cite this