3
$\begingroup$

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

$\endgroup$
1

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

To ease notation, let me use B as (sum_j Beta_ij.x_ij). Then the constraint (1) is B-t <=0... You multiply this with lambda_i (let me use L for short of sum_i Lambda_i) and carry to objective function, so new objective is: t + L(B-t) = t-Lt + LB = t(1-L)+ LB

$\endgroup$
1
  • $\begingroup$ Thank you so much @Omidi ....but I am having a query that when in constraint only one summation is present then how second summation is also coming into picture... $\endgroup$
    – chaaru
    Commented Aug 9, 2022 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.