Skip to main content
1 of 3
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{(\sum_{i=1}^m c_{ij}x_i)^2}{\beta_j}\right].$$

Is there a "well developed" numerical scheme for the above optimisation problem?

Fawen90
  • 1.4k
  • 4
  • 8