Samiksha Jaiswal (Editor)

Strong duality

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

Strong duality is a concept in optimization such that the primal and dual solutions are equivalent. This is as opposed to weak duality (the primal problem has optimal value not smaller than the dual problem, in other words the duality gap is greater than or equal to zero).

Contents

Characterizations

Strong duality holds if and only if the duality gap is equal to 0.

Sufficient conditions

  • F = F ∗ ∗ where F is the perturbation function relating the primal and dual problems and F ∗ ∗ is the biconjugate of F (follows by construction of the duality gap);
  • F is convex and lower semi-continuous (equivalent to the first point by the Fenchel-Moreau theorem)
  • the primal problem is a linear optimization problem;
  • Slater's condition for a convex optimization problem.

    • References

    Strong duality Wikipedia
    (Text) CC BY-SA