Finding minimum $\frac{c_1x + c_2y}{x+y}$

Question

I am looking for a good strategy to tackle this non-linear, non-convex optimization problem:

Minimize $$\frac{c_1x + c_2 y}{x+y}$$

such that:

$x, y > 0$

$x + y \leq c_3$

$c_1, c_2, c_3$ are given

$c_3 > 0$

Does anyone have any suggestions?

I know this objective function is non-convex, but I was wondering if there were any smart ways to find (or at least approximate) the global optimum. If you suggest an approximation algorithm, please also share its approximation factor. Computational efficiency is not a major concern for me, but accuracy is.

Currently, my leading (though inelegant) idea is to fix the value of $x + y$ and iterate through possible combinations. In the context of my problem, it is an OK assumption to say there are a finite number of meaningful combinations of $x + y$, so I could conceivable iterate through them, but this would be very inefficient.

In case it helps, there is the option for the additional constraint that $c_1, c_2 > 0$, but it's preferable to retain the freedom for them to be either positive or negative.

Thanks in advance for your help.

Answer 1

Hint: for any $\forall x,y \gt 0$: $$\min(c_1,c_2) \le \frac{c_1x + c_2 y}{x+y} \le \max(c_1,c_2)$$ The bounds are asymptotically approached when $y \to 0$ and $x \to 0$ respectively, but never attained unless $c_1=c_2\,$.

Answer 2

If $x=0$ or $y=0$ you know the value. Otherwise, divide through by $y,$ define $$ r = x/y, $$ and optimize $$ \frac{c_1 r + c_2}{r+1} = \frac{c_1 r + c_1}{r+1} + \frac{c_2 - c_1}{r+1} = c_1 + \frac{c_2 - c_1}{r+1} $$ The other order has $s = y/x $ and $$ \frac{c_1 + c_2 s}{1+s} = \frac{c_2 + c_2 s}{1+s} + \frac{c_1 - c_2}{1+s} = c_2 + \frac{c_1 - c_2}{1+s} $$ Either $r$ or $s$ is allowed to get arbitrarily large without violating the rules.

Answer 3

\begin{eqnarray} \inf_{x>0,y>0, x+y \le c_3} { c_1 x + c_2 y \over x+y } &=& \inf_{r \in (0,c_3]} \inf_{x>0,y>0, x+y = r} { c_1 x + c_2 y \over x+y } \\ &=& \inf_{r \in (0,c_3]} \inf_{x>0,y>0, x+y = r} { c_1 x + c_2 y \over r } \\ &=& \inf_{r \in (0,c_3]} \min_{x\ge 0,y \ge 0, x+y = r} { c_1 x + c_2 y \over r } \\ &=& \inf_{r \in (0,c_3]} \min(c_1,c_2) \\ &=& \min(c_1,c_2) \\ \end{eqnarray} The fourth line follows because the minimisation of a linear functional over the convex hull of a finite number of points (in this case, $(r,0), (0,r)$) can be replaced by the minimisation over those points.