KKT conditions for a convex optimization (optimal crowdsourcing with budget constraint)

118 Views Asked by At

I am having some troubles deriving the optimal solution of the following convex optimization problem, $w_j$, $c_{ij}$, and $B$ are fixed and non negative. \begin{align} & \underset{n_{ij}}{\text{minimize}} & & -\sum_{i=1}^{N}\sqrt[]{\sum_{j=1}^{M}n_{ij}w_{j}^2} \\ & \text{subject to} & & \sum_{ij} c_{ij}n_{ij} \leq B\\ &&& n_{ij} \geq 0, \text{ }i=1,...,N,j=1,...,M \end{align} I write out the KKT conditions, $\lambda$ and $\mu$ are the Lagrange multipliers. \begin{align} -\frac{w_{j'}^2}{2\sqrt{\sum_{j=1}^{M} n_{i'j}w_{j}^2}}+\lambda c_{i'j'}-\mu_{i'j'}&=0, \text{ }i'=1,...,N,j'=1,...,M \\ \lambda &\geq 0\\ \mu_{i'j'}&\geq 0, \text{ }i'=1,...,N,j'=1,...,M\\ \lambda(\sum_{ij}c_{ij}n_{ij}-B)&=0\\ \mu_{i'j'}n_{i'j'}&=0, \text{ }i'=1,...,N,j'=1,...,M\\ \end{align} Then, I find that $n_{i'j'}\neq 0$, $\mu_{i'j'}=0$, and $\lambda\neq0$, $B=\sum_{ij}c_{ij}n_{ij}$

From the first KKT conditions, I got \begin{align} \frac{w_{j'}^2}{2\sqrt{\sum_{j=1}^m n_{i'j}w_{j}^{2}}}+\lambda c_{i'j'}=0 \end{align} Then, I dont know how to proceed.

The following is the optimal solution for the above problem. \begin{align} n_{ij}^* = \begin{cases} \frac{B}{\frac{c_{ij_{i}^{*}}^2}{w_{j_{i}^{*}}^2}\sum_{l=1}^{N} \frac{w_{j_{l}^{*}}^2}{c_{lj_{l}^{*}}}} & \quad \text{if } j=j_{i}^{*} \\ 0 & \quad \text{otherwise} \end{cases}\\ \text{where }j_{i}^{*}= \underset{j}{\operatorname{arg\,max}}\frac{w_{j}^2}{c_{ij}} \text{ and }i=1,2,...,N \end{align}

Although I have the optimal solution, I don't how it was done. Could anyone show me the steps? Many thanks.