Use of Lagrangian dual information to prove optimalitiy of a solution : Any example?

Question

Can anyone please tell me what is Lagrangian Dual Information and how can it be used to prove the optimality of a solution? I'm talking about the solution to NP-Complete problems. Is it something that once you get a solution, you use LDI to prove that it is optimal?? Any example?

Answer 1

Lagrangian duality generalizes standard linear programming duality to the minimization of arbitrary functions (although it's often most effective for convex programs). The rough idea (and Convex Optimization by Boyd and Vandenberghe does a fantastic job of explaining this) is this:

• take a a constrained optimization problem,
• replace it by an unconstrained optimization problem in which the constraints are folded into the objective linearly by multiplying them by variables (the Lagrange multipliers)
• minimize this unconstrained optimization over the original variables
• what you end up with is a convex function of the Lagrange variables, the so-called Lagrange dual
• and minimizing this (easy, because it's convex regardless of the original function) provides a bound on the original optimization.

If the original problem was convex to begin with, and assuming some technnical conditions, this bound is tight and you have strong duality. Since NP-complete problems are nonconvex in general, you can't use Lagrange duals to prove optimality. However, you can use it to get guaranteed approximations. One of the more well known uses of Lagrange duality is in the approximation algorithm for facility location and the $k$-median problem by Jain and Vazirani.

Answer 2

This paper may be useful for you:

Andrade, Lucena, and Maculan, Using Lagrangian dual information to generate degree constrained spanning trees

It proposes Lagrangian based heuristic to solve Degree Constrained Minimum Spanning Tree Problem ($NP$-complete) in very large graphs.