= Solution
Let $f(x)=-\sum_i\log(\alpha_i+x_i)$. The feasible <probability simplex> is a nonempty <compact convex set>, so the <extreme value theorem> guarantees a minimizer. Its <Hessian matrix> is diagonal with positive entries $(\alpha_i+x_i)^{-2}$, making $f$ a <strictly convex function>. Hence \b[the minimizer is unique].
Use the <Lagrange multipliers> $\lambda$ for the sum constraint and $\nu_i\geq0$ for $-x_i\leq0$. The <Lagrangian> is
$$
L=f(x)+\lambda\left(\sum_i x_i-1\right)-\sum_i\nu_i x_i.
$$
The <KKT conditions> are
$$
-\frac1{\alpha_i+x_i}+\lambda-\nu_i=0,\qquad
x_i\geq0,\quad \nu_i\geq0,\quad \nu_i x_i=0,\quad \sum_i x_i=1.
$$
A strictly positive feasible allocation exists, so the <Slater condition> holds. These conditions are necessary and sufficient for this <convex optimization>. At least one coordinate is positive, giving $\lambda>0$. Put $\tau=1/\lambda$. For a positive coordinate, <complementary slackness> gives $\alpha_i+x_i=\tau$. At a zero coordinate, stationarity gives $\nu_i=1/\tau-1/\alpha_i\geq0$, or $\alpha_i\geq\tau$. Thus
$$
\boxed{x_i^*=(\tau-\alpha_i)_+,\qquad
\sum_i(\tau-\alpha_i)_+=1.}
$$
Here $(u)_+=\max(u,0)$. This <logarithmic water filling> raises the smaller baseline values to a common level. The scalar left side is a <continuous function> and strictly increasing above $\min_i\alpha_i$, starts at zero, and tends to infinity, so exactly one $\tau$ solves it. One can find it by <interval bisection>, or sort the baseline values increasingly and find an index $k$ for which
$$
\tau=\frac{1+\sum_{i=1}^k\alpha_{(i)}}k,
\qquad \alpha_{(k)}<\tau\leq\alpha_{(k+1)},
$$
using $\alpha_{(n+1)}=+\infty$. Equality at the next baseline simply gives a zero allocation. Sorting and a running sum implement the <water-filling algorithm> in $O(n\log n)$ time.
Back to article page
