# Related to Lagrangian dual

In my research class our professor discuss a paper wherein the solution is obtained via a Lagrangian duality. The original problem is given below:

minimize $$t$$

subject to $$\sum_{j \in \mathcal{M_i}}\beta_{ij}x_{ij}\leq t, i \in \mathcal{N}$$ ---(1)

where $$\mathcal{M_i}$$ and $$\mathcal{N}$$ are the sets.

Next, a partial Lagrangian is obtained by dualizing the constraint in (1). To do this , the authors introduced multipliers $$\lambda = (\lambda_i)_{i \in \mathcal{N}}$$ for the first set of inequality constraints.

Thus, the partial Lagrangian is given by

$$L(t, x, \lambda) = t(1-\sum_{i \in \mathcal{N}}\lambda_i)+\sum_{j \in \mathcal{M}}\sum_{i \in \mathcal{N_j}}\beta_{ij}\lambda_ix_{ij}$$ ---(2)

where they used the equivalence of the following two sets

$$\{(i,j)|i \in \mathcal{N}, j \in \mathcal{M_i}\}\equiv \{(n,m)|m \in \mathcal{M}, n \in \mathcal{N_m}\}$$

I am not getting how equation (2) is obtained from equation (1).

Dualizing a constraint comes back to the first, the direction of the objective function, and the second, how the dualized constraint would be violated. In your case, the constraint is written as $$LHS-RHS \leq 0$$, and therefore it is being violated when $$LHS-RHS \geq 0$$. Since we add this into the objective function as: $$min \quad z = t + \sum_{i}\lambda_{i}(\sum_{j}\beta_{ij}x_{ij}-t)$$ by multiplying in the appropriate violation penalties as $$\lambda_{i}$$ as there exist $$i$$ number of such constraint.