Return to Question

This post is a continuation of A variant of (discrete) optimal transport problem

For $\alpha=(\alpha_1,\ldots,\alpha_m)\subset\mathbb R^m_+$, $\beta=(\beta_1,\ldots,\beta_n)\subset\mathbb R^n_+$ and $x_1,\ldots, x_m\in \mathbb R^d$, consider the optimisation problem:

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

where $\Pi(\alpha,\beta)\subset \mathbb R^{mn}_+$ is 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.$$

Let $\sum_{i=1}^m \alpha_i =1 = \sum_{j=1}^n\beta_j$. What is the "best" numerical method to solve the above maximisation problem?

As $F$ is convex, the maximum can be attained at the extremal points of $\Pi(\alpha,\beta)$, where Brendan McKay pointed out a method to identify all the extremal points (see Extreme points of transportation polytope). However, this is too costly for this case (without using the particular structure of $F$ and $\Pi(\alpha,\beta)$). I wish to know whether "efficient" numerical methods are known in the literature for the maximisation of a convex function on a compact and convex subset?

PS: I'm very surprised that very few result on this issue. For practical purpose, $d=2,3$, $1\le n\le 20$ and $m\approx 100,000$.

PS2 : We can write $F$ more explicitly:

$$F(c)=\sum_{i,k=1}^m\sum_{j=1}^n \frac{\langle x_i, x_k\rangle}{\beta_j} c_{ij}c_{kj}\equiv \sum_{i,k=1}^m\sum_{j=1}^n a_{ijk} c_{ij}c_{kj}$$

This post is a continuation of A variant of (discrete) optimal transport problem

For $\alpha=(\alpha_1,\ldots,\alpha_m)\subset\mathbb R^m_+$, $\beta=(\beta_1,\ldots,\beta_n)\subset\mathbb R^n_+$ and $x_1,\ldots, x_m\in \mathbb R^d$, consider the optimisation problem:

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

where $\Pi(\alpha,\beta)\subset \mathbb R^{mn}_+$ is 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.$$

Let $\sum_{i=1}^m \alpha_i =1 = \sum_{j=1}^n\beta_j$. What is the "best" numerical method to solve the above maximisation problem?

As $F$ is convex, the maximum can be attained at the extremal points of $\Pi(\alpha,\beta)$, where Brendan McKay pointed out a method to identify all the extremal points (see Extreme points of transportation polytope). However, this is too costly for this case (without using the particular structure of $F$ and $\Pi(\alpha,\beta)$). I wish to know whether "efficient" numerical methods are known in the literature for the maximisation of a convex function on a compact and convex subset?

PS: I'm very surprised that very few result on this issue. For practical purpose, $d=2,3$, $1\le n\le 20$ and $m\approx 100,000$.

PS2 : $F$ can be written more explicitly:

$$F(c)=\sum_{i,k=1}^m\sum_{j=1}^n \frac{\langle x_i, x_k\rangle}{\beta_j} c_{ij}c_{kj}\equiv \sum_{i,k=1}^m\sum_{j=1}^n a_{ijk} c_{ij}c_{kj}.$$

This post is a continuation of A variant of (discrete) optimal transport problem

For $\alpha=(\alpha_1,\ldots,\alpha_m)\subset\mathbb R^m_+$, $\beta=(\beta_1,\ldots,\beta_n)\subset\mathbb R^n_+$ and $x_1,\ldots, x_m\in \mathbb R^d$, consider the optimisation problem:

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

where $\Pi(\alpha,\beta)\subset \mathbb R^{mn}_+$ is 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.$$

Let $\sum_{i=1}^m \alpha_i =1 = \sum_{j=1}^n\beta_j$. What is the "best" numerical method to solve the above maximisation problem?

As $F$ is convex, the maximum can be attained at the extremal points of $\Pi(\alpha,\beta)$, where Brendan McKay pointed out a method to identify all the extremal points (see Extreme points of transportation polytope). However, this is too costly for this case (without using the particular structure of $F$ and $\Pi(\alpha,\beta)$). I wish to know whether "efficient" numerical methods are known in the literature for the maximisation of a convex function on a compact and convex subset?

PS: I'm very surprised that very few result on this issue. For practical purpose, $d=2,3$, $1\le n\le 20$ and $m\approx 100,000$.

PS2 : We can write $F$ more explicitly:

$$F(c)=\sum_{i,k=1}^m\sum_{j=1}^n \frac{\langle x_i, x_k\rangle}{\beta_j} c_{ij}c_{kj}\equiv \sum_{i,k=1}^m\sum_{j=1}^n a_{ijk} c_{ij}c_{kj}.$$

