Optimization problem solution (water-filling)

Question

Let $x\in\mathbb{R}^n$ be an optimization variable and $\alpha\in\mathbb{R}^n$ be an n-dimensional vector. The standard water-filling problem is formulated as

\begin{equation} \begin{array}{ll} \operatorname{minimize} & -\displaystyle\sum_{i=1}^{n} \log \left(\alpha_{i}+x_{i}\right) \\ \text { subject to } & x \succeq 0, \quad \mathbf{1}^{T} x=1 \end{array} \end{equation}

and has a well known solution (see Boyd & Vandenberghe pag. 245).

My question is about a similar problem:

\begin{equation} \begin{array}{ll} \operatorname{minimize} & \max_{i}- \log \left(\alpha_{i}+x_{i}\right) \\ \text { subject to } & x \succeq 0, \quad \mathbf{1}^{T} x=1 \end{array} \end{equation}

The problem is still convex since the maximum of convex function is convex. How the solution would chance for this slightly modified optimization problem? It would be interesting to understand, also in terms of a wireless communication interpretation. Thanks!

Answer 1

I shall prove that the problems are in fact equivalent, in the sense that they both have the same optimal solution $x^*$. Let $P_1$ be the first optimization problem, and $P_2$ the second, and let $\alpha\succ 0$.

If $\tilde{x}$ is the optimal solution for $P_1$, then we know from the book that each $\tilde{x}_i$ satisfies the relation $$ \tilde{x}_i = \max\{0,1/\tilde{\nu} - \alpha_i\}, $$ where $\tilde{\nu}$ is the optimal dual variable associated with the equality constraint.

Now, write $P_2$ equivalently as $$\begin{split} \text{minimize} &\quad t\\ P_2:\quad\text{subject to}&\quad t\geq -\log(\alpha_i + x_i),\quad i=1 ,\ldots,n\\ &\quad x\succeq0,\quad \mathbf{1}^\top x=1. \end{split}.$$

Then, the Lagrangian is $$L(t,x,\mu,\lambda,\nu) = t - \sum_{i=1}^n \mu_i(\log(\alpha_i + x_i) + t) - \lambda^\top x + \nu(\mathbf{1}^\top x - 1) =\\t(1 - \mathbf{1}^\top\mu) - \sum_{i=1}^n\mu_i\log(\alpha_i + x_i) - \lambda^\top x + \nu(\mathbf{1}^\top x - 1).$$

Using this, you can write the KKT conditions of $P_2$ for the primal and dual optimal variables $t^*,x^*,\mu^*,\lambda^*$ and $\nu^*$ as $$x^*\succeq 0,\quad \mathbf{1}^\top x^* = 1,\quad \lambda^*\succeq0,~\mu^*\succeq 0,\quad \lambda_i^*x_i^*=0,\quad t^* + \log(\alpha_i + x_i^*) \geq 0,\quad \mu_i^*(t^* + \log(\alpha_i + x^*_i)) = 0,\quad i=1,\ldots,n,$$ and $$\partial/\partial x_i \left[ L(t^*,x^*,\mu^*,\lambda^*,\nu^*)\right]= -\mu_i^*/(\alpha_i^* + x_i^*) - \lambda_i^* + \nu ^* = 0,~i=1,\ldots,n,\quad \mathbf{1}^\top\mu^* = 1.$$ The last equality is necessary, otherwise the dual becomes unbounded in $t^*$. Eliminating $\lambda^*$ yields: $$x^*\succeq 0,\quad \mathbf{1}^\top x^* = 1,\quad x_i^*(\nu^* - \mu_i^*/(\alpha_i + x_i^*))=0,\quad \nu^*\geq \mu_i^*/(\alpha_i + x_i^*),\quad i=1\ldots,n,$$ and $$\mu^*\succeq 0,\quad \mathbf{1}^\top\mu^* = 1,\quad t^* + \log(\alpha_i + x_i^*) \geq 0,\quad \mu_i^*(t^* + \log(\alpha_i + x^*_i)) = 0,\quad i=1,\ldots,n.$$

