Sinkhorn algorithms and linear programming solvers for optimal partial transport problems

• URL: http://arxiv.org/abs/2407.06481v1
• Date: Tue, 9 Jul 2024 01:08:21 GMT
• Title: Sinkhorn algorithms and linear programming solvers for optimal partial transport problems
• Authors: Yikun Bai,
• Abstract summary: We introduce what we term generalized optimal partial transport'' problems. We then discuss the dual formulation of these problems and the associated Sinkhorn solver.
• Score: 1.8130068086063336
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this note, we generalize the classical optimal partial transport (OPT) problem by modifying the mass destruction/creation term to function-based terms, introducing what we term ``generalized optimal partial transport'' problems. We then discuss the dual formulation of these problems and the associated Sinkhorn solver. Finally, we explore how these new OPT problems relate to classical optimal transport (OT) problems and introduce a linear programming solver tailored for these generalized scenarios.

Related papers

• Convex Physics Informed Neural Networks for the Monge-Ampère Optimal Transport Problem [49.1574468325115]
  Optimal transportation of raw material from suppliers to customers is an issue arising in logistics. A physics informed neuralnetwork method is advocated here for the solution of the corresponding generalized Monge-Ampere equation. A particular focus is set on the enforcement of transport boundary conditions in the loss function.
  arXiv  Detail & Related papers  (2025-01-17T12:51:25Z)
• Gaussian entropic optimal transport: Schrödinger bridges and the Sinkhorn algorithm [0.0]
  Entropic optimal transport problems are regularized versions of optimal transport problems. These problems are commonly solved using Sinkhorn algorithm (a.k.a. iterative proportional fitting procedure) In more general settings the Sinkhorn iterations are based on nonlinear conditional/conjugate transformations and exact finite-dimensional solutions cannot be computed.
  arXiv  Detail & Related papers  (2024-12-24T13:49:02Z)
• A Sinkhorn-type Algorithm for Constrained Optimal Transport [14.935188572016635]
  This work focuses on a general class of OT problems under a combination of equality and inequality constraints. We derive the corresponding entropy regularization formulation and introduce a Sinkhorn-type algorithm for such constrained OT problems supported by theoretical guarantees. Overall, this work systematically combines recent theoretical and numerical advances in entropic optimal transport with the constrained case, allowing practitioners to derive approximate transport plans in complex scenarios.
  arXiv  Detail & Related papers  (2024-03-08T05:01:43Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Neural Time-Reversed Generalized Riccati Equation [60.92253836775246]
  Hamiltonian equations offer an interpretation of optimality through auxiliary variables known as costates. This paper introduces a novel neural-based approach to optimal control, with the aim of working forward-in-time.
  arXiv  Detail & Related papers  (2023-12-14T19:29:37Z)
• A Computational Framework for Solving Wasserstein Lagrangian Flows [48.87656245464521]
  In general, the optimal density path is unknown, and solving these variational problems can be computationally challenging. We propose a novel deep learning based framework approaching all of these problems from a unified perspective. We showcase the versatility of the proposed framework by outperforming previous approaches for the single-cell trajectory inference.
  arXiv  Detail & Related papers  (2023-10-16T17:59:54Z)
• On the Convergence of Projected Alternating Maximization for Equitable and Optimal Transport [36.97843660480747]
  This paper studies the equitable and optimal transport (EOT) problem, which has many applications. In the discrete distributions case, the EOT problem can be formulated as a linear program (LP) Since this LP is prohibitively large for general solvers, Scetbon etal citescetbonequitable suggests to perturb the problem by adding an entropy regularization. They proposed a projected alternating algorithm (PAM) to solve the dual of the entropy regularized EOT.
  arXiv  Detail & Related papers  (2021-09-29T04:32:06Z)
• Optimal transport with $f$-divergence regularization and generalized Sinkhorn algorithm [0.0]
  Entropic regularization provides a generalization of the original optimal transport problem. replacing the Kullback-Leibler divergence with a general $f$-divergence leads to a natural generalization. We propose a practical algorithm for computing the regularized optimal transport cost and its gradient.
  arXiv  Detail & Related papers  (2021-05-29T16:37:31Z)
• Relaxation of optimal transport problem via strictly convex functions [0.0]
  An optimal transport problem on finite spaces is a linear program. Recently, a relaxation of the optimal transport problem via strictly convex functions, especially via the Kullback--Leibler divergence, sheds new light on data sciences. This paper provides the mathematical foundations and an iterative process based on a gradient descent for the relaxed optimal transport problem via Bregman divergences.
  arXiv  Detail & Related papers  (2021-02-15T04:32:13Z)
• A Multi-Agent Primal-Dual Strategy for Composite Optimization over Distributed Features [52.856801164425086]
  We study multi-agent sharing optimization problems with the objective function being the sum of smooth local functions plus a convex (possibly non-smooth) coupling function.
  arXiv  Detail & Related papers  (2020-06-15T19:40:24Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.