This post is a continuation of A variant of (discrete) optimal transport problem

For $\alpha=(\alpha_1,\ldots,\alpha_m)\subset\mathbb R^m_+$, $\beta=(\beta_1,\ldots,\beta_n)\subset\mathbb R^n_+$ and $x_1,\ldots, x_m\in \mathbb R^d$, consider the optimisation problem:

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

where $\Pi(\alpha,\beta)\subset \mathbb R^{mn}_+$ is 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.$$

Let $\sum_{i=1}^m \alpha_i =1 = \sum_{j=1}^n\beta_j$. What is the "best" numerical method to solve the above maximisation problem?

As $F$ is convex, the maximum can be attained at the extremal points of $\Pi(\alpha,\beta)$, where Brendan McKay pointed out a method to identify all the extremal points (see Extreme points of transportation polytope). However, this is too costly for this case (without using the particular structure of $F$ and $\Pi(\alpha,\beta)$). I wish to know whether "efficient" numerical methods are known in the literature for the maximisation of a convex function on a compact and convex subset?

PS: I'm very surprised that very few result on this issue. For practical purpose, $d=2,3$, $1\le n\le 20$ and $m\approx 100,000$.

PS2 : We can write $F$ more explicitly:

$$F(c)=\sum_{i,k=1}^m\sum_{j=1}^n \frac{\langle x_i, x_k\rangle}{\beta_j} c_{ij}c_{kj}\equiv \sum_{i,k=1}^m\sum_{j=1}^n a_{ijk} c_{ij}c_{kj}$$

This post is a continuation of A variant of (discrete) optimal transport problem

For $\alpha=(\alpha_1,\ldots,\alpha_m)\subset\mathbb R^m_+$, $\beta=(\beta_1,\ldots,\beta_n)\subset\mathbb R^n_+$ and $x_1,\ldots, x_m\in \mathbb R^d$, consider the optimisation problem:

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

where $\Pi(\alpha,\beta)\subset \mathbb R^{mn}_+$ is 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.$$

Let $\sum_{i=1}^m \alpha_i =1 = \sum_{j=1}^n\beta_j$. What is the "best" numerical method to solve the above maximisation problem?

As $F$ is convex, the maximum can be attained at the extremal points of $\Pi(\alpha,\beta)$, where Brendan McKay pointed out a method to identify all the extremal points (see Extreme points of transportation polytope). However, this is too costly for this case (without using the particular structure of $F$ and $\Pi(\alpha,\beta)$). I wish to know whether "efficient" numerical methods are known in the literature for the maximisation of a convex function on a compact and convex subset?

PS: I'm very surprised that very few result on this issue. For practical purpose, $d=2,3$, $1\le n\le 20$ and $m\approx 100,000$.

PS2 : If we write $F$ more explicitly, we obtain

$$F(c)=\sum_{i,k=1}^m\sum_{j=1}^n \frac{\langle x_i, x_k\rangle}{\beta_j} c_{ij}c_{kj}\equiv \sum_{i,k=1}^m\sum_{j=1}^n a_{ijk} c_{ij}c_{kj}.$$

This post is a continuation of A variant of (discrete) optimal transport problem

For $\alpha=(\alpha_1,\ldots,\alpha_m)\subset\mathbb R^m_+$, $\beta=(\beta_1,\ldots,\beta_n)\subset\mathbb R^n_+$ and $x_1,\ldots, x_m\in \mathbb R^d$, consider the optimisation problem:

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

where $\Pi(\alpha,\beta)\subset \mathbb R^{mn}_+$ is 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.$$

Let $\sum_{i=1}^m \alpha_i =1 = \sum_{j=1}^n\beta_j$. What is the "best" numerical method to solve the above maximisation problem?

As $F$ is convex, the maximum can be attained at the extremal points of $\Pi(\alpha,\beta)$, where Brendan McKay pointed out a method to identify all the extremal points (see Extreme points of transportation polytope). However, this is too costly for this case (without using the particular structure of $F$ and $\Pi(\alpha,\beta)$). I wish to know whether "efficient" numerical methods are known in the literature for the maximisation of a convex function on a compact and convex subset?

PS: I'm very surprised that very few result on this issue. For practical purpose, $d=2,3$, $1\le n\le 20$ and $m\approx 100,000$.

PS2 : We can write $F$ more explicitly:

$$F(c)=\sum_{i,k=1}^m\sum_{j=1}^n \frac{\langle x_i, x_k\rangle}{\beta_j} c_{ij}c_{kj}\equiv \sum_{i,k=1}^m\sum_{j=1}^n a_{ijk} c_{ij}c_{kj}.$$