Skip to main content
3 of 3
edited tags
Fawen90
  • 1.4k
  • 4
  • 8

A variant of (discrete) optimal transport problem

Let $\alpha=(\alpha_1,\ldots,\alpha_m)\subset\mathbb R^m_+$ and $\beta=(\beta_1,\ldots,\beta_n)\subset\mathbb R^n_+$ be given and satisfy

$$\sum_{i=1}^m \alpha_i =1 = \sum_{j=1}^n\beta_j.$$

Define $\Pi(\alpha,\beta)\subset \mathbb R^{mn}_+$ be the subset consisting $c=(c_{ij})_{1\le i\le m, 1\le j\le n}$ satisfying for all $i=1,\ldots, m$ and $j=1,\ldots, n$

$$\sum_{j=1}^n c_{ij} =\alpha_i \quad \mbox{ and } \quad \sum_{i=1}^m c_{ij} =\beta_j.$$

Consider the minimisation problem as follows:

$$\min_{c\in \Pi(\alpha,\beta)}~~ \sum_{j=1}^n\left[\sum_{i=1}^m c_{ij}|x_i|^2 -\frac{\big|\sum_{i=1}^m c_{ij}x_i\big|^2}{\beta_j}\right],$$

where $x_1,\ldots, x_m\in \mathbb R^d$ are fixed parameters, and $|\cdot|$ denotes the standard Euclidean norm. Is there a "well developed" numerical scheme for the above optimisation problem?

PS : "well developed" means

  1. The numerical scheme must converge (as it is known that the above minimisation problem admits a minimiser);

  2. There are checkable conditions such that the numerical scheme may converge to a minimiser (or at least a local minimiser);

  3. An analysis on the convergence rate is furnished.

Fawen90
  • 1.4k
  • 4
  • 8