How the Lagrangian is obtained in the given example?

76 Views Asked by At

In my work which is related to user association with cellphone towers, I had the following optimization problem:

$$ \begin{array}{clc} & \max\limits_{x_{mk}} \sum\limits_{m=1}^M \sum\limits_{k=0}^K x_{mk} \log \left(R_m^k\right) - \sum\limits_{k=0}^K N_k \log (N_k), & (12) \\ \mathrm{s.t.} &\sum\limits_{k=0}^K x_{mk} = 1, \; x_{mk} \in \{0, 1\}, \; \forall m,k, & (13) \\ & \sum\limits_{m=1}^M x_{mk} = N_k, \; k = 0,1,...,K, & (14) \\ & \sum\limits_{m=1}^M x_{mk} R_m^k \leq N_k R_k^0, \; k=1,2,...,K. & (15) \end{array} $$

Then the Lagrangian dual problem is written as

$$ \begin{array}{clc} & \max\limits_{x_{mk}, N_k} \sum\limits_{m=1}^M \sum\limits_{k=0}^K x_{mk} \left(\log \left(R_m^k\right) - \lambda_{1, k} - \lambda_{2, k} R_m^k\right) + \\ & + \sum\limits_{k=0}^K \left(-N_K \log(N_k) + \lambda_{1,k}N_k + \lambda_{2, k} R_k^{0} N_k\right), & (16) \\ \mathrm{s.t.} &\sum\limits_{k=0}^K x_{mk} = 1, & (17) \\ & x_{mk} \in [0, 1]. & (18) \end{array} $$

where $\lambda_{1,k}$ and $\lambda_{2,k}$ are Lagrangian multipliers for constraint $(14)$ and $(15)$ respectively.

My query is how the eq $(16)$ is obtained from eq $(12-15)$. I had tried obtaining, but my all terms are not matching with the equation $(16)$.

Any help in this regard will be highly appreciated.