Session: Discrete Structures in Nonlinear Optimization
Chair: Qimeng / Kim Yu
Cluster: Interplay Between Continuous and Discrete Optimization
Talk 1: Lower bounds for binary polynomial optimization via signed certificates
Speaker: Liding Xu
Abstract: We consider the binary polynomial optimization (BPO) problem of minimizing a polynomial $f$ over the binary hypercube. The Lasserre and Sherali-Adams hierarchies are well-known successive convex relaxations of BPO. These relaxations are based on certificates for binary non-negativity of polynomials. Developing sparse-aware non-negativity certificates is vital for the scalability of such hierarchical-style-like relaxations, since the sizes of relaxations can blow up combinatorially w.r.t. the level of the relaxation. In this talk, we present a novel approach to constructing binary non-negativity certificates for polynomials and a new class of relaxations. We start with a subclass of binary polynomials with a specific signed support pattern called \emph{nonlinearly negatively signed (NNS) polynomials}. It is easy to identify them, as their nonlinear monomials all have negative coefficients (their linear parts can have arbitrary signs). We show that, for the set of NNS polynomials with $m$ monomials of degree $d$, their binary non-negativity can be checked in a $\bO(m^2d)$ time via minimum cut algorithms, and we construct a linear programming representation for this set through the min-cut-max-flow duality. We categorize binary polynomials based on their signed support patterns. For an arbitrary $n$-variate polynomial, we can decompose it as the sum of an NNS polynomial and a positively signed (PS) polynomial (that only contains nonlinear monomials with positive coefficients). Then, we develop parameterized linear programming representations of binary non-negative polynomials. This allows constructing binary no n-negative signed certificates with adjustable signed support patterns and representation complexities. Because the size of the LP reformulation may be huge, we further propose a refined signed support decomposition to decompose this polynomial as binary non-negativity certificates with simpler signed support patterns and lower representation complexities. This method yields new hierarchies of linear programming relaxations for binary polynomial optimization. The hierarchies of LP relaxations for the BPO that converge in at most $\ceil{\log(n)}$ steps, and each level of the relaxations can be solved in a time doubly exponential in its level number $i \le \ceil{\log(n)}$ (hence exponential in $n$). Moreover, since our decomposition only depends on the support of $f$, the new hierarchies are sparsity-preserving. We also provide preliminary computational experiments on comparing the proposed relaxations with SDP relaxations for max cut problems. This is a joint work with Leo Liberti.
Talk 2: Solving convex quadratic optimization with indicators over graphs with small treewidth
Speaker: Aaresh Bhathena
Abstract: This paper studies convex quadratic optimization problems where each continuous variable is coupled with an indicator variable. Our focus is on the structured case in which the matrix $Q$ defining the quadratic term is positive definite and whose sparsity pattern corresponds to the adjacency matrix of a graph with small treewidth. We introduce a dynamic programming algorithm that solves this problem in linear time with respect to $n$, under the assumptions of a fixed condition number of $Q$, fixed treewidth, and linear volume growth of the underlying graph. Computational experiments on synthetic data demonstrate that our algorithm significantly outperforms state-of-the-art mixed-integer quadratic programming solvers on instances with over 20,000 indicator variables. To demonstrate the practical utility of the method, we develop a novel framework for joint forecasting and anomaly detection by extending exponential smoothing to handle time series data with outliers. This framework is applied to various real-world instances from the Numenta Anomaly Benchmark, which includes traffic and AWS CloudWatch datasets.
Talk 3: The Augmented Factorization Bound for Maximum-Entropy Sampling
Speaker: Yongchun Li
Abstract: The maximum-entropy sampling problem (MESP) aims to select the most informative principal submatrix of a pre- specified size from a given covariance matrix. This paper proposes an augmented factorization bound for MESP based on concave relaxation. By leveraging majorization and Schur-concavity theory, we demonstrate that this new bound dominates the classic factorization bound of Nikolov (2015) and a recent upper bound proposed by Li et al. (2024). Furthermore, we provide theoretical guarantees that quantify how much our proposed bound improves the two existing ones and establish sufficient conditions for when the improvement is strictly attained. These results allow us to refine the celebrated approximation bounds for the two approximation algorithms of MESP. Besides, motivated by the strength of this new bound, we develop a variable fixing logic for MESP from a primal perspective. Finally, our numerical experiments demonstrate that our proposed bound achieves smaller integrality gaps and fixes more variables than the tightest bounds in the MESP literature on most benchmark instances, with the improvement being particularly significant when the condition number of the covariance matrix is small.
