How to find the values of $x,y,z$ to give a maximum value of $\min\{ax,by,cz\}/(x+y+z)$.

82 Views Asked by At

$a,b,c$ are all known positive rational numbers (e.g. $a=2.1,b=3.5,c=7.4$). They are also always $\geq1$ but I'm not sure if that helps. $\min\{ax,by,cz\}$ means the minimum out of those three products.

This feels like an optimisation problem but I'm not sure how to approach it. I'm hoping to solve this programmatically, so that it can be solved for several thousand sets of coefficients.

2

There are 2 best solutions below

1
On BEST ANSWER

Suppose that $ax$ is the minimum; then $y$ can be reduced to $ax/b$ without changing the numerator but decreasing the denominator; and similarly for $z$. And similarly if one of the other two products is the minimum.

So the maximum of the quotient is going to be achieved when $ax=by=cz$, that is, when $x=\lambda/a$, $y=\lambda/b$, $z=\lambda/c$ for some constant $\lambda$, so that the quotient equals $1/(\frac1a+\frac1b+\frac1c)$.

0
On

One way to model a minimum so it can be solved programmatically is to turn it into a series of optimization problems. In each of these problems you evaluate the set of points for which one of the elements of the minimum is minimal:

$$ \max_{x_1,...,x_n\in\mathbb{R}}\min\{f_1(x_1),...,f_n(x_n)\}/(x_1+...+x_n) = \max_{i=1,..,.n} \left(\max_{x_1,...,x_n\in\mathbb{R}\\f_i(x_i)\le f_1(x_1)\\...\\f_i(x_i)\le f_n(x_n)}f_i(x_i)/(x_1+...+x_n) \right) $$

The above formula holds in an even more general context, but depending on how complex the $f_i$ are, it may or may not be programmatically feasible.

In your case the constraints create a convex polyhedron, so a nonlinear solver probably can solve even a series of 1000 problems rather quickly.

That said, doing a theoretical analysis of your optimization problem and simplifying it will bring you a possibly tremendous speed up