0
$\begingroup$

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.

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

1 Answer 1

1
$\begingroup$

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

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .