It seems to me that the solution to the optimization over $\lambda \in \mathbb{R}^n$ \begin{align} & \underset{\lambda}{\arg\min} \sum_i c_i/\lambda_i\\ \textbf{s.t } & \sum_i \lambda_i = 1\\ & \lambda_i \geq 0 \end{align} where $c \in \mathbb{R}^n$, $c_i \geq 0$, is $\lambda_i = \frac{c_i}{\sum_i c_i}$, but I'm having trouble showing so... Is this the correct minimizer? How might it be derived?
Asked
Active
Viewed 68 times
2
-
1What is the meaning of arg? – DBFdalwayse Sep 01 '13 at 08:58
-
@DBF: http://en.wikipedia.org/wiki/Arg_max#Arg_min – Anthony Carapetis Sep 01 '13 at 09:01
-
I see, so it is the pre-image set of the min of the upper expression. Thanks. – DBFdalwayse Sep 01 '13 at 09:04
-
@DBF The variables are all real numbers I mean to minimize the sum as written. Although I'm not entirely sure what/why you are asking. – fairidox Sep 01 '13 at 09:12
2 Answers
3
This is a minimization problem with a constraint, namely that $\sum \lambda_i =1$. Use Lagrange multipliers to write: $$f(\lambda, \Lambda)=\sum \frac{c_i}{\lambda_i}+\Lambda\left(\sum \lambda_i-1\right)$$ The minimum will be achieved when: $$\frac{\partial f}{\partial \lambda_i}=0,\ \frac{\partial f}{\partial \Lambda}=0$$ Or: $$-\frac{c_i}{\lambda_i^2}+\Lambda=0 \ \to \ \lambda_i=\sqrt{c_i/\Lambda}$$ $$\sum \lambda_i = 1 \ \to \ \Lambda=\left(\sum \sqrt{c_i}\right)^{2}$$ So that the minimum is achieved when: $$\lambda_i =\frac{\sqrt{c_i}}{\sum \sqrt{c_i}}$$ Note that this is your solution if $c_i\to c_i^2$.
Nathaniel Bubis
- 33,018
2
By Cauchy Schwarz inequality we have
$$\sum \frac{c_i}{\lambda_i} \cdot \sum \lambda_i \ge \left(\sum \sqrt{c_i} \right)^2$$
and equality is possible if $\lambda_i^2$ is proportional to $c_i$ or if $\lambda_i = \dfrac{\sqrt{c_i}}{\sum \sqrt{c_i}}$
Macavity
- 46,381