The following equation arises in the water-filling problem:
$\sum_{i=1}^{n} max \left\{ 0, \frac{1}{\nu} - \alpha_i \right\} = 1$
Assuming that all $\alpha_i$s are known, how does one solve for $\nu$?
The following equation arises in the water-filling problem:
$\sum_{i=1}^{n} max \left\{ 0, \frac{1}{\nu} - \alpha_i \right\} = 1$
Assuming that all $\alpha_i$s are known, how does one solve for $\nu$?
One possible method: arrange all $\alpha_i$'s into an increasing sequence:
$\alpha_{(1)} \leq \alpha_{(2)} \leq \alpha_{(3)} \leq \ldots \leq \alpha_{(n)}$
For now, introduce the variable $x=\frac{1}{\nu}$. Then, the problem can be restated as
$\sum_{i=1}^n \max\{0,x-\alpha_{(i)}\} = 1$
We are looking for an $m$ such that
$m x - \sum_{i=1}^m \alpha_{(i)} = 1$
or
$ x = \frac{1+\sum_{i=1}^m \alpha_{(i)}}{m} $
and we must also have that
$ \frac{1+\sum_{i=1}^m \alpha_{(i)}}{m} \geq \alpha_{(j)} \; , \; \forall j \in \{1,\ldots,m\} $
and
$ \frac{1+\sum_{i=1}^m \alpha_{(i)}}{m} < \alpha_{(j)} \; , \; \forall j \in \{m+1,\ldots,n\} $
This gives a method for finding the solution.