5
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ well the book says, convex optimization includes linear programming problems. Narula-Ho proposed linear 0/1 integer formulation of DCMST. So I can infer DCMST can be solved using convex optimization?? Further, DCMST is NP-complete.Then why you said Lagrange duals are not optimal to solve NP-complete problems?? Did I miss something? $\endgroup$ – user770 Sep 16 '10 at 8:39
  • $\begingroup$ linear programming is not the same as integer programming. The latter is NP-complete (and does not have a convex formulation) Hence the difference. $\endgroup$ – Suresh Venkat Sep 16 '10 at 14:57
3
$\begingroup$

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.

$\endgroup$

Your Answer

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