A Generalized Water Filling Problem: $\max_{1^Tx\in[0,1]}\sum_j\ln(\sum_ia_{i,j}x_i)$

95 Views Asked by At

The problem is to find $x^*\in\mathbb R^{|I|}$, s.t.: $$x^*=\operatorname*{arg max}_{1^Tx\in[0,1]}\sum_{j\in J}\ln \left( \sum_{i\in I}a_{i,j}x_i \right)$$

where $(i,j)\in I\times J$ is finite indexes. Positive constant matrix $a\in\mathbb R^{|I\times J|}$.


While I am trying to take the KT condition, I get:

$$\partial_{x_k} \sum_j\ln\left(\sum_ia_{i,j}x_i\right)=\lambda \ \ \forall k\in I$$

$$\sum_j\frac{a_{k,j}}{\sum_ia_{i,j}x_i}=\lambda$$

$\lambda$ is a constant.

which does not seem right at all! I don't know how to do the next step.


I know what I missed (?). There are actually two constraints ($g$):

$$g_1(x)=1^Tx-1\leq0$$ $$g_2(x)=-1^Tx\leq0.$$

Therefore the KKT condition translates into... The same expression (sad)


Not a homework.

1

There are 1 best solutions below

2
On BEST ANSWER

As long as I understood the problem reads as

$$ \max \sum_{j\in J}\ln(a_j^{\top} x) $$

subjected to

$$ 0 \le \left< x,1 \right>\\ \left< x, 1 \right> \le 1 $$

This can be formulated as a Lagrangian multipliers with slack variables problem

$$ L(x,\lambda, \epsilon) = \sum_{j\in J} \ln{a_j^{\top} x}+\lambda_1(\left< x,1 \right>-\epsilon_1^2)+\lambda_2(\left< x,1 \right>-1+\epsilon_2^2) $$

with stationary points given by the solutions for

$$ \nabla_{x_i}L = \sum_{j\in J}\frac{a_j^i}{a_j^{\top}x}+\lambda_1+\lambda_2 = 0\\ \nabla_{\lambda_1}L = \left< x,1 \right>-\epsilon_1^2=0\\ \nabla_{\lambda_2}L = \left< x,1 \right>-1+\epsilon_2^2=0\\ \nabla_{\epsilon_1}L = \lambda_1\epsilon_1 = 0\\ \nabla_{\epsilon_2}L = \lambda_2\epsilon_2 = 0 $$

I hope this helps.