# MaxMin of Sum of Fractionals Optimization Problem

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.

• even for fixed $n$ this is a difficult problem, see Fractional Programming: the sum-of-ratios case by Schaible and Shi. Aug 11, 2020 at 21:30
• What are $A, \alpha, \beta$? Oct 31, 2020 at 16:45
• you added a bounty but never bothered to even reply to an elaborate answer? Nov 11, 2020 at 23:12
• Thank you for your answer. But this solution method may be far from the optimal answer. Nov 12, 2020 at 22:58

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\} \}.$$