CRII: CIF: Leveraging the Laplacian Paradigm for Efficient Non-Convex Optimization in Transportation and Payment Channel Networks

Within the last 15 years, permissionless, decentralized electronic cash systems based on a public consensus mechanism, such as Bitcoin, have emerged as credible tools for efficient cross-border payments, financial inclusion and debasement protection. While payment channel networks (PCNs) such as the Lightning network help to overcome their inherent limitations with respect to payment throughput and transaction speed, the reliability of such off-chain payments is not guaranteed, especially for participating individuals with limited abilities to allocate large capital amounts to establish payment channels. So-called multipart payments have the potential to ensure reliable, cheap payments within PCNs, but to reach their full potential, require the solution of non-standard optimization problems which are challenging for currently available optimization algorithms and solvers. This project aims to fill this gap and develop novel optimization algorithms suitable for such problems, and to provide scalable implementations via an open-source software toolbox. The resulting algorithms will also of useful for urban planners, in particular in the context of public transportation and road systems. For such urban planning applications, designs can be improved by solving related optimization problems whose formulations jointly model commuter goals, capacity constraints and economies of scale. The research project involves the mentoring of a graduate student as well as the development of new course materials on the technology of digital asset systems into existing course curricula.As a first goal, the project aims to develop prototypes of iterative optimization algorithms for capacitated and uncapacitated minimum-cost flow problems with non-convex objectives based on continuous optimization and the framework of iteratively reweighted least squares, building on a new generation of robust Laplacian linear system solvers to solve the associated subproblems. Subsequently, the project intends to generalize these algorithms to problems involving multicommodity flows and to develop scalable software implementations that are adapted to the specific necessities and challenges within payment channel networks and transportation networks. A complementary research thrust within the project is the theoretical convergence analysis of the resulting algorithms, which will shed light on their performance guarantees and limitations.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.