# How can I convexify (allowed some approximation) the objective function?

I have a known matrix, $$H$$ of size $$U\times B$$. The optimization variable is $$D$$ of same size, which is binary

Now I have $$S_u=\frac{\sum\limits_{b=1}^{B} D_{u,b}H_{u,b}}{\sum\limits_{b=1}^{B}H_{u,b}-\sum\limits_{b=1}^{B} D_{u,b}H_{u,b}},\quad \forall u\in\{1,\cdots, U\}$$ and I want to maximize $$\sum\limits_{u=1}^US_u$$.

UPDATE:

with $$b_\min\le \sum_{b=1}^B D_{u,b}\le b_\max, \forall u$$ and $$\sum_{u=1}^{U}D_{u,b}\le u_\max, \forall b$$

Can I perform some alternative formulation so that the function becomes convex, or any convex approximation?

EDIT:

The denominator is strictly non-negative. The first or positive part of the denominator denotes the case where $$D_{u,b}=1, \forall b, b=1,\cdots, B$$

Also, the elements in $$H$$ are non-negative.

• Do you have any other constraints? If not, you can solve a separate problem for each $u$. Nov 24 '20 at 2:07
• For EDIT-2, you should not mix $\sum_u$ and $\forall u$. Nov 24 '20 at 2:08
• @RobPratt, yes, I have other constraints. The constraints are on $D$. Please see my update. Nov 24 '20 at 8:41
• @RobPratt, how can I enforce the equality constraint? does it make much sense to add an equality constraint in optimization? Nov 25 '20 at 10:15
• In your new denominator, you have $\sum_u$ when the ratio itself depends on $u$. Should the sum instead be over a dummy index $v$ or just omitted? Nov 25 '20 at 14:07

Because you have a sum of ratios here, introduce a new variable $$T_u$$ for each summand $$S_u$$. The idea is to multiply numerator and denominator by $$T_u$$ so that the denominator becomes 1. You want to maximize $$\sum_{u,b} D_{u,b} H_{u,b} T_u$$ subject to $$\sum_b H_{u,b} T_u - \sum_b D_{u,b} H_{u,b} T_u = 1$$ for each $$u$$. Now introduce $$Y_{u,b} = T_u\cdot D_{u,b}$$ to linearize both objective and constraint: $$\text{maximize \sum_{u,b} H_{u,b} Y_{u,b} subject to \sum_b H_{u,b} T_u - \sum_b H_{u,b} Y_{u,b}=1}$$ Finally, linearize the relationship between $$Y$$ and $$D$$.
For your new question in EDIT 2, first linearize $$P_{u,b}D_{u,b}$$ and then apply Charnes-Cooper.
• @RobPratt, thanks for your answer. I am now implementing it. In fact, I posted a simplified version of my problem. In my original problem, I have another variable, $P_{u,b}$. How can I deal with it? See my EDIT-2. Nov 24 '20 at 0:04