Dissecting the duality gap: the supporting hyperplane interpretation revisited (Q2119761): Difference between revisions

The classical supporting hyperplane illustration of the duality gap for non-convex optimization problems has been extended, by dissecting the gap into two contributions: near-optimality in the Lagrangian relaxation and near-complementarity in the Lagrangian relaxed constraints. This dissection adds improved understanding of the nature of the duality gap. Further it is demonstrated that this dissection may have implications on the design of solution approaches. An example is given to show of how this dissection may be exploited in the design of a solution approach within discrete optimization.