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: A Parametric Approach for Solving Convex Quadratic Optimization with Indicators Over Trees
Speaker: Aaresh Bhathena
Abstract: We investigate convex quadratic optimization problems involving $n$ indicator variables, each associated with a continuous variable, particularly focusing on scenarios where the matrix $Q$ defining the quadratic term is positive definite and its sparsity pattern corresponds to the adjacency matrix of a tree graph. We introduce a graph-based dynamic programming algorithm that solves this problem in time and memory complexity of $\mathcal{O}(n^2)$. Central to our algorithm is a precise parametric characterization of the cost function across various nodes of the graph corresponding to distinct variables. Our computational experiments conducted on both synthetic and real-world datasets demonstrate the superior performance of our proposed algorithm compared to existing algorithms and state-of-the-art mixed-integer optimization solvers. An important application of our algorithm is in the real-time inference of Gaussian hidden Markov models from data affected by outlier noise. Using a real on-body accelerometer dataset, we solve instances of this problem with over 30,000 variables in under a minute, and its online variant within milliseconds on a standard computer.
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.
