Session: Recent advances in mixed-integer programming
Chair: Linchuan Wei
Cluster: Interplay Between Continuous and Discrete Optimization
Talk 1: Solving convex optimization problems with structured sparsity under indicator conditions
Speaker: Tongtong Chen
Abstract: We study convex optimization problems where disjoint blocks of variables are controlled by binary indicator variables, which themselves are subject to additional conditions such as cardinality constraints. Several classes of important examples can be formulated in such a way that both the objective and the constraints are separable convex quadratics, including the cardinality-constrained portfolio optimization problem. We introduce a new metric for sparsity, namely, the treewidth of the intersection graph for the transpose of our constraint matrix. We provide complexity results and a family of polynomial-time approximation algorithms for those types of problems.
Talk 2: Integer Programming for Learning Directed Acyclic Graphs from Non-identifiable Gaussian Models
Speaker: Tong Xu
Abstract: We study the problem of learning directed acyclic graphs from continuous observational data, generated according to a linear Gaussian structural equation model. State-of-the-art structure learning methods for this setting have at least one of the following shortcomings: i) they cannot provide optimality guarantees and can suffer from learning sub-optimal models; ii) they rely on the stringent assumption that the noise is homoscedastic, and hence the underlying model is fully identifiable. We overcome these shortcomings and develop a computationally efficient mixed-integer programming framework for learning medium-sized problems that accounts for arbitrary heteroscedastic noise. We present an early stopping criterion under which we can terminate the branch-and-bound procedure to achieve an asymptotically optimal solution and establish the consistency of this approximate solution. In addition, we show via numerical experiments that our method outperforms state-of-the-art algorithms and is robust to noise heteroscedasticity, whereas the performance of some competing methods deteriorates under strong violations of the identifiability assumption. The software implementation of our method is available as the Python package \emph{micodag}.
Talk 3: Disjunctive Sum of Squares
Speaker: Yixuan Hua
Abstract: We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach where nonnegativity is certified by a single algebraic identity, the disjunctive sum of squares approach certifies nonnegativity with multiple algebraic identities. Our main result is a disjunctive Positivstellensatz proving that we can keep the degree of each algebraic identity as low as the degree of the polynomial whose nonnegativity is in question. Based on this result, we construct a semidefinite programming based converging hierarchy of lower bounds for the problem of minimizing a polynomial over a compact basic semialgebraic set, where the size of the largest semidefinite constraint is fixed throughout the hierarchy. We further prove a second disjunctive Positivstellensatz which leads to an optimization-free hierarchy for polynomial optimization. We specialize this result to the problem of proving copositivity of matrices. Finally, we describe how the disjunctive sum of squares approach can be combined with a branch-and-bound algorithm and we present numerical experiments on polynomial, copositive, and combinatorial optimization problems.