These are in fact very similar conditions to those of $P_1$. Now, let $M = \{i\in \{1,\ldots,n\} ~|~ \mu_i^* > 0\}$. This is a nonempty set, because $\mathbf{1}^\top \mu^* = 1$. For all $i\in M$, you can thus deduce (in a similar way to the book) that in fact $$x_i^* = \max\{0, \mu_i^*/\nu^* - \alpha_i\}.$$ Furthermore, we have that $t^* = -\log(\alpha_i + x_i^*)$.

Now, let $M' = \{1,\ldots,n\}\setminus M$. In this case, we have that for all $i\in M'$: $$ x_i^*\nu^* = 0,\quad \nu^* \geq 0,\quad t^* + \log(\alpha_i + x_i^*) \geq 0. $$ We can't have $\nu^* = 0$, otherwise it would imply that $0 < \mu_j^*/(a_j + x_j^*) \leq 0$, for all $j\in M$, which is impossible. So, the only option is that $x_i^* = 0$ for all $i\in M'$.

Thus, the problem reduces to solving the equation: $$ \sum_{i\in M} x_i^* = \sum_{i\in M}\max\{0,\mu_i^*/\nu^* - \alpha_i\} = 1. $$

However, the choice of $\mu$ can be arbitrary, as long as it satisfies the KKT conditions. Let $K = \{i\in\{1,\ldots,n\}~|~ \tilde{x}_i > 0\}$, and suppose we set the multipliers to $$ \mu_i^* = \begin{cases} 1/\lvert K \rvert & i \in K\\ 0 &\text{otherwise,} \end{cases} $$ then $\mathbf{1}^\top \mu^* = 1, \mu^*\succeq 0$. Clearly, we also have $M = K$, which implies $x_i^* = \tilde{x}_i=0$ for all $i\in M'$. Now, setting $\nu^* = \tilde{\nu}/\lvert M \rvert > 0$, then this implies $x_i^* = \tilde{x}_i$ for all $i\in M$, and we get exactly the same solution as $P_1$. And since $\tilde{x}_i + \alpha_i = \tilde{x}_j + \alpha_j$ for all $i,j\in M, i\neq j$, then this implies $$ \log(x_i^* + \alpha_i) = \log(x_j^* + \alpha_j), $$ thus $t^* = -\log(x_i^* + \alpha_i)$ for all $i\in M$, so all of the KKT conditions are satisfied.

Therefore, solving $P_2$ is equivalent to solving $P_1$. The optimal value of $P_2$ is $-\log(\alpha_i + \tilde{x}_i)$, for any $\tilde{x}_i > 0$.

Answer 2

You can solve this problem by using a greedy algorithm. To see intuitively why this is the case, imagine that $\ \alpha_i\ $ is the initial amount of water in the $\ i^\text{th}\ $ of $\ n\ $ buckets, to any selection of which you are required to add water amounting to a total of $\ 1\ $ unit. If $\ w_i\ $ is the amount of water in the $\ i^\text{th}\ $ bucket after you have finished topping them up, and $\ w_\min=\min_\limits{1\le i\le n}w_i\ $ is the smallest amount of water in any of the buckets, you receive a payoff of $\ \log\big(w_\min\big)\ $, which you wish to naximise. Letting $\ x_i\ $ be the amount of water you add to the $\ i^\text{th}\ $ bucket, then (because $\ \log\ $ is a strictly increasing function) your problem is to

\begin{equation} \begin{array}{ll} \operatorname{maximise} & \min_\limits{1\le i\le n} \log \left(\alpha_{i}+x_{i}\right) \\ \text { subject to } & x \succeq 0, \quad \mathbf{1}^{T} x=1\ , \end{array} \end{equation} which is equivalent to the problem posed:

\begin{equation} \begin{array}{ll} \operatorname{minimize} & \max_{i}- \log \left(\alpha_{i}+x_{i}\right) \\ \text { subject to } & x \succeq 0, \quad \mathbf{1}^{T} x=1\ . \end{array} \end{equation}

