Does anyone know if the following optimization problem has an elegant solution? Let $A=\{a_1, a_2, \ldots, a_n\}$ be positive real numbers. Let $B=\{b_1, b_2, \ldots, b_n\}$ be unknown positive real values that sum to a fixed total $L$. Given $L$ and $A$, choose values for $b_1, b_2, \ldots, b_n$ to minimize $J(B)=\sum_{i=1}^n \frac{a_i}{\sqrt{b_i}}$.
Asked
Active
Viewed 110 times
1
-
1Lagrange multipliers should work nicely. – André Nicolas Jan 14 '14 at 06:19
-
Yes, @AndréNicolas, I know I could find the solution numerically using Lagrange multipliers, but I was hoping for a solution that would give me more insight. Thanks! – Tom Dietterich Jan 14 '14 at 06:36
-
It is not exactly numerically. One obtains an explicit expression in terms of the $a_i$. – André Nicolas Jan 14 '14 at 06:38
1 Answers
1
Lagrange multipliers should work fine as always to give you an analytic solution.
Alternately, you have from Holder's inequality: $J^2L \ge \left(\sum a_i^{2/3}\right)^3$. The equality (i.e. minimum) is achieved when the $b_i$ are proportional to $a_i^{2/3}$.
By Holder's Inequality, we have that if $x_i, y_i, z_i$ are sequences of positive real numbers, then
$$\left(\sum x_i^3 \right)^{\frac13} \cdot \left(\sum y_i^3 \right)^{\frac13}\cdot \left(\sum z_i^3 \right)^{\frac13} \ge \sum x_i y_i z_i $$
Equality holds iff there are real numbers $\alpha, \beta$ such that $x_i : y_i = \alpha$ and $x_i : z_i = \beta$ for all $i$.
Now consider $x_i^3 = y_i^3 = \frac{a_i}{\sqrt{b_i}}$ and $z_i^3 = b_i$.
Macavity
- 46,381
-
This looks promising, but can you spell this out in a bit more detail? How does this map to Holder's inequality? – Tom Dietterich Jan 14 '14 at 22:00
-
-