= Logarithmic water filling
{title2=$x_i=(\tau-\alpha_i)_+,\quad\sum_i x_i=B$}
To maximize $\sum_i\log(\alpha_i+x_i)$ for positive baselines, nonnegative allocations and a positive budget $B$, the <KKT conditions> equalize the shifted values on allocated coordinates. The unique water level solves $\sum_i(\tau-\alpha_i)_+=B$. Inactive coordinates have baselines at least the water level. <Strict convexity> of the negative objective ensures uniqueness, and sorting the baselines gives an efficient <water-filling algorithm>.
Back to article page
