MaxMin of Sum of Fractionals Optimization Problem

Question

Let $\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(L)}$ be $L$ vectors of $N$ variables. Then, how can I solve the following fractional optimization problem? \begin{align} \max_{\mathbf{x}^{(1)},\ldots,\mathbf{x}^{(L)}}&\min_n\quad \sum_{\ell} \frac{x_n^{(\ell)}}{\alpha+\sum_{m}\beta_m^{(n,\ell)}x_m^{(\ell)}}\\ \text{subject to}&\quad\sum_{\ell=1}\mathbf{A}^{(\ell)}\mathbf{x}^{(\ell)}\leq \mathbf{1}, \end{align} where $\alpha$ and $\beta_m$'s are non-negative constants. Moreover, $\mathbf{A}^{(\ell)}$'s are $M\times N$ matrices with non-negative entries. Inequlity is entry-wise and $\mathbf{1}$ is all-one vector.

Answer 1

As I explained before, the problem is difficult. Here is an approach that will give an approximate solution (feasible but not necessarily optimal). The difficulty in this approach is the distribution of the budget constraints.

For each $\ell$, you first estimate a Pareto frontier of $N$ objectives: \begin{align} \max_{\mathbf{x}^{(\ell)}}& \frac{x_n^{(\ell)}}{\alpha+\sum_{m}\beta_m^{(n,\ell)}x_m^{(\ell)}}\\ \text{subject to}&\quad\mathbf{A}^{(\ell)}\mathbf{x}^{(\ell)}\leq \mathbf{b}^{(\ell)}. \end{align} Some Pareto optimization techniques use a weighted sum of the $N$ objectives, which does not simplify the problem at all. You should use a method where you optimize one objective while constraining the other objectives. The right hand side in the constraints should be picked in a way such that $\sum_\ell \mathbf{b}^{(\ell)} = \mathbf{1}$, for example via $\mathbf{b}^{(\ell)} = \mathbf{1}/L$. The result of this step is a large set of Pareto-optimal solutions (say $(x^{(\ell,k)})_{k\in K}$).

The next step is to pick one $x^{(\ell)}$ for each $\ell$ that optimizes the original objective. Precompute $p_{\ell n k} := (x_n^{(\ell,k)}) / (\alpha+\sum_{m}\beta_m^{(n,\ell)}x_m^{(\ell,k)})$. The following mixed integer linear optimization problem picks the optimal $x$ within the set of Pareto optimal solutions: $$\max_y \min_n \{ \sum_{\ell,k} p_{\ell nk}y_{\ell k} : \sum_k y_{\ell k}=1 \; \forall \ell, \; y_{\ell k} \in\{0,1\} \}, $$ which you can solve as: $$\max_{y,t} \{ t : t \leq \sum_{\ell,k} p_{\ell nk}y_{\ell k} \; \forall n, \; \sum_k y_{\ell k}=1 \; \forall \ell, \; y_{\ell k} \in\{0,1\} \}. $$