I shall assume here—as in the problem cited from Boyd and Vandenberghe—that $\ \alpha_i>0\ $ (otherwise there are elements of the feasible set at which the payoff function is not well-defined), and, without loss of generality, that $\ \alpha_i\ $ have been labelled so as to be in non-deceasing order: $$ 0<\alpha_1\le\alpha_2\le\dots\le\alpha_n\ . $$ If $\ \alpha_1<\alpha_2\ $, then when you start adding water to the buckets, there is no point adding it to any other bucket than the first, because as long as that bucket has received no additional water, your payoff will stay at $\ \log\big(\alpha_1\big)\ $, whereas, by adding $\ x_1\ $ of water to that bucket, your payoff will increase to $\ \log\big(\alpha_1+x_1\big)\ $ as long as $\ x_1\le\alpha_2-\alpha_1\ $. Once $\ x_1\ $ reaches $\ \alpha_2-\alpha_1\ $, there is no point adding more water to the first bucket unless you add some to the second as well, since your payoff would otherwise remain stuck at $\ \log\big(\alpha_2\big)\ $. The best solution would thus appear to be to top up as many of the emptiest buckets as you can to the same level, until your reservoir has been used up.

Suppose that your reservoir gets used up once you've raised all of the buckets $\ 1,2,\dots,m\ $ to a level $\ \ell\ge\alpha_i\ $ for $\ i=1,2,\dots\,m\ $. Then you must have $\ \ell\le\alpha_{m+1}\ $—otherwise you would have had to include bucket $\ m+1\ $ among those you've added water to—and $\ x_i=\ell-\alpha_i\ $, so $\ 1=\sum_\limits{i=1}^m\big(\ell-\alpha_i\big)=m\ell-\sum_\limits{i=1}^m\alpha_i\ $, or $$ \ell=\frac{1}{m}\left(1+\sum_\limits{i=1}^m\alpha_i\right)\ . $$ This leads us to define \begin{align} m^*&=\max\left\{m\in\mathbb{N}\,\bigg|\,1+\sum_\limits{j=1}^m\alpha_j\ge m\alpha_i\ \ \text{ for }\ 1\le i\le m\right\}\\ \ell^*&=\frac{1}{m^*}\left(1+\sum_\limits{j=1}^{m^*}\alpha_j\right)\\ x_i^*&=\cases{\ell^*-\alpha_i&if $\ 1\le i\le m^*$\\ 0&otherwise.} \end{align} With these definitions, we have \begin{align} \ell^*&=\frac{1}{m^*}\left(1+\sum_\limits{j=1}^{m^*}\alpha_j\right)\\ &\ge\alpha_i\ \ \text{ for }\ 1\le i\le m^*\ \text{, and}\\ 1+\sum_\limits{j=1}^{m^*+1}\alpha_j&< \big(m^*+1)\alpha_{m^*+1}\ , \end{align} from which it follows that $\ x_i^*\ge0\ $ and $\ \ell^*\le\alpha_k\ $ for $\ m^*+1\le k\le n\ $. We also have $\ \sum_\limits{i=1}^nx_i^*=\sum_\limits{i=1}^{m^*}\big(\ell^*-\alpha_i\big)=1\ $, from the definition of $\ \ell^*\ $. So $\ x^*\ $ is a feasible solution to the problem with objective value $$ \min_\limits{1\le i\le n} \log\big(\alpha_i+x_i^*\big)=\log\big(\ell^*\big)\ , $$ because $\ \alpha_i+x_i^*=\ell^*\ $ for $\ 1\le i\le m^*\ $, and $\ \alpha_j+x_j^*=\alpha_j\ge\ell^*\ $ for $\ m^*+1\le j\le n\ $.

It is easy to show that $\ x^*\ $ is optimal. If $\ x\ $ is any feasible solution, then since $\ \sum_\limits{i=1}^{m^*}x_i\le1=\sum_\limits{i=1}^{m^*}x_i^*\ $, there must exist at least one $\ k=1,2,\dots,m^*\ $ for which $\ x_k\le x_k^*\ $. Therefore \begin{align} \min_\limits{1\le i\le n}\log\big(\alpha_i+x_i\big)&\le \log\big(\alpha_k+x_k\big)\\ &\le\log\big(\alpha_k+x_k^*\big)\\ &=\log\big(\ell^*\big)\ . \end{align} That is, the objective value for $\ x\ $ cannot exceed its value $\ \log\big(\ell^*\big)\ $ attained by $\ x^*\ $.