|Project Title: Gibbs manifolds and semidefinite programming
Advisors: B. Sturmfels (MPG), S. Telen (MPG), M. Laurent (NWO-I), Mentor: Georgios Korpas (HSBC)
|Objectives: Interior point methods for linear programming use regularization to reduce the problem to smooth convex optimisation on a polytope. A popular choice for the regularization is a strictly convex entropy function. In this case, under suitable assumptions, the optimizer of the regularized problem is the intersection of the feasible polytope with a toric variety. The geometry and combinatorics behind this story are quite rich and well-developed, and they have lead to a better understanding of these interior point methods. Entropic regularization exists for semidefinite programming (SDP) too. Here one uses the von Neumann entropy, which is strictly convex on the positive semidefinite cone. The role of the toric variety is played by the Gibbs manifold, which is the image under the matrix exponential map of a linear space of symmetric matrices. In this project we will develop the geometry and combinatorics of entropic regularization for SDP. We also investigate scenarios in which the Gibbs manifold is algebraic. Optimal transport is a particular linear program whose entropic regularization can be solved using Sinkhorn scaling. Quantum optimal transport (QOT) is a generalization of interest in quantum information theory. It is used, for instance, to define a notion of Wasserstein distance between quantum states. The optimal transport problem and its quantum analogue can be defined for any undirected graph, in which case we are addressing an optimisation problem in a high-dimensional space of tensors. The feasible regions are marginal polytopes or marginal spectrahedra as specified by the graph. The Gibbs manifold for QOT is isomorphic to a product of projective spaces. We will investigate the algebraic degree of QOT and explore Sinkhorn-like algorithms for finding the unique positive semidefinite optimizer.
|Expected Results: A new geometric approach to entropic regularization for semidefinite programming and a generalization of Sinkhorn scaling algorithms for quantum optimal transport.
|Planned secondment(s): with Monique Laurent at NWO-I (M21-31) to use the newly developed results for semidefinite relaxations of polynomial optimisation problems; with G. Korpas at HSBC Lab (M32-33) to work on Quantum Optimal Transport.
|Joint degree: University of Leipzig, University of Tilburg