1
$\begingroup$

Can anybody clarify the following to me? Consider an LP, say a maximization problem, with solution x* and optimal value Z*. Its dual will have optimal value W*=Z* (by strong duality) and optimal solution y*.

Consider a lagrangian relaxation of the primal $max ZLR(\lambda)=cx+\lambda(b-Ax)$, where $\lambda$ are Lagrangian multipliers (assume not all constraints have been relaxed). Say that we solve the so called Lagrangian Dual (i.e., we find $Z_D=\min_{\lambda}\{ZLR(\lambda)\}$).

In which cases we can state that:

  1. $\lambda$ is equal to y* for the constraints relaxed
  2. x which solves the lagrangian is feasible or optimal for the primal,
  3. $Z_D=Z^*=W^*$

Thanks for the clarification. References are welcome.

$\endgroup$
0
$\begingroup$

I think I might have arrived to at least part of the answer, but comments will still be highly appreciated.

Consider the following LP: $$\max cx\\ a_ix\leq b_i,\quad i=1,\ldots,m\\ x\geq 0$$

The Lagrangian relaxation problem consists of finding, for $\lambda\geq 0$:

$$ZLR(\lambda)=\max_x \{\sum_{j=1}^n(c_j-\sum_{i=1}^m\lambda_ia_{ij})x_j+\sum_{i=1}^m\lambda_ib_i\}$$

Here, we see that we obtain the maximum in $\sum_{i=1}^m\lambda_ib_i$ when $c_j-\sum_{i=1}^m\lambda_ia_{ij}\leq 0, j=1,\ldots,n$ by setting $x=0$. Otherwise, if the latter inequality does not hold for some $j$ we have $ZLR(\lambda)=-\infty$, just by increasing $x_j$ indefinitely. Therefore, we can write the following problem:

$$\min \sum_i \lambda_ib_i\\ \sum_m\lambda_ia_{ij}\geq c_j,\quad j=1,\ldots,n\\ \lambda_i\geq 0 $$

which is exactly the dual problem of the original LP. Since the Lagrangian Dual is $ZD=\min_\lambda ZLR(\lambda)$, from here we understand that the best set of lagrangian multipliers corresponds to the solution to the dual problem. Therefore, if both primal and dual have optimal solutions, their objective values coincide (Strong Duality) and coincide to ZD as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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