Session: Advances in Conic Optimization
Chair: Timotej Hrga
Cluster: Conic and Semidefinite Optimization
Talk 1: Completely positive reformulations for sparse quadratic optimization
Speaker: Bo Peng
Abstract: In this talk, we explore the completely positive reformulation of quadratic optimization problems involving the $\ell_0$ quasinorm, which is well-known for promoting solution sparsity. Compared to existing approaches in the literature, we propose novel, more compact relaxations that are proven to be exact under milder conditions. Furthermore, we demonstrate the exactness of a decomposed completely positive relaxation by leveraging inherent sparse patterns of the model. A numerical study is conducted to compare double nonnegative relaxations derived from these reformulations. Extensive numerical experiments illustrate the quality of the resulting bounds while maintaining tractability and scalability.
Talk 2: Connectivity via convexity: Bounds on the edge expansion in graphs
Speaker: Timotej Hrga
Abstract: Convexification techniques have gained increasing interest over the past decades. In this work, we apply a recently developed convexification technique for fractional programs by He, Liu and Tawarmalani (2024) to the problem of determining the edge expansion of a graph. Computing the edge expansion of a graph is a well-known, difficult combinatorial problem that seeks to partition the graph into two sets such that a fractional objective function is minimized. We give a formulation of the edge expansion as a completely positive pro- gram and propose a relaxation as a doubly non-negative program, further strengthened by cutting planes. Additionally, we develop an augmented Lagrangian algorithm to solve the doubly non-negative program, obtaining lower bounds on the edge expansion. Numerical results confirm that this relaxation yields strong bounds and is computationally efficient, even for graphs with several hundred vertices.
Talk 3: Facial Reduction in BiqCrunch
Speaker: Ian Sugrue
Abstract: BiqCrunch is a binary quadratic solver that uses a semidefinite bounding procedure with a branch-and-bound framework to get exact solutions to combinatorial optimization problems. Since its latest official update, BiqCrunch has undergone further development, most notably the inclusion of the dimensionality reduction process known as facial reduction. We will discuss the details of how facial reduction is implemented, the numerical results that support this inclusion, as well as future development plans for BiqCrunch.
