3
$\begingroup$

As the title states, what is the motivation behind the Lagrangian duality in integer programming? I tried looking up online references including the post: BigPicture Lagrangian, KKT, Duality, and also $\textbf{Wolsey's}$ $\textit{Integer}$ $\textit{Programming}$ but I can't picture the concepts intuitively (especially certain variables - such as the penalty term $u(d-Dx)$ are introduced). Some insight will be appreciated.

$\endgroup$
  • $\begingroup$ If you're looking for maybe a sort of "application" of duality, then en.wikipedia.org/wiki/Kernel_method. So if our primal problem doesn't have inner products, we can try to see if the dual problem contains inner products in its terms and then apply the kernel trick. $\endgroup$ – learning Nov 1 '17 at 18:58
  • $\begingroup$ I've not learnt that yet and it will probably take quite some time for that, but it does look interesting! Thanks for the heads up. $\endgroup$ – Stoner Nov 1 '17 at 19:06
  • $\begingroup$ Did you learn Lagrange Duality as part of a Machine Learning class? $\endgroup$ – learning Nov 1 '17 at 19:07
  • $\begingroup$ @learning No, its solely based on integer programming. $\endgroup$ – Stoner Nov 1 '17 at 19:09
  • 1
    $\begingroup$ @Stoner Happy for that! As for your “soft” questions, keep in mind that: 1) the optimal value of the Lagrangian function $Z_{LR}(x,u)=cx+u(b-Ax)$ depends on $u$; therefore we can define this dependency as a function, the Lagrangian Dual function, $Z_D(u)=\max Z_{LR}(x,u)$; 2) the Lagrangian problem is a maximisation problem with binary variables; therefore if the lagrangian cost of a variable is negative, for a given set of multipliers, then that variable will take the null value whenever it is feasible. $\endgroup$ – Marcello Sammarra Nov 3 '17 at 20:39

Your Answer

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

Browse other questions tagged or ask your own question.