Time: Wednesday, 04/Sept/2024: 11:00am - 12:00pm Session Chair: Jan Krause |
Location: Wirtschaftswissenschaften Z538 Room Location at NavigaTUM |
A low-rank high-precision solver for semidefinite programming
University of Klagenfurt, Austria
Low-rank approaches for solving semidefinite programs have recently attracted a lot of attention. In this talk, we present a new solver for semidefinite programs that is capable of computing solutions with arbitrary precision. The idea is to employ the non-convex Burer-Monteiro reformulation to exploit low-rank structure of SDP solutions. We base our approach on a variant of the so-called Mixing Method for diagonally constrained SDPs. The latter implements a coordinate descent approach with respect to the rows/columns of the Burer-Monteiro factorization matrix.
We follow the original approach of Burer and Monteiro and employ an augmented Lagrangian approach to solve the non-convex reformulation. However, instead of minimizing the augmented Lagrangian with respect to the whole factorization matrix, we borrow the idea of minimizing with respect to a single row/column at a time from the Mixing Method, leading to an ADMM-style method. We present promising results on various classes of semidefinite programs, showing that the approach has practical good convergence properties if it is warm-stared from a solution close to the optimum. Our Julia implementation can use arbitrary precision arithmetic and allows the user to solve semidefinite programs to any user-specified precision.
The Bipartite Quadric Polytope with Partitioned Subtotal Constraints and its Application to Pooling Problems
1University of Technology Nuremberg, Germany; 2KPMG, Germany; 3Horváth, Germany
The well-known boolean quadric polytope was introduced by Manfred Padberg in 1989. We study a similar, but more structured version of the latter which we call the bipartite quadric polytope with partitioned subtotal constraints. Here we assume a bipartition on the variables and besides the bilinear product equations, we consider additional linear constraints on one of the variable sets. Elementary polyhedral properties are discussed, including vertex characteristics and valid resp. facet-defining inequalities. In addition to the adaption of the known RLT-inequalities, we find a new class that we call subset-𝑚 inequalities. Furthermore, we investigate a certain variant of the pooling problem that contains the mentioned polytope as a substructure and demonstrate the potential of found cutting planes in this application.