A variant of (discrete) optimal transport problem

Question

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.

Answer 1

The minimum here can be found exactly, in a finite number of steps.

Indeed, the target function is concave. So, its minimum on the (compact) (transportation) polytope $P:=\Pi(\alpha,\beta)$ is attained at one of the extreme points of $P$. For a construction and a characterization of all extreme points of $P$, see this answer by Brendan McKay.