Optimization problem solution (water-filling)

convex optimizationconvex-analysisoptimizationprogramming

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!

Best Answer

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$.

Related Question