# Motivation behind Lagrangian duality

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.

• 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. – learning Nov 1 '17 at 18:58
• 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. – Stoner Nov 1 '17 at 19:06
• Did you learn Lagrange Duality as part of a Machine Learning class? – learning Nov 1 '17 at 19:07
• @learning No, its solely based on integer programming. – Stoner Nov 1 '17 at 19:09
• @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. – Marcello Sammarra Nov 3 '17 at 20:39